第五章         分解因數與公鑰密碼系統

RSA 演算法

王荊公：看似平常最奇絕，成如容易卻艱難。

pages 115 - 121

例題01

p = 336998653; q = 951871033; n = p*q

e = 83089;

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}];
Q[plaintext_] := StringReplace[plaintext, digitalize];
Qd[plaintext_] := ToExpression[Q[plaintext]];
A[digit_] := StringReplace[digit, alphabetize];

won = "wonderfulweekend"; s = StringLength[won]; 
    w = Q[won]

m = ToExpression[{StringTake[w, s], StringTake[w, -s]}]

c = PowerMod[m, e, n]

d = PowerMod[e, -1, EulerPhi[n]]

PowerMod[c, d, n]

PowerMod[c, d, n] == m

例題02

n = 851; phin = 792; 
    Roots[x^2 - (n - phin + 1) x + n == 0, x]

例題03

n = 11313771275590312567; phin = 11313771187608744400;
Roots[x^2 - (n - phin + 1) x + n == 0, x]

質數檢驗與分解因數

pages 123 - 130

例題05

n = 561; k = 4; m = 35; a = 2; 
    b[0] = PowerMod[a, m, n];
b[j_] := PowerMod[b[j - 1], 2, n]; Table[b[j], {j, 0, 3}]

GCD[b[2] - 1, n]

x = 10. ^100; {Log[x], x/Log[x]}

例題09

n = 320779255950718549; a = 5; e = 83089; 
    d = 138212005402570609;
{GCD[n, a], Table[GCD[d*e - 1, 2^j], {j, 1, 10}]}

k = 8; 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}

例題10

n = 
      114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541;  
    a = 2;
r = 
        961034419617782266156919023359583834109854129051878330250644604041155985575087352659156174898557342995131594680431086921245830097664;
{ GCD[n, a], Table[GCD[r, 2^j], {j, 1, 10}]}

k = 8; m = r/2^k; b[0] = PowerMod[a, m, n];
b[j_] := PowerMod[b[j - 1], 2, n]; 
    Table[b[j], {j, 0, k - 1}]

{p3 = GCD[b[2] - 1, n], p4 = n/p3}

例題11

n = 8834884587090814646372459890377418962766907; a = 2; 
    b[1] = a;
{b[j_] := PowerMod[b[j - 1], j, n]; p5 = GCD[b[75] - 1, n], 
      p6 = n/p5}

二次篩法

n = 3837523; 
    FactorInteger[PowerMod[{9398, 19095, 1964, 17078}, 2, n]] // 
      ColumnForm

pd = Mod[{9398*19095*1964*17078, 2^4*3^2*5^3*11*13^2*19}, n]

{Mod[pd[[1]] + pd[[2]], n] == 0, 
      Mod[pd[[1]] - pd[[2]], n] == 0}

{n1 = GCD[pd[[1]] - pd[[2]], n], n2 = n/n1}

FactorInteger[PowerMod[{8077, 3397, 14262}, 2, n]] // 
      ColumnForm

{a = Mod[{9398*8077*3397, 2^3*5^3*13*19}, n], 
      Mod[a[[1]] + a[[2]], n] == 0, 
      Mod[a[[1]] - a[[2]], n] == 0}

{b = Mod[{9398*19095*1964*17078, 2^4*3^2*5^3*11*13^2*19}, n], 
      GCD[b[[1]] - b[[2]], n]}

{c = Mod[{1964*14262, 3*5*7*13^2}, n], 
      GCD[c[[1]] - c[[2]], n]}

RSA 挑戰

n = 
        114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541;
e = 9007;
c = 
        96869613754622061477140922254355882905759991124574319874695120930816298225145708356931476622883989628013391990551829945157815154;

s = 
        16717861150380844246015271389168398245436901032358311217835038446929062655448792237114490509578608655662496577974840004057020373;

p = 
        3490529510847650949147849619903898133417764638493387843990820577;
q = 
        32769132993266709549961988190834461413177642967992942539798288533;

d = PowerMod[e, -1, (p - 1)*(q - 1)]

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]]

PowerMod[s, e, n]

\(A["06091819200019151222051800230914190015140500082114041805040004151212011819"]\)