![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
#author("2023-10-05T03:02:18+09:00","","") [[ExcelEx]] * 公開鍵暗号を使った暗号化と復号 [#t4471e0c] ** A small RSA encoding and decoding by Excel without using a VBA macro. Takashi Yamanoue, Fukuyama University. [#jaf943cd] - 送信者、受信者の間の通信が第三者から観測されても、その通信の内容がその第三者にわからないように、暗号化したいことがあります。たとえば、パスワードや、クレジットカード番号や、個人情報などを送受信するとき、それが第３者に知れてしまうと、財産や、ときには生命が危険にさらされる可能性があります。 - 送信側では、元の文である「平文」を「暗号化」し、それによって得られた暗号を受信者に送ります。 - 受信側では、暗号を受け取り「復号」して、元の平文を取り出します。 - 暗号化するとき「共通鍵」暗号方式が使われることがあります。これは、送受信者共に、同じ「共通鍵」という情報を使って、暗号化と復号を行う方法です。 - 共通鍵暗号で通信するとき、その通信を始める前に、どのようにして、相手に鍵を送るか？という問題が発生する場合があります。たとえば、電話で鍵を伝えた場合、その通話内容が盗聴されると、第三者に通信の内容が漏えいしてしまう可能性が発生します。 - この問題を解決する方法の一つに、「公開鍵暗号」方式を使った暗号化と復号の方法があります。 - 公開鍵暗号では、暗号を受信する側が、「公開鍵」と「秘密鍵」のペアを作成し、公開鍵を公開し、秘密鍵は外部には秘密にしておきます。 - 送信者は、受信者が公開した公開鍵を使って平文を暗号化し、生成された暗号を受信者に送信します。 - 受信者は、秘密鍵を使って暗号文を復号し、平文に戻します。公開鍵で暗号化された平文は、そのペアである秘密鍵を使わないと復号できない（復号が非常に困難な）ようになっています。 - このため、共通鍵方式のように、鍵の配送に頭を悩ます必要がなくなります。 - 公開鍵暗号方式の代表的なものが、RSA公開鍵暗号です。 * RSA 公開鍵暗号 [#z00310f1] - RSA公開鍵暗号方式の計算を表計算で行います。 ** RSA 公開鍵暗号は、以下の式を計算して、暗号化、復号を行います。 [#mea01220] *** 公開鍵と秘密鍵の生成 [#s9995f77] - 公開鍵<n, e>, 秘密鍵<n,d>(n,e,dは整数)を以下のように計算します。 -- n = p*q (p,q は異なる素数) -- L=lcm(p-1, q-1) -- e は L とは互いに素である数で、Lより小さな数。 -- d は、1=ed (mod L) となる数。 *** 暗号化 [#g516894f] -- M は平文で、1 <M < n -- C は暗号文 -- <n, e> は公開鍵 -- <n, d> は秘密鍵 -- 暗号化: C=(M^e)(mod n) *** 復号 [#d456d0d3] -- 復号: M=(C^d)(mod n) ** 計算表の実際 [#a693a766] - p,q, e, M を与えることで、上の、暗号化、復号、公開鍵、秘密鍵を計算します。 -- 暗号化と復号を行うとき、上の式をそのまま使うと、小さなM,C, e, d でも、非常に大きな数の余りを計算することになって、現実的ではありません&br; （Windows の電卓だと、結構、大きな桁数の計算を行うことはできます）。 -- 実際の暗号化で使われているような大きなM,C,e,d は使えませ んが、授業でやってみることができるような桁数(3桁程度)までの計算を行うことができる表を作っています。 -- 表を vlookup で検索することにより、計算を行っています。 -- マクロは使いません。 * 画面キャプチャ [#v858e3e2] ** 鍵ペアの生成と、暗号化と復号の例(シート「鍵生成」) [#bec574f4] - &ref(RSA/public-key-3-key.jpg,75%); *** 主要なセルの計算式 [#pf8600b6] - 公開鍵、秘密鍵の計算 -- B7 (n=p*q) =B5*B6 -- B9 (=lcm(p-1,q-1)) =LCM((B5-1),(B6-1)) -- B12 (... Lとeが互いに素であることの確認) =GCD(B10,B9) -- B14 (1=ed (mod L) であるような dを検索) =VLOOKUP(1,A20:B228,2,FALSE) -- A20 (d を見つけるための, ed (mod L)の計算) =MOD(B$10*B20,B$9) -- B20 (d を1から並べる) 1 -- A21 以降の A* (A20のコピー) -- B21 =B20+1 -- B22 以降の B* (B21のコピー) - 暗号化 -- G9 (暗号化の式, C=M^e(mod n)) =VLOOKUP(B10,F20:G161,2,FALSE) - 暗号化で使う表 -- F20 ... e を1から並べる 1 -- F21 =F20+1 -- F22 以降は、F21をコピー -- G20 ... e が 1のときの、M^e (mod n)=M (mod n) =MOD(G$6,$B$7) -- G21 ... e が 2のときの M^e (mod n)= M*(M^ (e-1)(mod n)) (mod n) =MOD(G$6*G20,$B$7) -- G22 以降は G21をコピー - 復号 -- L9 (暗号化の式, M=C^d(mod n)) =VLOOKUP(B14,K20:L177,2) - 復号で使う表 -- K20 ... d を1から並べる 1 -- K21 =K20+1 -- K22 以降は、F21をコピー -- L20 ... d が 1のときの、C^d (mod n)=C (mod n) =MOD(L$6,$B$7) -- L21 ... d が 2のときの C^d (mod n)= M*(M^ (d-1)(mod n)) (mod n) =MOD(L$6*L20,$B$7) -- L22 以降は L21をコピー ---- ** 上の鍵ペアを使った、短い文の暗号化と復号の例(シート「暗号化・復号例」) [#za5e67b2] - &ref(RSA/public-key-3-endecode.jpg,75%); *** 主要なセルの計算式 [#pf8600b6] - B5...M5 : 下の行(B6...M6)に並んでいる文字の、左から数えたときの番号 -- B5 1 -- C5 =B5+1 -- D5から右は, C5をコピー - B6... M6 : 入力された平文, 1つのセルに１文字。 - B7...M7 : B6 ... M6 の文字をASCIIコードで表したときの数 -- B7 =CODE(B6) -- C7から右は, B6をコピー - B8... M8 : 各文字が暗号化された結果が格納されている場所 -- B8 ="'code-"&B5&"'!B7" -- C8から右は, B8をコピー - B9 ... M9 : 上の場所にある暗号化された結果を表示 -- B9 =INDIRECT(B8) -- C9から右は, B9をコピー - B11... M11 : 暗号化された平文を復号した結果が格納されている場所 -- B11 ="'code-"&B5&"'!G7" -- C8から右は, B8をコピー - B12 ... M12 : 上の場所にある復号された結果を表示 -- B12 =INDIRECT(B11) -- C12から右は, B12をコピー ** 上の暗号化と復号の例で利用する、x番目の文字の暗号化と復号のためのシート 「code-x (x=1,...,)」 [#u2e78147] - &ref(RSA/public-key-3-c-1.jpg,75%); - code-1, code-2, ... 内のすべての式は同じです。code-1 を作って、それを、code-2, code-3, ... にコピーしているだけです。 *** 主要なセルの計算式 [#pf8600b6] - K4: このシート名を取得 =RIGHT(CELL("filename",A2),LEN(CELL("filename",A2))-FIND("]",CELL("filename",A2))) - K5: code-x の xを取り出す。 =MID(K4,6,LEN(K4)-5) - K7: このシートが暗号化・復号を担当する文字がある場所 ="暗号化・復号例!"&CHAR(CODE("A")+K5)&"7" - K8: 取り出した文字 =INDIRECT(K7) ---- ** Excelの表 [#v6f4170f] - &ref(public-key-3.xlsx); ---- * 参考文献 [#b6ecf9cd] - NHK 笑わない数学 #9 暗号理論, 数学ノート, https://www.nhk.jp/p/ts/Y5R676NK92/blog/bl/pmg0p5PX8L/bp/pXAL4oAb7l/ - サルにもわかるRSA暗号, http://www.maitou.gr.jp/rsa/rsa10.php - 公開鍵暗号-RSA-基礎 <暗号楽しいです, http://elliptic-shiho.hatenablog.com/entry/2015/11/12/182219 - RSA暗号体験入門（第３章）, 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 - Excel でプログラムを書く, http://lecture.ecc.u-tokyo.ac.jp/~shagiya/excel.pdf ---- #counter
