RSA密码体系:

RSA密码体系是一种依赖于依赖于大数质因数分解的难解性的密码体系.

RSA加密算法:

参与者:

私钥持有者Alice
公钥持有者Bob

运行步骤:

Alice选取两个大质数$p,q$(需要使用Miller-Rabin算法判定其是否为质数),计算$n=pq$,其欧拉函数$\phi(n)=(p-1)(q-1)$
Alice选取大质数$e\in(\max(p,q),\phi(n))$,这保证了$gcd(e,\phi(n))=1$
Alice(使用扩展欧几里得算法或欧拉定理)计算出$d$,使得$d\cdot e = k \cdot n+1$,其中$k$是任意的整数,这意味着,$d=e^{-1} \mod n$
Alice将$pk=(n,e)$作为公钥发送给Bob,将$sk=(p,q,d)$作为私钥自己保留
若Bob要给Alice发送信息(明文)$m$,用以下加密(encryption)算法将其加密为密文$c$:$$c=Enc(pk,m)=m^e \mod n$$
Alice收到密文$c$后,用以下解密(decryption)算法还原出明文$m$:$$Dec(sk,c)=c^d \mod n$$.

正确性:

至于为什么$c^d=m \mod n$,证明要根据密文$m$是否与模数$n$互质,考虑如下两种情况:

当$m,n$互质时,

$$ \begin{aligned} c^d = & m^{ed} \\ = & m^{k\phi(n)+1} \qquad \text{($k$为整数,由于第3步的构造)} \\ = & m \cdot (m^{\phi(n)})^k \\ = & m \cdot (1)^k \mod n \qquad \text{(欧拉定理)}\\ = & m \end{aligned} $$

当$m,n$不互质时,欧拉定理失效,由于$n=pq$,因此$m$要么是$p$的倍数,要么是$q$的倍数

不妨记$m=kp$,$k$为整数,且$m,q$互质(否则$m$会是$q$的倍数,同时是$p,q$的倍数,就是$n$的倍数,此时证明是显然的),那么,此时可应用以$q$为模数的欧拉定理

$$\begin{aligned} x^{q-1}=& 1 \mod q \\ x^{k(p-1)(q-1)} = & 1 \mod q \qquad \text{(等式两端同时做$k(p-1)$次方)} \\ x^{k(p-1)(q-1)} = & iq + 1 \text{(将同余式改写成恒等式)} \end{aligned}$$

重新观察解密过程

$$ \begin{aligned} c^d = & m^{ed} \\ = & m^{k\phi(n)+1} \qquad \text{($k$为整数,由于第3步的构造)} \\ = & m \cdot m^{k(p-1)(q-1)} \\ = & (iq+1)m \qquad (x^{k(p-1)(q-1)} = iq + 1) \\ = & mq+m \\ = & kpq+m \qquad (m=kp) \\ = &m \mod n \end{aligned} $$

综上,

$$c^d = m \mod n$$

安全性:

Alice的私钥$sk=(p,q,d)$不会上传到网络上,因此理论上无法被攻击者截获,攻击者若截获了加密消息$c$,同时已知公开信息$pk=(n,e)$时,由于大整数分解质因数问题的难解性,攻击者很难知道$n=pq$中的$p,q$到底是多少,也就不知道$e=d^{-1} \mod (p-1)(q-1)$是多少.

代码:

def divi(a): #分解质因数
    i=2
    ans=[]
    while(i*i<a):
        while(a%i==0):
            ans.append(i)
            a=a//i
        i=i+1
    if(a>1):
        ans.append(a)
    return ans

def gcd(a,b): #辗转相除法
    if(b == 0):
        return a
    else:
        return gcd(b,a%b)
    
def exgcd(a,b): #扩展欧几里得算法
    if(b == 0):
        x = 1
        y = 0
        return a,x,y
    ans,t,x = exgcd(b,a%b)
    y = t-a//b*x
    return ans,x,y

