1. 随机选择一个满足安全要求的1024位的大素数p，并生成有限域Z_p的一个生成元g∈Z_p^*；
2. 选择一个随机数x(1<x<p-1)，计算y≡g^x(mod p),则公钥为(y,g,p)，私钥为S_k=x。

                          （随机数的选取可以使同一明文在不同时间加密成不同密文）

1. 加密过程：将明文分组比特串分组，是分组长度小于LOG₂p,，然后对每个明文分组分别加密
   1. 得到公钥P_k（y,g,p）；
   2. 消息m分组m₁m₂m₃m₄······
   3. 对第i块消息随机选择整数r_i(1<ri<p-1);
   4. 计算c_i≡g^r_i(mod p),c_i'≡m_iy^r_i(mod p)(1≤i≤t)
   5. 将密文C=(c₁,c₁')()()()····发送给接收方  （可知，密文是明文长度的2倍）
2. 解密过程
   1. 接收方接收密文C
   2. 使用密钥x和解密算法m_i≡(c_i'/c_i^x)(mod p)(1≤i≤t)进行计算
   3. 得到明文
3. 正确性

1. 穷举法和列表法（二分查找算法） O（p）
2. 小步大步算法

来源于生日攻击的思想，

小步为 序列1：g¹,···,g^j,···,g^m(1≤j≤m)

大步为 序列2：y,y*g^-m,···，y*g^-im

找到g^j≡y*g^-im(mod p),即找到y=g^j+im(mod p),即x=j+im私钥被找到

@R_747_1304@：O(p^1/2)

3.指数积分法

1.  选取因子基S
2. 建构同余方程组：对若干随机整数k(0≤k≤p)，计算g^k，尝试将g^k写成S中的元素幂次的乘积，即g^k=∏p_i^e_i(mod p),式子两边取离散对数k≡∑e_ilog_g(p_i)(mod (p-1)),重复这个过程，直到有超过m个方程
3. 求log_g(p_i)
4. 计算x:随机取整数r，计算yg^rmod p，使得其值可表示为S中元素幂次的乘积，即yg^r=∏p_i^d_i(mod p),取离散对数可得x≡log_g(y)≡-r+∑d_ilog_g(p_i)(mod (p-1)),如果成功，即求得此解x。

 背包问题：∑a_ix_i=b，这是一个NP完全类问题

特例：超递增序列（每一个元素都比先前的元素和大） 可将背包问题转化为P类问题

1. 选取素数p 和u，且bi为超递增序列
2. 利用uv=1（mod p）可求得v
3. a=ub_k(mod p)
4. {a_i}和p作为公钥，{b_i}和v作为私钥

1.  明文消息分组
2. 密文c=a₁m₁+···+a_nm_n
   1. 利用{bi}求v c的解，可得消息m　　

1.  NP类问题，至今没有好的求解方法，能经受住穷举攻击
2. 隐蔽性不够，此公钥密码是不安全的

 数论中的欧拉定理，安全性依赖于大整数的素因子分解的困难性

欧拉定理：若a和n互素，则a^Φ(n)≡1(mod n)

密钥生成算法

加密和解密

（1）生成公私密钥

• 选取两个大素数p和q，至少要1024位
• 计算n=p*q
• 随机选取整数e在(1≤e≤Φ(n))作为公钥，要求满足gcd(e,Φ(n))=1
• 用Euclid扩展算法计算私钥d，满足d*e≡1(mod Φ(n)),则e和n是公钥，d是私钥

（3）明文加密 　c=E(m)=m^e(mod n)（4）密文解密。   m=D(c)=cd(mod n)

 1.算法正确性的证明

2.攻击

1. 针对n分解的攻击
   1. 试除法
   2. 因子分解分析法：二次筛因子分析法
   3. 侧信道攻击

           2.针对算法参数的攻击

                       1.对素数p和q选取时的限制；p和q长度相差不大，大小相差要大，否则难以抵御除法的攻击；p-1和q-1都应有大的素因子。

                       2.共模攻击（因此不同用户不用使用相同的p和q）

                       3.低指数攻击

韦尔斯特拉方程 ：E:y²+axy+by=x³+cx²+dx+e。密码学中，常采用的椭圆曲线为： E:y²=x³+ax+b，并要求4a³+27b²≠0

Hasse定理：如果E是有限域GF(p)上的椭圆曲线，N是E上的点(x,y)（其中x,yξGF(p)）的个数，则：|N-(p+1)|≤2(p)^½

椭圆曲线上的点集合E_p（a,b）对于如下定义的加法规则构成一个Abel群：

1. O+O=O;(O是单位元)
2. 椭圆上的点P，P+O=P；
3. P的逆元是-P；

4. 

5. 满足交换律

6. 满足结合律

点乘规则：

• 如果k为整数，kP=P+···+P    （k个P相加）
• 如果s和t为整数，(s+t)P=sP+tP,s(tP)=t(sP)

椭圆曲线点的计算：

1. 选择一个椭圆曲线E，构造一个椭圆群E_p(a,b)。 
2. 在椭圆群中挑选生成元点G=(x₀,y₀),需满足nG=O的最小的n是一个非常大的素数。
3. 选择一个小于n的整数n_B作为私钥，然后利用P_B=n_BG算出P_B。

       公钥为(E,n,G,P_B)，私钥为n_B。

1.  A将明文消息编码成一个数m<p,并在椭圆群E_p(a,b)中任选一点P_t=(x_t,y_t);
2. 在区间[1,n-1]内，A选取一个随机数k，计算P₁：P₁=(x₁,y₁)=kG;
3. 依据接收方B的公钥P_B，A计算点P₂：P₂=(x₂,y₂)=kP_B；
4. A计算密文C=mx_t+y_t;
5. A传送加密数据C_m={kG,P_t+kP_B,C}给接收方B。

1.  接收方B收到Cm;
2. B使用私钥n_B做运算：P_t+kP_B-n_B(kG)=P_t+k(n_BG)-n_B(kG)=P_t;
3. B计算m=(C-y_t)/x_t,得明文m。

 160位的ECC密钥和1024位的RSA和1024位的ElGamal的安全性等同。

 不是以一一对应的陷门单向函数为基础，同一密文可能有多种明文；

随机选取两个大素数p和q，并且p≡q≡3mod4，将p和q作为私钥，n=pq作为公钥