5.11

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

设明文为\(m\),密文为\(c\),公钥为\((n,b)\),私钥为\((n,a)\),则

\[ \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} \]

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

所以只需证

\[ m^{ab} \equiv m \pmod n \]

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

\[ \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^{\lambda(n)} \equiv 1 \pmod q \]

因为\(n = pq\),故

\[ m^{\lambda(n)} \equiv 1 \pmod n \]

对上式进行变换可得

\[ \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)\)已知\(p=37\)\(q=79\)\(b=7\)

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

   

  当\(ab \equiv 1 \pmod{\lambda(n)}\)\(a\)\(b\)\(n\)意义下的逆元且$ {} (n,a) = 1$

  则.

\[ a = 67 \]

   

  当\(ab \equiv 1 \pmod{\varphi(n)}\)\(a\)\(b\)\(n\)意义下的逆元且$ {} (n,a) = 1$

  则.

\[ a = 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

\(n_1 = 18923,b_1=1261\)

\(n_2 = 31313,b_2 = 4913\)

http://factordb.com/分解\(n_1\)得到\(p=127,q=149\)

分解\(n_2\)得到\(p=173,q=181\)

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

通过扩展欧几里得算法求逆元得到私钥\(a_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,\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)\)

\(\rm Sig\). 对于消息\(x\),选择一个秘密随机数\(k \in {\Bbb Z}^*_{p-1}\),计算 \[ \gamma = \alpha ^ k \mod p, {\,\,\,\,}\delta = (x-k\gamma)a^{-1} \mod{(p-1)} \]

定义签名为 \[ {\rm Sig}_{\cal K}(x,r) = (\gamma, \delta) \]

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

\[ {\rm Vrfy}_{\cal K}(x,(\gamma,\delta)) = 1 \iff \beta^{\delta}\gamma^{\gamma} \equiv \alpha^{x} \mod p \]

\((b)\)

\(\rm Sig.\)

\[ \delta = (x-a\gamma)k^{-1} \mod{(p-1)} \]

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

\((c)\)

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

\[ \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过程如下

\({\rm KeyGen}\). 设\(p\)是长为\(L\)bit的素数,在\({\Bbb Z}^*_p\)上其离散对数问题是难解的,其中\(L \equiv 0 \pmod{64}\)\(512 \leq L \leq 1024\)\(q\)是能被\(p-1\)整除的\(160\)bit的素数,设\(\alpha \in {\Bbb Z}^*_p\)\(1\)\(p\)\(q\)次根。定义

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

其中\(0 \leq b \leq q - 1\)\(p,q,\alpha,\beta\)是公钥,\(b\)是私钥

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

\[ \begin{aligned} \gamma = (\alpha ^ r \mod{p}) \mod{q}\\ \delta = ({\rm SHA-1}(x)+b\gamma)r^{-1} \mod{q} \end{aligned} \]

定义签名为

\[ {\rm Sig}_{\cal K}(x,r) = (\gamma, \delta) \]

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

\[ \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,\alpha=170,a=75,\beta=4567,k=49,{\rm SHA-1}(x)=52\)

计算得到\(k^{-1} = 33, \gamma = 59,\delta = 79\)

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

验证过程如下:

  计算\(\delta^{-1} = 78\)\(e_1 = 16\)\(e_2 = 57\)

  \((\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(·)\)\(\rm HASH\)函数,\((p,q,\alpha,\beta)\)是公钥,\(a\)是私钥,\(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} \]

如果两个签名的随机数\(r\)相同,我们可以分别记两次的\(\gamma\)值和\(\delta\)值,即\(\gamma_1,\gamma_2\)\(\delta_1,\delta_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\)值,即\(\delta_1,\delta_2\).

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

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

定义\((p,q,\alpha,\beta)\)是公钥,\(a\)是私钥

\[ \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椭圆曲线签名方案

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

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

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

\[ \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)\)

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

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

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

其中\(0 \leq m \leq q - 1\)\(p,q,E,A,B\)是公钥,\(m\)是私钥

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

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

定义签名为

\[ {\rm Sig}_{\cal K}(x,k)=(r,s) \] (如果\(r=0\)或者\(s=0\),应该为\(k\)另选一个随机数)

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

\[ \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 = 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)\)\(k = 75, {\rm SHA-1(x)} = 10\)

\[ \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)\)

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

\[ \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 = 88\),即

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