def qpow(base,exp,mod): #快速幂
    ans = 1
    while(exp>0):
        if(exp%2 == 1):
            ans = ans*base%mod
        exp = exp//2
        base = base*base%mod
    return ans

def rev(a,mod,type ='not_prime'):
    if(type =='prime'): #费马小定理求逆元
        return qpow(a,mod-2,mod)
    else: #辗转相除法求逆元
        g,x,y = exgcd(a,mod)
        if(g!= 1):
            return -1 #逆元不存在
        else:
            return (x+mod)%mod

p = 97
q = 103 #实际上这两个大整数是随机生成并通过Miller-Rabin算法判定的
print("Gen()->pk,sk")
print('p =',p,end=' = ')
print(*divi(p),sep='*')
print('q =',q,end=' = ')
print(*divi(q),sep='*')
g,x,y = exgcd(p,q)
n = p*q
print('n = pq =',n)
φ = (p-1)*(q-1)
print('φ = (p-1)(q-1) =',φ)
e = 197
print('e =',e,'\ngcd(z,e) =',gcd(φ,e))
d = rev(e,φ,type ='not_prime')
print('''d = e^{-1}(mod φ) =''',d)
print('pk:(n =',n,',e =',e,')')
print('sk:(n =',n,',d =',d,')')

print('\n')
print("Enc(pk,m)->c")
m = 114
print('m =',m)
c = qpow(m,e,n)
print('''c = m^e mod n =''',c)

print('\n')
print('Dec(c,sk)->m')
m1 = qpow(c,d,n)
print('''m = c^d mod n =''',m1)

运行结果:

Gen()->pk,sk
p = 97 = 97
q = 103 = 103
e = 197
gcd(z,e) = 1
d = e^{-1}(mod φ) = 845
pk:(n = 9991 ,e = 197 )
sk:(n = 9991 ,d = 845 )


Enc(pk,m)->c
m = 114
c = m^e mod n = 7731


Dec(c,sk)->m
m = c^d mod n = 114

RSA数字签名算法:

RSA密码体系还可以用于数字签名.

参与者:

私钥持有者Alice
公钥持有者Bob

运行步骤:

Alice选取两个大质数$p,q$(需要使用Miller-Rabin算法判定其是否为质数),计算$n=pq$,其欧拉函数$\phi(n)=(p-1)(q-1)$
Alice选取大质数$e\in(\max(p,q),\phi(n))$,这保证了$gcd(e,\phi(n))=1$
Alice(使用扩展欧几里得算法或欧拉定理)计算出$d$,使得$d\cdot e = k \cdot n+1$,其中$k$是任意的整数,这意味着,$d=e^{-1} \mod n$
Alice将$pk=(n,e)$作为公钥发送给Bob,将$sk=(p,q,d)$作为私钥自己保留
若Alice要对一段信息$m$进行签名,用以下签名(signature)算法为其签名$s$:$$s=Sign(sk,m)=m^d \mod n$$
Bob收到$(m,s)$后,用以下验证(verify)算法验算签名是否有效$$Ver(pk,m,s): s^e==m? 1 : 0$$.

正确性:

同上,略.

安全性:

同上,攻击者要伪造签名,就需要在仅知道公钥$pk=(n,e)$的情况下,计算出$d=e^{-1} \mod (p-1)(q-1)$,需要进行分解质因数$n=pq$,这在计算复杂度上是不可行的.

代码:

def divi(a): #分解质因数
    i=2
    ans=[]
    while(i*i<a):
        while(a%i==0):
            ans.append(i)
            a=a//i
        i=i+1
    if(a>1):
        ans.append(a)
    return ans

def gcd(a,b): #辗转相除法
    if(b == 0):
        return a
    else:
        return gcd(b,a%b)
    
