RSA のバックアップ(No.2) - PukiWiki

[ トップ ] [ 新規 | 一覧 | 単語検索 | 最終更新 | ヘルプ ]

RSA 公開鍵暗号 †

RSA公開鍵暗号方式の計算を表計算で行います。
RSA 公開鍵暗号は、以下の式を計算して、暗号化、復号を行います。
- M は平文で、1 <M < n-1
- 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 でも、非常に大きな数の余りを計算することになって、現実的ではありません
  （Windows の電卓だと、結構、大きな桁数の計算を行うことはできます）。
- 実際の暗号化で使われているような大きなM,C,e,d は使えませんが、授業でやってみることができるような桁数(3桁程度)までの計算を行うことができる表を作っています。
- 表を vlookup で検索することにより、計算を行っています。
- マクロは使いません。

計算表の実際 †

画面キャプチャ †

主要なセルの計算式 †

暗号化
- B7 (暗号化の式, C=M^e(mod n))
```
=VLOOKUP(B15,F23:G164,2,FALSE)
```

公開鍵、秘密鍵の計算
- 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から並べる)
```
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 ... e が 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の表 †

public-key-2.xlsx

参考文献 †

RSA暗号体験入門（第３章）, http://www.cybersyndrome.net/rsa/rsa3.html
はやわかり RSA , http://www.mew.org/~kazu/doc/rsa.html

Counter: 4315, today: 1, yesterday: 0