RSA のバックアップの現在との差分(No.3)

追加された行はこの色です。
削除された行はこの色です。
[[MenuBar]]
[[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 公開鍵暗号は、以下の式を計算して、暗号化、復号を行います。
** 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} は秘密鍵
-- <n, e> は公開鍵
-- <n, d> は秘密鍵
-- 暗号化: C=(M^e)(mod n)
*** 復号 [#d456d0d3]
-- 復号: 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 を与えることで、上の、暗号化、復号、公開鍵、秘密鍵を計算します。
** 計算表の実際 [#a693a766]
- p,q, e, 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)
----
* 画面キャプチャ [#v858e3e2]
** 鍵ペアの生成と、暗号化と復号の例(シート「鍵生成」) [#bec574f4]
- &ref(RSA/public-key-3-key.jpg,75%);
*** 主要なセルの計算式 [#pf8600b6]
- 公開鍵、秘密鍵の計算
-- B12 (n=q*1)
 =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から並べる)
-- 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
-- A24 以降の A* (A23のコピー)
-- B24 
 =B23+1
-- B25 以降の B* (B24のコピー)
----
-- A21 以降の A* (A20のコピー)
-- B21 
 =B20+1
-- B22 以降の B* (B21のコピー)
- 暗号化
-- G9 (暗号化の式, C=M^e(mod n))
 =VLOOKUP(B10,F20:G161,2,FALSE)
- 暗号化で使う表
-- F23 ... e を1から並べる
-- F20 ... 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をコピー

----
-- 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)
- 復号で使う表
-- K23 ... d を1から並べる
-- K20 ... 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をコピー

-- 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をコピー
----

- 復号
-- G4 ... C ... 復号するときの元の暗号文
 =B7
-- G7 (復号の式, M=C^d (mod n), 表の検索)
 =VLOOKUP(B18,K23:L180,2)
** 上の鍵ペアを使った、短い文の暗号化と復号の例(シート「暗号化・復号例」) [#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-2.xlsx);

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