第五章一般習題

pages 140 - 142

5.1.1. 密文 5859 乃是 RSA 演算法加密而成，其公開鑰匙為
n=11413, e=7647 使用分解式 11413= 101x113，試求其明文。

n = 11413; e = 7647; 
    d = PowerMod[e, -1, EulerPhi[n]];
c = 5859; m = PowerMod[c, d, n]

5.1.9. 多人同時使用 RSA 系統時，必須避免採用同一個加密次冪 e
(a) 假設有三位使用者。若這三個人所使用的 RSA 之模 n_1, n_2 及 n_3 兩兩互質，但所使用的加密次冪都是 e=3。假設同一信息傳遞給他們當中的每一個人而且你截獲這些密文，請問你怎麼破解此一系統？
(b) 兩兩互質 RSA 模 2469247531693, 11111502225583, 44444222221411, 對應的密文是 359335245251, 10436363975495, 5135984059593 都使用 e= 3 加密而成，找出原信息。

<< NumberTheory`NumberTheoryFunctions`
n1 = 2469247531693; n2 = 11111502225583; 
    n3 = 44444222221411;
c1 = 359335245251; c2 = 10436363975495; c3 = 5135984059593;

y = 
        ChineseRemainderTheorem[{c1, c2, c3}, {n1, n2, 
            n3}];
Solve[x^3 == y, x][[1]]

PowerMod[805121215, 3, {n1, n2, n3}] == {c1, c2, c3}

abc = " abcdefghijklmnopqrstuvwxyz";
\(\(no = "000102030405060708091011121314151617181920212223242526";\)\)
digitalize = 
        Table[StringTake[abc, {i}] -> 
            StringTake[no, {2*i - 1, 2*i}], {i, 1, 27}];
alphabetize = 
        Table[StringTake[no, {2*i - 1, 2*i}] -> 
            StringTake[abc, {i}], {i, 1, 27}];
A[digit_] := StringReplace[digit, alphabetize];

A["0805121215"]

5.1.11. 假設三毛使用 RSA 演算法如下。她從一個含幾個字母的信息開始，並指定 a=1,b=2,..., z=26。接著她將每一個字母分別加密。譬如說,若她的信息是cat, 那麼她就計算 3^e mod{n}, 1^e mod{n} 及20^e mod{n}。然後她將加密好的信息傳送給四郎。請解釋為何不需分解 n 五爺就可找出原信息。假設 n=8881 且 e=13, 五爺截取得信息 4461 794  2015  2015  3603。在不分解 n 之下，請找出原信息。

n = 8881; e = 13; 
    c = {4461, 794, 2015, 2015, 3603};
t = Table[PowerMod[i, e, n], {i, 26}]
mf = 
        Table[Position[t, c[[j]]], {j, Length[c]}] // 
          Flatten;
md = 
      Table[If[mf[[i]] < 10, "0" <> ToString[mf[[i]]], 
          ToString[mf[[i]]]], {i, Length[mf]}]

A[md] // StringJoin

5.1.15. 令 p=7919,q=17389 且令 e=66909025。計算顯示 e^2\equiv 1 mod{(p-1)(q-1)}。三毛決定用公鑰為 (n=pq,e) 的 RSA 演算法將信息 12345 加密。因為她希望有非常安全的加密等級，所以就用同一公鑰再加密一次(亦即將原信息雙重加密)。請問她送出之最後的密文為何？驗證之，但不要使用任何計算器。

p = 7919; q = 17389; n = p*q; e = 66909025;
PowerMod[e, 2, (p - 1) (q - 1)]
PowerMod[12345, e, n]
PowerMod[%, e, n]

Exit[]

第五章電腦習題

pages 143 - 144

5.2.1. Paul Revere的朋友在M.I.T.的鐘塔對他說：如果今夜英國人從城裏經海上或陸路向我們進攻，我就在鐘塔拱門上掛起燈籠作信號燈---若經由陸路，掛一盞即傳送信息one; 若經由海上，掛兩盞即傳送信息two。我在對岸會作好準備，騎馬傳播警報聲。因為他們知道RSA密碼系統將會在波士頓地區被發明，所以他們決定應該用
RSA 演算法來加密，其中 n=712446816787 而 e=6551。保羅裏維爾接到的密文為 273095689186。請問原來的明文為何？

n = 712446816787; e = 6551; 
    c = 273095689186;