def exgcd(a,b): #扩展欧几里得算法
    if(b == 0):
        x = 1
        y = 0
        return a,x,y
    ans,t,x = exgcd(b,a%b)
    y = t-a//b*x
    return ans,x,y

def qpow(base,exp,mod): #快速幂
    ans = 1
    while(exp>0):
        if(exp%2 == 1):
            ans = ans*base%mod
        exp = exp//2
        base = base*base%mod
    return ans

def rev(a,mod,type ='not_prime'):
    if(type =='prime'): #费马小定理求逆元
        return qpow(a,mod-2,mod)
    else: #辗转相除法求逆元
        g,x,y = exgcd(a,mod)
        if(g!= 1):
            return -1 #逆元不存在
        else:
            return (x+mod)%mod

p = 97
q = 103 #实际上这两个大整数是随机生成并通过Miller-Rabin算法判定的
print("Gen()->pk,sk")
print('p =',p,end=' = ')
print(*divi(p),sep='*')
print('q =',q,end=' = ')
print(*divi(q),sep='*')
g,x,y = exgcd(p,q)
n = p*q
print('n = pq =',n)
φ = (p-1)*(q-1)
print('φ = (p-1)(q-1) =',φ)
e = 197
print('e =',e,'\ngcd(z,e) =',gcd(φ,e))
d = rev(e,φ,type ='not_prime')
print('''d = e^{-1}(mod φ) =''',d)
print('pk:(n =',n,',e =',e,')')
print('sk:(n =',n,',d =',d,')')

print('\n')
print("Sign(sk,m)->s")
m = 114
print('m =',m)
s = qpow(m,e,n)
print('''s = m^e mod n =''',s)

print('\n')
print('''Ver(pk,s,m)->{Valid,Invalid}''')
m1 = qpow(s,d,n)
print('''s^d mod n =''',m1)
if (m1==m):
    print("Valid")
else:
    print("Invalid")

运行结果:

Gen()->pk,sk
p = 97 = 97
q = 103 = 103
n = pq = 9991
φ = (p-1)(q-1) = 9792
e = 197
gcd(z,e) = 1
d = e^{-1}(mod φ) = 845
pk:(n = 9991 ,e = 197 )
sk:(n = 9991 ,d = 845 )


Sign(sk,m)->s
m = 114
s = m^e mod n = 7731


Ver(pk,s,m)->{1,0}
s^d mod n = 114
Valid

离散对数密码体系(ElGamal):

ElGamal密码体系是一种利用离散对数难解性问题的密码体系

ElGamal加密算法:

参与者:

私钥持有者Alice
公钥持有者Bob

运行步骤:

Alice选取大质数$p$,整数$g\in[0,p-1]$,整数$\alpha \in [0,p-2]$,计算$\beta=g^{\alpha} \mod p$
Alice将$pk=(p,g,\beta)$作为公钥发送给Bob,将$sk=(p,\alpha)$作为私钥自己保留
若Bob要给Alice发送信息(明文)$m$,需要先随机生成一个$k\in[0,p-1]$,然后用以下加密(encryption)算法将其加密为密文$c$:$$c=Enc(pk,m,k)=(r,s)$$其中$r=g^k \mod p$, $s=m\beta^k \mod p$
Alice收到密文$c=(r,s)$后,用以下解密(decryption)算法还原出明文$m$:$$Dec(sk,c)=s(r^{\alpha})^{-1} \mod n$$.

正确性:

$$\begin{aligned}
sr^{-\alpha}=&m\beta^k \cdot (g^k)^{-\alpha} \qquad (\text{加密过程},r=g^k \mod p, s=m\beta^k \mod p)\\
=&m \cdot (g^{\alpha})^k \cdot (g^k)^{-\alpha} \qquad (\text{密钥生成过程},\beta=g^{\alpha}\mod p)\\
=&m\cdot g^{\alpha k}\cdot g^{-\alpha k}\\
=&m
\end{aligned}$$

安全性:

