Top / どのように暗号化するか?
HTML convert time: 0.027 sec.

どのように暗号化するか?

Last-modified: 2015-03-26 (木) 21:41:47

RSA暗号化アルゴリズムの仕組み

暗号化と復号化

紙とペンとGoogleを用意してください。

命題:3という数字を暗号化、復号化する。

①素数×素数の積の決定
本来は莫大な素数と素数の積を使って暗号化するのですが、Googleや電卓では数値が莫大すぎて計算してくれないので、77という素数と素数の積(11×7)を使って暗号化するものとします。

②暗号化の際に必要とするべき乗する数の決定
まず、3という数字をべき乗する数を決めます。
べき乗する数は2つの素数それぞれから1を引いた数
(11-1)と(7-1)の最小公倍数を求めます。
ここでは10と6なので、30が最小公倍数です。
その30に適当な正の整数を掛けたものに1を加えたものをべき乗する数にします。

n*30+1=べき乗する数

nは正の整数ならなんでもよいのですが、べき乗する数が2つの異なった数字の積を選びます。

n=1のとき
31。(この数字は素数であるので、利用できません。)
n=2のとき
61。(この数字も素数であるので、利用できません。)
n=3のとき
91。(これは13×7)で求められる数字かつそれぞれ異なっているのでべき乗する数字を13と7に決定します。

④3という数字を暗号化する。
はじめに13乗しても7乗してもよいのですが、先に乗数が多い13乗の方を利用します。
3^13 mod 77 = 38 ←(googleの検索欄に3^13 mod 77と打ち込めば答えが返ってきます。)
この38が暗号化された情報です。

⑤その数字をさらにもう一つのべき乗する数でべき乗し、あまりを出すと3に戻る(復号化)。
38^7 mod 77 = 3

あら不思議3に戻ってきました。

クラック

さて今度はこれをクラックしてみましょう。
わかっている情報(ネットワークを流れる情報)は77と暗号文の38ですね。ここから3という元の数字を見つけていきましょう。

77は素因数分解すると11と7ですね。桁の小さい素数と素数の積なので、素因数分解すればすぐでます。
また(11-1)と(7-1)の最小公倍数は30で、
これを
n*30+1=べき乗する数
n=1のとき・・・31 ×ダメ
n=2のとき・・・61 ×ダメ
n=3のとき91になったので、13と7です

よって
x^13 mod 77 = 38・・・①
38^7 mod 77 = x・・・②

②を計算すると
x=3

クラックできました。

問題

公開鍵が55で、暗号文が18のとき、もとの平文の数字は何になるか答えなさい。
答えは2行下に白い文字で書いておきます。マウスで反転させてください。

答え:2