# 5.11

(a)(a) 若修改后的RSA\rm RSA 密码体制的加密解密仍然互逆.

设明文为mm,密文为cc,公钥为(n,b)(n,b),私钥为(n,a)(n,a),则

cmb(modn)mca(modn)cb(mb)amabmab%λ(n)(modn)\begin{aligned} c \equiv m^b & \pmod n\\ m \equiv c ^a & \pmod n\\ c ^ b \equiv (m^b)^a \equiv m^{ab} \equiv m^{ab \% \lambda(n)} & \pmod n \end{aligned}

因为ab1(modλ(n))ab \equiv 1 \pmod{\lambda(n)},则ab%λ(n)=1ab \% \lambda(n) = 1,故上式是可逆的.

所以只需证

mabm(modn)m^{ab} \equiv m \pmod n

已知λ(n)=(p1)(q1)gcd(p1,q1)\lambda(n) = \frac {(p-1)(q-1)} { {\rm gcd} (p-1,q-1)},且ab \equiv 1 \pmod

mλ(n)m(p1)(q1)gcd(p1,q1)(modp)mλ(n)(mp1)q1gcd(p1,q1)(modp)由费马小定理可知,mλ(n)(1)q1gcd(p1,q1)(modp)mλ(n)1(modp)\begin{aligned} m^{\lambda(n)} & \equiv m^{\frac{(p-1)(q-1)}{ {\rm gcd} (p-1,q-1)}} \pmod p \\ m^{\lambda(n)} & \equiv (m^{p-1})^{\frac{q-1}{ {\rm gcd} (p-1,q-1)}} \pmod p \\ 由费马小定理可知, m^{\lambda(n)} & \equiv (1)^{\frac{q-1}{ {\rm gcd}(p-1,q-1)}} \pmod p \\ \Rightarrow m^{\lambda(n)} & \equiv 1 \pmod p \\ \end{aligned}

同理可证

mλ(n)1(modq)m^{\lambda(n)} \equiv 1 \pmod q

因为n=pqn = pq,故

mλ(n)1(modn)m^{\lambda(n)} \equiv 1 \pmod n

对上式进行变换可得

mkλ(n)1(modn)mkλ(n)+1m(modn)mabm(modn)\begin{aligned} m^{k \lambda(n)} & \equiv 1 \pmod n \\ m^{k \lambda(n) + 1} & \equiv m \pmod n \\ \iff m^{ab} & \equiv m \pmod n \end{aligned}

(b)(b) 已知p=37p=37q=79q=79b=7b=7

n=pq=2923n = pq = 2923λ(n)=(p1)(q1)gcd(p1,q1)=468\lambda(n) = \frac{(p-1)(q-1)}{ {\rm gcd} (p-1,q-1)} = 468φ(n)=(p1)(q1)=2808\varphi(n) = (p-1)(q-1) = 2808


ab1(modλ(n))ab \equiv 1 \pmod{\lambda(n)}aabbnn 意义下的逆元且 $ {\rm gcd} (n,a) = 1$

则.

a=67a = 67


ab1(modφ(n))ab \equiv 1 \pmod{\varphi(n)}aabbnn 意义下的逆元且 $ {\rm gcd} (n,a) = 1$

则.

a=2407a = 2407

扩展欧几里得求乘法逆元代码

#include <cstdio>
#include <cstdlib>
using namespace std;
void exgcd(int a, int b, int &x, int &y) {
    if(!b) {
        x = 1;
        y = 0;
        return ;
    }
    else {
        exgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }
}
int inv(int a, int n) {
    int x, y;
    exgcd(a, n, x, y);
    return (x + n) % n;
}
int main() {
    printf("%d\n", inv(7, 468));
    printf("%d\n", inv(7, 2808));
}

# 5.12

n1=18923b1=1261n_1 = 18923,b_1=1261

n2=31313b2=4913n_2 = 31313,b_2 = 4913