d = PowerMod[e, -1, EulerPhi[n]];
m = PowerMod[c, d, n]

abc = " abcdefghijklmnopqrstuvwxyz";
\(\(no = "000102030405060708091011121314151617181920212223242526";\)\)
digitalize = 
        Table[StringTake[abc, {i}] -> 
            StringTake[no, {2*i - 1, 2*i}], {i, 1, 27}];
alphabetize = 
        Table[StringTake[no, {2*i - 1, 2*i}] -> 
            StringTake[abc, {i}], {i, 1, 27}];
A[digit_] := StringReplace[digit, alphabetize];

A[ToString[m]]

5.2.2  在RSA中知n=718548065973745507, e=3449, d=543546506135745129, 分解 n。

n = 718548065973745507; a = 2;
e = 3449; d = 543546506135745129;
{GCD[n, a], Table[GCD[d*e - 1, 2^j], {j, 1, 10}]}

k = 5; m = (d*e - 1)/2^k; 
    b[0] = PowerMod[a, m, n];
b[j_] := PowerMod[b[j - 1], 2, n];
Table[b[j], {j, 0, k - 1}]

{p1 = GCD[b[2] - 1, n], p2 = n/p1}

5.2.3. 選取兩個30位數的質數p與q及加密次冪e。請將下列信息加密：
cat, bat, hat, encyclopedia, antidisestablishmentarianism
(a) 觀看密文，你能看出前三個明文信息只有一個字的差異嗎？
(b) 觀看密文，你能看出後兩個明文信息遠比前三個來得長嗎？

p = 1621363683730794830562206941193;
q = 6808408721789606173485310148771;
e = 6551; n = p*q;

Qd[plaintext_] := 
        ToExpression[StringReplace[plaintext, digitalize]];

m1 = Qd["cat"]; m2 = Qd["bat"]; m3 = Qd["hat"]; 
    m4 = Qd["encyclopedia"]; 
    m5 = Qd["antidisestablishmentarianism"];
c1 = PowerMod[m1, e, n]; c2 = PowerMod[m2, e, n]; 
    c3 = PowerMod[m3, e, n]; c4 = PowerMod[m4, e, n]; 
    c5 = PowerMod[m5, e, n];

{c1, c2, c3, c4, c5}

5.2.4. 利用 p-1 演算法來分解 618240007109027021。

n = 618240007109027021; a = 2; b[1] = a;
b[j_] := PowerMod[b[j - 1], j, n];
Table[GCD[b[j] - 1, n], {j, 20, 25}]

{p1 = GCD[b[23] - 1, n], p2 = n/p1}

5.2.5. n=537069139875071。知85975324443166^2=462436106261^2 mod{n},分解n。

n = 537069139875071; x = 85975324443166; 
    y = 462436106261;
{Mod[x + y, n] == 0, Mod[x - y, n] == 0, 
      PowerMod[x, 2, n] == PowerMod[y, 2, n]}

{p1 = GCD[x - y, n], p2 = n/p1}

5.2.6. 令 n=84047x65497。 x , y 滿足 x^2\equiv y^2 但 x\not \equiv \pm y mod{n}。

p = 84047; q = 65497; n = p*q

{x = (p + q)/2, y = (p - q)/2}

PowerMod[x, 2, n] == PowerMod[y, 2, n]

5.2.7 (a) \(設你知33335\^2\)=(670705093^2) mod 670726081。用此分解670726081。
(b) 設你知 (3^2)=(670726078^2) mod 670726081。為何無法用此來分解 670726081？

xa = 670705093; ya = 33335; n = 670726081;
PowerMod[xa, 2, n] == PowerMod[ya, 2, n]

{p1 = GCD[xa - ya, n], p2 = n/p1}

xb = 670726078; yb = 3; n = 670726081;
PowerMod[xb, 2, n] == PowerMod[yb, 2, n]

{p1 = GCD[xb - yb, n], p2 = n/p1}

{Mod[xb + yb, n] == 0, Mod[xb - yb, n] == 0}