攻击者在截获密文$c=(r,s)$,并已知公钥$pk=(p,g,\beta)$时,要还原密文,就需要知道$\alpha$是多少,这就需要在已知$p,g,\beta$的情况下求解$$\beta=g^{\alpha} \mod p$$中的$\alpha$是多少,该等式可记为如下等价形式$$\alpha=\log_g\beta \mod p$$称为离散对数问题,这在计算复杂度上是难以求解的.

代码:

import time #用于生成随机数
def divi(a): #分解质因数
    i=2
    ans=[]
    while(i*i<a):
        while(a%i==0):
            ans.append(i)
            a=a//i
        i=i+1
    if(a>1):
        ans.append(a)
    return ans

def gcd(a,b): #辗转相除法
    if(b == 0):
        return a
    else:
        return gcd(b,a%b)
    
def exgcd(a,b): #扩展欧几里得算法
    if(b == 0):
        x = 1
        y = 0
        return a,x,y
    ans,t,x = exgcd(b,a%b)
    y = t-a//b*x
    return ans,x,y

def qpow(base,exp,mod): #快速幂
    ans = 1
    while(exp>0):
        if(exp%2 == 1):
            ans = ans*base%mod
        exp = exp//2
        base = base*base%mod
    return ans

def rev(a,mod,type ='not_prime'):
    if(type =='prime'): #费马小定理求逆元
        return qpow(a,mod-2,mod)
    else: #辗转相除法求逆元
        g,x,y = exgcd(a,mod)
        if(g!= 1):
            return -1 #逆元不存在
        else:
            return (x+mod)%mod


print("Gen()->pk,sk")
p=97
print('p =',p,end=' = ')
print(*divi(p),sep='*')
g=5
print('g =',g,', g in [0,p-1]')
α=8
print('α =',α,', α in [0,p-2]')
β=qpow(g,α,p)
print('''β = g^α mod p =''',β)
print('pk:(p =',p,',g =',g,',β =',β,')')
print('sk:(p =',p,',α =',α,')')

print('\n')
print("Enc(pk,m)->c")
m = 66
print('m =',m)
k=int(time.time())%(p-1)
print('随机生成 k in [0,p-2], k =',k)
r=qpow(g,k,p)
s=m*qpow(β,k,p) % p
print('r=g^k mod p =',r)
print('s= m*β^k mod p =',s)
print('c=(r,s)')

print('\n')
print("Dec(sk,c)->m")
m1=s*rev(qpow(r,α,p),p,type='prime')%p
print('''m=s*(r^α)^{-1} mod p =''',m1)

运行结果:

Gen()->pk,sk
p = 97 = 97
g = 5 , g in [0,p-1]
α = 8 , α in [0,p-2]
β = g^α mod p = 6
pk:(p = 97 ,g = 5 ,β = 6 )
sk:(p = 97 ,α = 8 )


Enc(pk,m)->c
m = 66
随机生成 k in [0,p-2], k = 3
r=g^k mod p = 28
s= m*β^k mod p = 94
c=(r,s)


Dec(sk,c)->m
m=s*(r^α)^{-1} mod p = 66

ElGamal数字签名算法:

参与者:

私钥持有者Alice
公钥持有者Bob

运行步骤:

Alice选取大质数$p$,,整数$g\in[0,p-1]$,整数$\alpha \in [0,p-2]$,计算$\beta=g^{\alpha} \mod p$
Alice将$pk=(p,g,β)$作为公钥发送给Bob,将$sk=(p,α)$作为私钥自己保留
若Alice要对一段信息$m$进行签名,首先生成一个与$p-1$互质的随机数$k\in[0,p-2]$,然后用以下签名(signature)算法为其签名$sig$:$$sig=Sign(sk,m,k)=(r,s)$$ 其中 $$r=g^k \mod p$$ $$s=(m-\alpha r) k^{-1} \mod (p-1)$$
Bob收到$(m,sig)$后,用以下验证(verify)算法验算签名是否有效$$Ver(pk,m,sig): \beta^r r^s==g^m? 1 : 0$$.

