对称密码的不足：每个用户要管理n个密钥，总密钥量是n^2，密钥空间非常大。密钥传递的信道的安全要求非常高。传统加密算法无法抗抵赖。
加密和解密由不同密钥完成
知道加密算法和加密密钥，无法推出解密密钥
明文用公钥加密，解密时用私钥解密
特征：
1.给定x，计算
y
=
f
k
(
x
)
y=f_k (x)
y=fk(x)可行
2.给定y，计算
x
=
f
k
−
1
(
y
)
x=f_k^{-1}(y)
x=fk−1(y)不可行
3.已知k的情况下，计算x可行
即存在一些控制量来决定这个函数的逆能否被计算出来
如果
m
i
m_i
mi两两互素，并且有
N
=
m
1
m
2
.
.
.
m
r
,
N
=
m
i
M
i
N=m_1m_2...m_r, N=m_iM_i
N=m1m2...mr,N=miMi
则同余方程组
x
≡
b
i
(
m
o
d
m
i
)
x \equiv b_i(mod m_i)
x≡bi(modmi)
有唯一解
x
≡
∑
M
i
M
i
′
b
i
x\equiv \sum M_iM_i'b_i
x≡∑MiMi′bi
其中
M
i
′
是
M
i
在
m
i
下
的
逆
元
M_i'是M_i在m_i下的逆元
Mi′是Mi在mi下的逆元
注意到中国剩余定理要求两两互素，对于两两不互素的情况
比如
a
n
s
≡
3
m
o
d
4
,
a
n
s
≡
5
m
o
d
6
ans\equiv3mod4, ans\equiv5mod6
ans≡3mod4,ans≡5mod6
则有
a
n
s
=
4
k
1
+
3
,
a
n
s
=
6
k
2
+
5
ans=4k_1+3,ans=6k_2+5
ans=4k1+3,ans=6k2+5
4
k
1
+
3
=
6
k
2
+
5
4k_1+3=6k_2+5
4k1+3=6k2+5
2
k
1
−
3
k
2
=
1
2k_1-3k_2=1
2k1−3k2=1
观察得到特解为
k
1
=
2
,
k
2
=
1
k_1=2,k_2=1
k1=2,k2=1
希望得到ans的通解，因为是一次，则两个k增长的速度都是1次的
令
k
1
=
2
+
q
t
,
k
2
=
1
+
p
t
令k_1=2+qt, k_2=1+pt
令k1=2+qt,k2=1+pt
求得
2
p
=
3
q
2p=3q
2p=3q
则通解为
k
1
=
2
+
3
t
,
k
2
=
1
+
2
t
k_1=2+3t,k_2=1+2t
k1=2+3t,k2=1+2t
代入
a
n
s
=
4
k
1
+
3
=
11
+
12
t
ans=4k_1+3=11+12t
ans=4k1+3=11+12t
因此两个方程同时满足的x满足同余
x
≡
11
m
o
d
12
x\equiv11mod12
x≡11mod12
更多的式子可以类似的合并
记
ϕ
(
x
)
为
和
1
−
x
中
和
x
互
素
的
数
的
个
数
,
x
素
因
子
分
解
为
∏
p
i
a
i
记\phi(x)为和1-x中和x互素的数的个数,x素因子分解为\prod p_i^{a_i}
记ϕ(x)为和1−x中和x互素的数的个数,x素因子分解为∏piai
则有
ϕ
(
x
)
=
∏
p
i
a
i
(
1
−
1
/
p
)
=
x
∏
(
1
−
1
/
p
)
\phi(x)=\prod p^{a_i}_i(1-1/p)=x\prod(1-1/p)
ϕ(x)=∏piai(1−1/p)=x∏(1−1/p)
Euler定理：若a和n互素，
a
ϕ
(
n
)
≡
1
m
o
d
n
a^{\phi (n)}\equiv 1 modn
aϕ(n)≡1modn
推论：
n
=
p
q
,
p
≠
q
n=pq,p\neq q
n=pq,p=q且pq为素数，k是任意整数，则有
m
k
(
p
−
1
)
(
q
−
1
)
+
1
≡
m
m
o
d
n
m^{k(p-1)(q-1)+1}\equiv m modn
mk(p−1)(q−1)+1≡mmodn对任意0<=m<=n成立
a
p
−
1
≡
1
m
o
d
p
a^{p-1}\equiv1modp
ap−1≡1modp
可以作为欧拉定理的推论
1.大整数分解算法
2.背包算法
3.离散对数问题
G是阶为p的有限循环群，g是生成元。
y
=
g
x
m
o
d
p
y=g^x modp
y=gxmodp，则称x是群G上元素y关于生成元g的离散对数。
离散对数难题：
1.已知g,x,p求解y容易
2.一直y,g,p，求解x困难
算法安全性依赖解离散对数的难度
算法：
一般的背包算法是NP的，有两类背包问题，其中公钥使用难解的背包问题，私钥使用易解的背包问题
其中简单背包的特征是，背包物品从重到轻排列后，每一个背包都大于所有小于他的背包的和。显然这个背包易解。
算法：
选择一个
m
>
∑
a
i
m>\sum a_i
m>∑ai,选择一个和
n
n
n互素的整数w，令
a
i
′
=
w
a
i
(
m
o
d
m
)
a_i'=wa_i(modm)
ai′=wai(modm)，就可以把私钥转化成公钥
将明文按比特位转化成背包重量W并发送。解密时要先求出对应的私钥背包的重量，即
W
−
1
=
W
∗
w
−
1
（
m
o
d
m
）
W^{-1}=W*w^{-1}（modm）
W−1=W∗w−1（modm）再解简单背包问题，就可以得到明文
利用euler定理的推论，将N=pq视作单项陷门函数，陷门参数为pq。
算法：
分组大小为k
公开密钥为{e,n},
n
=
p
q
n=pq
n=pq
e
与
(
p
−
1
)
(
q
−
1
)
互
素
e与(p-1)(q-1)互素
e与(p−1)(q−1)互素
私有密钥为{d,p,q}
d
=
e
−
1
(
m
o
d
(
p
−
1
)
(
q
−
1
)
)
,
e
d
=
1
+
k
(
p
−
1
)
(
q
−
1
)
d=e^{-1}(mod(p-1)(q-1)),ed=1+k(p-1)(q-1)
d=e−1(mod(p−1)(q−1)),ed=1+k(p−1)(q−1)
加密
c
=
m
e
m
o
d
n
c=m^e modn
c=memodn
解密
m
=
c
d
m
o
d
n
m=c^d modn
m=cdmodn
思想就是通过幂运算进行加密，希望公钥私钥共同作用之后产生 m t = m m o d n m^t=mmodn mt=mmodn的效果，因此可以通过euler定理构造 t = k ( p − 1 ) ( q − 1 ) + 1 t=k(p-1)(q-1)+1 t=k(p−1)(q−1)+1，从而推出私钥公钥互相为对方(p-1)(q-1)的逆元
RSA的签名方式，将用自己的私钥加密一个数m，验证签名时，用公钥解密，并验证是否和m相同，从而验证是否是用私钥签名了的。从而签名可以抗抵赖。
对RSA的攻击方法主要是基于签名的协议攻击，因此不要用RSA随意对别人的文件签名。
同时p,q应该尽可能长度相等且大，让攻击者没法直接整数分解出pq，e,d不应该太小，e太小会导致离散对数可解，在不同模数相同e的已知明文攻击中可被攻破，d太小可能会被针对解密密钥的强力攻击破解。
依赖有限域上计算离散对数的难度
密钥：选择一个素数p，整数模p的一个原根g，随机选择x，g和x都小于p，计算
y
=
g
x
m
o
d
p
y=g^xmodp
y=gxmodp
公钥是y,g,p
密钥是x
算法：
加密：随机选择随机数k，明文为M，计算
a
=
g
k
m
o
d
p
a=g^kmodp
a=gkmodp
b
=
y
k
M
m
o
d
p
b=y^kM modp
b=ykMmodp
(
a
,
b
)
作
为
密
文
(a,b)作为密文
(a,b)作为密文
解密：
M
=
b
/
a
x
m
o
d
p
M=b/a^xmodp
M=b/axmodp
a
x
≡
g
k
x
m
o
d
p
,
b
/
a
x
≡
y
k
M
/
a
x
≡
g
x
k
M
/
g
x
k
≡
M
m
o
d
p
a^x\equiv g^{kx}modp,b/a^x\equiv y^kM/a^x\equiv g^{xk}M/g^{xk}\equiv Mmodp
ax≡gkxmodp,b/ax≡ykM/ax≡gxkM/gxk≡Mmodp
作为一个公钥算法，这里显然是不能直接用y来加密了…否则攻击者直接求y关于p的逆元就可以了。因此引入一个k，用y^k加密，那么此时因为k是随便选的，需要一个额外的信息来标注这个k，所以引入了a。因此很容易就可以得到解密的步骤。
要用不同的k加密信息，如果是相同的k，密文为
(
a
1
,
b
1
)
(
a
2
,
b
2
)
(a_1,b_1)(a_2,b_2)
(a1,b1)(a2,b2)
则
b
1
/
b
2
=
m
1
/
m
2
b_1/b_2=m_1/m_2
b1/b2=m1/m2，则
m
1
m_1
m1已知时
m
2
m_2
m2很容易计算