5.2.8. \(TraditionalForm\`你知2\^958230\)=1488665 \(TraditionalForm\`及2\^1916460\)=1 mod 3837523。
如何利用此來分解3837523？注意到指數1916460為另一指數958230的兩倍。

n = 3837523; x = 1488665; y = 1;
{Mod[x + y, n] == 0, 
      Mod[x - y, n] == 0, 
PowerMod[x, 2, n] == 
        PowerMod[y, 2, n]}

{p1 = GCD[x - y, n], p2 = n/p1}

5.2.9a 在RSA演算法中所用的p與q其距離不能太近，否則危險重重。
假設在RSA演算法中所用的p與q為連續質數，那麼你如何分解 n=pq？

5.2.9b 密文10787770728是利用n=10993522499, e=113 所加密而成。已知n的因子p與q為連續奇數。試破解之。

n = 10993522499; c = 10787770728; e = 113; 
    p = Floor[Sqrt[n]]

{PrimeQ[p], q = n/p}

d = 
        PowerMod[
          e, -1, (p - 1) (q - 1)];
m = PowerMod[c, d, n]

A["0" <> ToString[m]]

5.2.9c 下列密文c是在模n之下使用e所加密而成：n=152415787501905985701881832150835089037858868621211004433,e=9007,c=141077461765569500241199505617854673388398574333341423525。已知n的因子p與q為連續質數。試破解之。

n = 
        152415787501905985701881832150835089037858868621211004433;
e = 9007;
c = 141077461765569500241199505617854673388398574333341423525; 
    f = Floor[Sqrt[n]]

L = 
        Table[If[PrimeQ[f - j] == True, 1, 0], {j, 1, 
            59}];
p = f - Position[L, Max[L]][[1]][[1]]

L = 
        Table[If[PrimeQ[f + j] == True, 1, 0], {j, 1, 
            59}];
q = f + Position[L, Max[L]][[1]][[1]]

n == p*q

d = 
        PowerMod[
          e, -1, (p - 1) (q - 1)];
m = PowerMod[c, d, n]

A[ToString[m]]

5.2.10 令p=123456791,q=987654323,e=127, m=14152019010605127。
(a) 計算 m^e mod{p} 與 m^e mod{q}, 用孫子定理將其合併得到密文 c=m^e mod{pq}。
(b) 改變 m^e mod{p} 當中的一個數(這可能是某種幅射所造成)。現在將此值與m^e mod{q} 合併得到一個m^e mod{pq}的錯誤值 f。計算gcd(c-f,pq)。為何可分解pq？使用(a)之法來算m^e mod{pq}  是挺有魅力，因為不要求像直接在模pq 所需較大的多倍精密度運算。然而，如(b)部分所說，如果攻擊者造成一位元偶發性的錯誤，則 pq 可被分解。

p = 123456791; q = 987654323; e = 127; 
    m = 14152019010605127;

PowerMod[m, e, {p, q}]

<< NumberTheory`NumberTheoryFunctions`

c = ChineseRemainderTheorem[PowerMod[m, e, {p, q}], {p, q}]

c == PowerMod[m, e, p*q]

f = ChineseRemainderTheorem[{23161231, 925665447}, {p, q}]

GCD[c - f, p*q]

5.2.11 假設 p=76543692179, q=343434343453且 e=457。密文 c=m^e mod{pq} 在傳送的時候產生一錯誤，收到的密文是 2304329328016936947195。收方有辦法決定所收到的數字無誤，但最後一位數不見了。請找出來此失蹤的數並破解此密文。

p = 76543692179;  q = 343434343453; n = p*q;
e = 457; w = 2304329328016936947195; 
    d = PowerMod[
        e, -1, (p - 1) (q - 1)];
pos = Table[PowerMod[10*w + j, d, n], {j, 0, 9}]

m = pos[[3]]; c = PowerMod[m, e, n]

j = c - 10  w

A[ToString[m]]

5.2.12 用a=2透過密勒-瑞班法來檢驗38200901201是否為質數。然後再用a=3檢驗。注意：第一個檢驗說38200901201可能是質數，但第二個檢驗卻說是合成數。像這樣子的合成數就稱之為底2的一個強擬質數。

Exit[]

n = 38200901201; Table[GCD[n - 1, 2^i], {i, 10}]

k = 4; m = (n - 1)/2^4;

a = 2; b[0] = PowerMod[a, m, n];
b[i_] := PowerMod[b[i - 1], 2, n]; 
    Table[b[i], {i, 0, k - 1}]

a = 3; b[0] = PowerMod[a, m, n];
b[i_] := PowerMod[b[i - 1], 2, n]; 
    Table[b[i], {i, 0, k - 1}]