http://factordb.com/ 分解n1n_1 得到p=127,q=149p=127,q=149

分解n2n_2 得到p=173,q=181p=173,q=181

通过计算得到φ(n)1=(p1)(q1)=18648\varphi(n)_1 = (p-1)(q-1) = 18648φ(n)2=(p1)(q1)=30960\varphi(n)_2 = (p-1)(q-1) = 30960

通过扩展欧几里得算法求逆元得到私钥a1=5797a2=6497a_1 = 5797,a_2 = 6497

求明文代码如下

from ctypes.wintypes import CHAR
def transform(num):
    pos2 = 0
    pos1 = 0
    pos0 = 0
    while num != 0:
        if num >= (26 ** 2):
            pos2 = num // (26 ** 2)
            num = num % (26 ** 2)
        elif num >= 26:
            pos1 = num // 26
            num = num % 26
        else:
            pos0 = num
            num = 0
    return [pos2 % 26, pos1 % 26, pos0 % 26]
list1 = []
list2 = []
CHAR_TABLE = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
n1 = 18923
a1 = 5797
n2 = 31313
a2 = 6497
with open("./cipher1.txt", "r", encoding="utf-8") as f:
    for line in f.readlines():
        line = line.strip("\n")
        list1.append(line)
    f.close()
with open("./cipher2.txt", "r", encoding="utf-8") as f:
    for line in f.readlines():
        line = line.strip("\n")
        list2.append(line)
    f.close()
plaintext1 = ""
plaintext2 = ""
for item in list1:
    temp_digit = pow(int(item), a1, n1)
    temp = transform(temp_digit)
    temp_str = CHAR_TABLE[temp[0]] + CHAR_TABLE[temp[1]] + CHAR_TABLE[temp[2]]
    plaintext1 += temp_str
for item in list2:
    temp_digit = pow(int(item), a2, n2)
    temp = transform(temp_digit)
    temp_str = CHAR_TABLE[temp[0]] + CHAR_TABLE[temp[1]] + CHAR_TABLE[temp[2]]
    plaintext2 += temp_str
print(plaintext1)
print("")
print(plaintext2)

表一对应明文:

IBECAMEINVOLVEDINANARGUMENTABOUTMODERNPAINTINGASUBJECTUPONWHICHIAMSPECTACULARLYILLINFORMEDHOWEVETEPNYOFMYFRIENDSCANBECOMEHEATEDANDEVENVIOLENTONTHESUBJECTANDIENJOYTHEIRWRANGLESINAMODESTWAYIAMANARTISTMYSELFANDIHAVESOMESYMPATHYWITHTHEABSTRACTIONISTSALTHOUGHIAUTEGONEBEYONDTHEMINMYOWNAPPROACHTOARTIAMALUMPISTTWOORTHREEDECADESAGOITWASQUITEFASHIONABLETOBEACUBISTANDTODRAWEVERYTHINGINCUBESTHENTHEREWASAREVOLTBYTHEVORTICISTSWHODREWEVERYTHINGINWHIRLSWENOWHAVETHEABSTRACTIONISTSWHOPAINTEVERYTHINGINAVERYABSTRACTEDMANNERBUTMYOWNSMALLWORKSDONEONMYTELEPHONEPADARECOMPOSEDOFCAREFULLYSHADEDSTRANGELYSHAPEDLUMPSWITHTRACESOFCUBISMVORTICISMANDABSTRACTIONISMINTHEMFORTHOSEWHOPOSSESSTHESEEINGEYEASALUMPISTISTANDALONE

表二对应明文:

