[[MenuBar]] * RSA 公開鍵暗号 [#z00310f1] - RSA公開鍵暗号方式の計算を表計算で行います。 - RSA 公開鍵暗号は、以下の式を計算して、暗号化、復号を行います。 -- M は平文で、1 <M < n -- C は暗号文 -- {n, e} は公開鍵 -- {n, d} は秘密鍵 -- 暗号化: C=(M^e)(mod n) -- 復号: M=(C^d)(mod n) -- n = p*q (p,q は異なる素数) -- L=lcm(p-1, q-1) -- e は L とは互いに素である数で、Lより小さな数。 -- d は、1=ed (mod L) となる数。 - p,q, M を与えることで、上の、暗号化、復号、公開鍵、秘密鍵を計算します。 -- 暗号化と復号を行うとき、上の式をそのまま使うと、小さなM,C, e, d でも、非常に大きな数の余りを計算することになって、現実的ではありません&br; (Windows の電卓だと、結構、大きな桁数の計算を行うことはできます)。 -- 実際の暗号化で使われているような大きなM,C,e,d は使えませ んが、授業でやってみることができるような桁数(3桁程度)までの計算を行うことができる表を作っています。 -- 表を vlookup で検索することにより、計算を行っています。 -- マクロは使いません。 * 計算表の実際 [#a693a766] ** 画面キャプチャ [#v858e3e2] - &ref(RSA/public-key-2.jpg,75%); ---- ** 主要なセルの計算式 [#pf8600b6] ---- - 暗号化 -- B7 (暗号化の式, C=M^e(mod n)) =VLOOKUP(B15,F23:G164,2,FALSE) ---- - 公開鍵、秘密鍵の計算 -- B12 (n=p*q) =B10*B11 -- B14 (=lcm(p-1,q-1)) =LCM((B10-1),(B11-1)) -- B17 (... Lとeが互いに素であることの確認) =GCD(B15,B14) -- B18 (1=ed (mod L) であるような dを検索) =VLOOKUP(1,A23:B231,2,FALSE) -- A23 (d を見つけるための, ed (mod L)の計算) =MOD(B$15*B23,B$14) -- B23 (d を1から並べる) 1 -- A24 以降の A* (A23のコピー) -- B24 =B23+1 -- B25 以降の B* (B24のコピー) ---- - 暗号化で使う表 -- F23 ... e を1から並べる 1 -- F24 =F23+1 -- F25 以降は、F24をコピー -- G23 ... e が 1のときの、M^e (mod n)=M (mod n) =MOD(B$4,$B$12) -- G24 ... e が 2のときの M^e (mod n)= M*(M^ (e-1)(mod n)) (mod n) =MOD(B$4*G23,$B$12) -- G25 以降は G24をコピー ---- - 復号で使う表 -- K23 ... d を1から並べる 1 -- K24 =K23+1 -- K25 以降は、K24をコピー -- L23 ... d が 1のときの、C^d (mod n)=C (mod n) =MOD(G$4,$B$12) -- L24 ... d が 2のときの C^d (mod n)= C*(C^(d-1)(mod n)) (mod n) =MOD(G$4*L23,$B$12) -- L25 以降は L24をコピー ---- - 復号 -- G4 ... C ... 復号するときの元の暗号文 =B7 -- G7 (復号の式, M=C^d (mod n), 表の検索) =VLOOKUP(B18,K23:L180,2) ---- * Excelの表 [#v6f4170f] - &ref(public-key-2.xlsx); ---- * 参考文献 [#b6ecf9cd] - RSA暗号体験入門(第3章), http://www.cybersyndrome.net/rsa/rsa3.html - はやわかり RSA , http://www.mew.org/~kazu/doc/rsa.html - RSA暗号の例, http://www.ss.cs.tut.ac.jp/umemura/RSA-lecture-ppt.pdf ---- #counter