正确性:

$$\begin{aligned}
\beta^rr^s=&(g^{\alpha})^r(g^k)^s\\
=&g^{\alpha r} g^{k (m-r\alpha)k^{-1}} \qquad (\text{由签名过程,}s=(m-\alpha r)k^{-1})\\
=&g^{\alpha r+(m-\alpha r)}\\
=&g^m
\end{aligned}$$

安全性:

同上,攻击者若要伪造签名,就需要就需要知道$\alpha$是多少,就要求解离散对数问题$\alpha=\log_g\beta \mod p$.

代码:

import time #用于生成随机数
def divi(a): #分解质因数
    i=2
    ans=[]
    while(i*i<a):
        while(a%i==0):
            ans.append(i)
            a=a//i
        i=i+1
    if(a>1):
        ans.append(a)
    return ans

def gcd(a,b): #辗转相除法
    if(b == 0):
        return a
    else:
        return gcd(b,a%b)
    
def exgcd(a,b): #扩展欧几里得算法
    if(b == 0):
        x = 1
        y = 0
        return a,x,y
    ans,t,x = exgcd(b,a%b)
    y = t-a//b*x
    return ans,x,y

def qpow(base,exp,mod): #快速幂
    ans = 1
    while(exp>0):
        if(exp%2 == 1):
            ans = ans*base%mod
        exp = exp//2
        base = base*base%mod
    return ans

def rev(a,mod,type ='not_prime'):
    if(type =='prime'): #费马小定理求逆元
        return qpow(a,mod-2,mod)
    else: #辗转相除法求逆元
        g,x,y = exgcd(a,mod)
        if(g!= 1):
            return -1 #逆元不存在
        else:
            return (x+mod)%mod


print("Gen()->pk,sk")
p=97
print('p =',p,end=' = ')
print(*divi(p),sep='*')
g=5
print('g =',g,', g in [0,p-1]')
α=8
print('α =',α,', α in [0,p-2]')
β=qpow(g,α,p)
print('''β = g^α mod p =''',β)
print('pk:(p =',p,',g =',g,',β =',β,')')
print('sk:(p =',p,',α =',α,')')

print('\n')
print("Sign(pk,m)->c")
m = 66
print('m =',m)
k=0
while(gcd(k,p-1)!=1):
    k=int(time.time()*1000)%(p-1)
print('随机生成与(p-1)互质的 k in [0,p-2], k =',k,'gcd(p-1,k) =',gcd(p-1,k))
r=qpow(g,k,p)
print('r=g^k mod p =',r)
s=(m-r*α)*rev(k,p-1,type='not_prime')%(p-1)
print('''s= (m-ra)k^{-1} mod (p-1) =''',s)
print('sig=(r,s)')

print('\n')
print('''Ver(pk,sig)->{0,1}''')
m1=qpow(β,r,p)*qpow(r,s,p)%p
m2=qpow(g,m,p)

print('''β^r·r^s mod p =''',m1)
print('''g^m mod p =''',m2)
if (m1==m2):
    print("Valid")
else:
    print("Invalid")

运行结果:

Gen()->pk,sk
p = 97 = 97
g = 5 , g in [0,p-1]
α = 8 , α in [0,p-2]
β = g^α mod p = 6
pk:(p = 97 ,g = 5 ,β = 6 )
sk:(p = 97 ,α = 8 )


Sign(pk,m)->c
m = 66
随机生成与(p-1)互质的 k in [0,p-2], k = 41 gcd(p-1,k) = 1
r=g^k mod p = 80
s= (m-ra)k^{-1} mod (p-1) = 82
sig=(r,s)


Ver(pk,sig)->{0,1}
β^r·r^s mod p = 70
g^m mod p = 70
Valid