LAKEWOBEGONISMOSTLYPOORSANDYSOILANDEVERYSPRINGTHEEARTHHEAVESUPANEWCROPOFROCKSPILESOFROCKSTENFEETHIGHINTHECORNERSOFFIELDSPICKEDBYGENERATIONSOFUSMONUMENTSTOOURINDUSTRYOURANCESTORSCHOSETHEPLACETIREDFROMTHEIRLONGJOURNEYSADFORHAVINGLEFTTHEMOTHERLANDBEHINDANDTHISPLACEREMINDEDTHEMOFTHERESOTHEYSETTLEDHEREFORGETTINGTHATTHEYHADLEFTTHEREBECAUSETHELANDWASNTSOGOODSOTHENEWLIFETURNEDOUTTOBEALOTLIKETHEOLDEXCEPTTHEWINTERSAREWORSEZ

# 6.9

p=31847,α=5,a=7899,β=18074p=31847,\alpha=5,a=7899,\beta=18074

代码如下:

p = 31847
alpha = 5
a = 7899
beta = 18074
CHAR_TABLE = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
CIPHER_TABLE = []
with open("./cipher1.txt", "r", encoding="utf-8") as f:
    for line in f.readlines():
        line = line.replace("(", "")
        line = line.replace(")", "")
        line = line.replace(",", " ")
        line = line.strip("\n").split(" ")
        CIPHER_TABLE.append(line)
    f.close()
def exgcd(a, b):
    if b == 0:
        x = 1
        y = 0
        return x, y
    x1, y1 = exgcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return x, y
def inv(a, n):
    x, y = exgcd(a, n)
    return (x + n) % n
def transform(num):
    pos2 = 0
    pos1 = 0
    pos0 = 0
    while num != 0:
        if num >= (26 ** 2):
            pos2 = num // (26 ** 2)
            num = num % (26 ** 2)
        elif num >= 26:
            pos1 = num // 26
            num = num % 26
        else:
            pos0 = num
            num = 0
    return [pos2 % 26, pos1 % 26, pos0 % 26]
plaintext = ""
for item in CIPHER_TABLE:
    m = (int(item[1]) * inv(pow(int(item[0]), a, p), p)) % p
    temp = transform(m)
    temp_str = CHAR_TABLE[temp[0]] + CHAR_TABLE[temp[1]] + CHAR_TABLE[temp[2]]
    plaintext += temp_str
print(plaintext)

解密出的明文为:

SHESTANDSUPINTHEGARDENWHERESHEHASBEENWORKINGANDLOOKSINTOTHEDISTANCESHEHASSENSEDACHANGEINTHEWEATHERTHEREISANOTHERGUSTOFWINDABUCKLEOFNOISEINTHEAIRANDTHETALLCYPRESSESSWAYSHETURNSANDMOVESUPHILLTOWARDSTHEHOUSECLIMBINGOVERALOWWALLFEELINGTHEFIRSTDROPSOFRAINONHERBAREARMSSHECROSSESTHELOGGIAANDQUICKLYENTERSTHEHOUSE

# 6.12

转换成三进制后用快速幂计算可得

GALOISFIELD

# 7.6

(a)(a)

Sig\rm Sig. 对于消息xx,选择一个秘密随机数kZp1k \in {\Bbb Z}^*_{p-1},计算

γ=αkmodp,δ=(xkγ)a1mod(p1)\gamma = \alpha ^ k \mod p, {\,\,\,\,}\delta = (x-k\gamma)a^{-1} \mod{(p-1)}

定义签名为

SigK(x,r)=(γ,δ){\rm Sig}_{\cal K}(x,r) = (\gamma, \delta)

Vrfy.\rm Vrfy. 对于消息xx 和给定签名SigK(γ,δ){\rm Sig}_{\cal K}(\gamma, \delta)

VrfyK(x,(γ,δ))=1βδγγαxmodp{\rm Vrfy}_{\cal K}(x,(\gamma,\delta)) = 1 \iff \beta^{\delta}\gamma^{\gamma} \equiv \alpha^{x} \mod p

(b)(b)

Sig.\rm Sig.

δ=(xaγ)k1mod(p1)\delta = (x-a\gamma)k^{-1} \mod{(p-1)}

在多次签名过程中,可以减少随机数的逆元计算

(c)(c)

若随机数kk 泄露,且gcd(γ,p1)=1\gcd(\gamma, p-1) = 1,则很容易计算出私钥aa

βδγγαaδαkγαxmodpb=(xkγ)δ1mod(p1)\begin{aligned} \beta ^ \delta \gamma ^ \gamma \equiv \alpha ^ {a \delta} \alpha ^ {k \gamma} \equiv \alpha ^ x \mod p \\ \Rightarrow b = (x - k\gamma)\delta^{-1} \mod{(p-1)} \end{aligned}

# 7.7

数字签名 DSA 过程如下

KeyGen{\rm KeyGen}. 设pp 是长为LLbit 的素数,在Zp{\Bbb Z}^*_p 上其离散对数问题是难解的,其中L0(mod64)L \equiv 0 \pmod{64}512L1024512 \leq L \leq 1024qq 是能被p1p-1 整除的160160bit 的素数,设αZp\alpha \in {\Bbb Z}^*_p11ppqq 次根。定义

K={(p,q,α,b,β):βαb(modp)}{\cal K} = \left\{(p,q,\alpha,b,\beta): \beta \equiv \alpha ^ b \pmod p \right\}

其中0bq10 \leq b \leq q - 1p,q,α,βp,q,\alpha,\beta 是公钥,bb 是私钥

Sig.{\rm Sig.} 对于消息xxK={(p,q,α,b,β):βαb(modp)}{\cal K} = \left\{(p,q,\alpha,b,\beta): \beta \equiv \alpha ^ b \pmod p \right\} 和一个秘密随机数rZpr \in {\Bbb Z}^*_p1rq11 \leq r \leq q - 1,计算

γ=(αrmodp)modqδ=(SHA1(x)+bγ)r1modq\begin{aligned} \gamma = (\alpha ^ r \mod{p}) \mod{q}\\ \delta = ({\rm SHA-1}(x)+b\gamma)r^{-1} \mod{q} \end{aligned}

定义签名为

SigK(x,r)=(γ,δ){\rm Sig}_{\cal K}(x,r) = (\gamma, \delta)

Vrfy.{\rm Vrfy.}x{0,1},γ,δZqx \in \left\{0,1\right\}^*,\gamma,\delta \in {\Bbb Z_q},验证通过下面计算完成

e1=SHA1(x)δ1modqe2=γδ1modqVrfyK(x,(γ,δ))=1(αe1βe2modp)modq=γ\begin{aligned} e_1 & = {\rm SHA-1}(x)\delta^{-1} \mod{q}\\ e_2 & = \gamma \delta^{-1} \mod{q}\\ {\rm Vrfy}_{\cal K}(x,(\gamma, \delta)) = 1 & \iff (\alpha ^ {e_1} \beta ^ {e_2} \mod{p}) \mod{q} = \gamma \end{aligned}

已知参数为p=7879,q=101,α=170,a=75,β=4567,k=49,SHA1(x)=52p=7879,q=101,\alpha=170,a=75,\beta=4567,k=49,{\rm SHA-1}(x)=52

计算得到k1=33,γ=59,δ=79k^{-1} = 33, \gamma = 59,\delta = 79

则签名为(59,79)(59,79)

验证过程如下:

计算δ1=78\delta^{-1} = 78e1=16e_1 = 16e2=57e_2 = 57

(αe1βe2modp)modq=1776mod101=59=γVrfyK(x,(γ,δ))=1(\alpha ^ {e_1} \beta ^ {e_2} \mod{p}) \mod{q} = 1776 \mod 101 = 59 = \gamma \iff {\rm Vrfy}_{\cal K}(x,(\gamma, \delta)) = 1

# 7.8

# Schnorr 签名方案

在 Schnorr 签名方案中,定义h()h(·)HASH\rm HASH 函数,(p,q,α,β)(p,q,\alpha,\beta) 是公钥,aa 是私钥,rr 为随机数

则签名过程为

γ=h(xαrmodp)δ=r+aγmodqSigK(x,r)=(γ,δ)\begin{aligned} &\gamma = h(x||\alpha^r \mod p)\\ &\delta = r + a\gamma \mod q\\ &{\rm Sig}_{\cal K}(x,r) = (\gamma, \delta) \end{aligned}

如果两个签名的随机数rr 相同,我们可以分别记两次的γ\gamma 值和δ\delta 值,即γ1,γ2\gamma_1,\gamma_2δ1,δ2\delta_1,\delta_2

δ1=r+aγ1modqδ2=r+aγ2modqδ1δ2=a(γ1γ2)a=δ1δ2γ1γ2\begin{aligned} \delta_1 = r + a\gamma_1 \mod q\\ \delta_2 = r + a\gamma_2 \mod q\\ \Rightarrow \delta_1 - \delta_2 = a(\gamma_1 - \gamma_2)\\ \Rightarrow a = \frac{\delta_1 - \delta_2}{\gamma_1 - \gamma_2} \end{aligned}

即可得到私钥

# DSA 签名方案

同 Schnorr 签名方案,我们记两次的δ\delta 值,即δ1,δ2\delta_1,\delta_2.

因为γ=(αkmodp)modq\gamma = (\alpha ^ k \mod p) \mod q,所以两次的γ\gamma 值相同

同时记录A=SHA1(x1),B=SHA1(x2)A = {\rm SHA-1}(x_1), B = {\rm SHA-1}(x_2)

定义(p,q,α,β)(p,q,\alpha,\beta) 是公钥,aa 是私钥

δ1=(A+aγ)k1modqδ2=(B+aγ)k1modqa=δ2Aδ1Bγ(δ1δ2)\begin{aligned} &\delta_1 = (A+a\gamma)k^{-1} \mod q\\ &\delta_2 = (B+a\gamma)k^{-1} \mod q\\ &\Rightarrow a = \frac{\delta_2 A - \delta_1 B}{\gamma(\delta_1 - \delta_2)} \end{aligned}

即可得到私钥

# ECDSA 椭圆曲线签名方案

如果两次的随机数相同,则由随机数kk 得到的kA=(u,v)kA = (u,v) 点是相同的,则r=umodqr = u \mod q 是相同的

记录A=SHA1(x1),B=SHA1(x2)A = {\rm SHA-1}(x_1), B = {\rm SHA-1}(x_2)

定义(p,q,E,A,B)(p,q,E,A,B) 是公钥,mm 是私钥

r1=r2=rs1=(A+mr)k1modqs2=(B+mr)k1modqm=s2As1Br(S1S2)\begin{aligned} &r_1 = r_2 = r\\ &s_1 = (A+mr)k^{-1} \mod q\\ &s_2 = (B+mr)k^{-1} \mod q\\ &\Rightarrow m = \frac{s_2 A - s_1 B}{r(S_1 - S_2)} \end{aligned}

即可得到私钥

值得一提的是,2010 年 PS3 的破解中最离谱的就是因为索尼在使用 ECDSA 签名的时候使用了 4 作为随机数来签所有的文件,导致黑客很容易就破解了 PS3

# 7.13

(a)(a)

椭圆曲线签名算法流程如下

KeyGen.{\rm KeyGen.}pp 是一个大素数,EE 是定义在Fp{\Bbb F}_p 上的椭圆曲线。设AAEE 上阶为qqqq 为素数)的一个点,使得<A><A> 上的离散对数问题是个困难问题。定义:

K={(p,q,E,A,m,B):BmA,mZq}{\cal K} = \left\{(p,q,E,A,m,B):B \equiv mA, m \in {\Bbb Z}_q\right\}

其中0mq10 \leq m \leq q - 1p,q,E,A,Bp,q,E,A,B 是公钥,mm 是私钥

Sig.{\rm Sig.} 对于消息xxK={(p,q,E,A,m,B):BmA,mZq}{\cal K} = \left\{(p,q,E,A,m,B):B \equiv mA, m \in {\Bbb Z}_q\right\} 和一个秘密随机数kZqk \in {\Bbb Z}^*_q1kq11 \leq k \leq q - 1,计算

kA=(u,v)r=umodqs=(SHA1(x)+mr)k1modq\begin{aligned} & kA = (u,v)\\ & r = u \mod{q}\\ & s = ({\rm SHA-1}(x)+mr)k^{-1} \mod{q} \end{aligned}

定义签名为

SigK(x,k)=(r,s){\rm Sig}_{\cal K}(x,k)=(r,s)

(如果r=0r=0 或者s=0s=0,应该为kk 另选一个随机数)

Vrfy.{\rm Vrfy.}x{0,1}r,sZqx \in \left\{0,1\right\}^*r,s \in {\Bbb Z}^*_q,验证过程如下

w=s1modqi=wSHA1(x)modqj=wrmodq(u,v)=iA+jBVrfyK(x,(r,s))=1umodq=r\begin{aligned} w &= s^{-1} \mod{q}\\ i &= w{\rm SHA-1}(x) \mod{q}\\ j &= wr \mod{q}\\ (u,v) &= iA + jB\\ {\rm Vrfy}_{\cal K}(x,(r,s)) & = 1 \iff u \mod{q} = r \end{aligned}

已知参数为a=1,A=(2,6),m=54,p=127a = 1, A = (2, 6), m = 54, p = 127

则公钥计算如下

def exgcd(a, b):
    if b == 0:
        x = 1
        y = 0
        return x, y
    x1, y1 = exgcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return x, y
def inv(a, n):
    x, y = exgcd(a, n)
    return (x + n) % n
def ECDSA_number_multiply(k, a, x, y, p):
    x_1, y_1 = x, y
    x_2, y_2 = x, y
    x_3, y_3 = 0, 0
    quotient = 0
    if k == 1:
        return [x, y]
    for i in range(k - 1):
        if (x_2 == x_1) and (y_2 == y_1):
            quotient = (3 * (x_1 ** 2) + a) * inv(2 * y_1, p) % p
        else:
            quotient = (y_2 - y_1) * inv(x_2 - x_1, p) % p
        x_3 = (quotient ** 2 - x_1 - x_2) % p
        y_3 = (quotient * (x_1 - x_3) - y_1) % p
        x_1, y_1 = x_3, y_3
    return [x_3, y_3]
print(ECDSA_number_multiply(54, 1, 2, 6, 127))

得到公钥B=mA=(24,44)B = mA = (24,44)

(b)(b)k=75,SHA1(x)=10k = 75, {\rm SHA-1(x)} = 10

kA=75(2,6)=(88,55)r=umodq=88mod131=88s=(SHA1(x)+mr)k1modq=(10+54×88)×7mod131=60\begin{aligned} & kA = 75(2,6) =(88,55)\\ & r = u \mod q = 88 \mod 131 = 88\\ & s = ( {\rm SHA-1} (x) + mr)k^{-1} \mod q = (10 + 54 \times 88) \times 7 \mod 131 = 60 \end{aligned}

所以签名为(r,s)=(88,60)(r,s) = (88,60)

(c)(c) 验证过程如下

w=s1modq=107i=wSHA1(x)modq=22j=wrmodq=115(u,v)=iA+jB=(91,18)+(18,62)=(88,55)\begin{aligned} & w = s^{-1} \mod q = 107\\ & i = w {\rm SHA-1} (x) \mod{q} = 22\\ & j = wr \mod q = 115\\ & (u,v) = iA + jB = (91,18) + (18,62) = (88,55) \end{aligned}

计算得到u=88u = 88,即

VrfyK(x,(r,s))=1umodq=r=88{\rm Vrfy}_{\cal K}(x,(r,s)) = 1 \iff u \mod{q} = r = 88