公開鍵暗号

ＢからＡに公開鍵暗号方法で暗号文を送るとします。

最初にＡからＢに公開鍵を送ります。ある本によると公開鍵とは暗号法の一つだそうです。例えば

公開鍵は：
ABC...をBCD...に一文字ずらす方法

すると平文を"IBM"とすると暗号文は"HAL"になります。
ＢはＡに"HAL"を送ります。
これを受け取ったＡは"HAL"を"IBM"に解読します。

悪意のあるＣが"HAL"を受信したとしても暗号法を知らないので"IBM"には戻すことが出来ない（もちろん、この例とした単純な暗号法では何時かは解読されますが）です。

この公開鍵暗号法を考えた人は賢いとは思いますが、公開するときにＣが公開鍵を見てしまったら意味がないのではないでしょうか。その本にはこの点が触れられていなかったのですが、素数が関係あると書かれていました。

どう関係あるのでしょうか。
難しい解説はご遠慮ください。

質問者からの補足コメント

• 数123
  
  を、Aが見つけた二つの素数
  
  7と11
  
  を公開鍵と秘密鍵として
  
  1/2
  ＡがBに教えた公開鍵を使ってＢが123を暗号化
  
  2/2
  その暗号化された数字をＡが秘密鍵で、元の123に戻す
  
  する様子を教えて下さい。
  上で使っている数値が不適ならば変えてもらって結構です。
  
  
  抽象的な話は、それから考えます。

    補足日時：2016/08/05 02:28

No.12 回答者： tantanmm 回答日時： 2016/08/08 02:42

数百"個" ではなくて 数百"桁" です

仮に500桁の数で，素数の存在確率を0.001（0.1％）とすると
それ以下の素数の個数は497桁個

以下，非常に大雑把な計算ですが：
スパコン 京 の浮動小数点数演算が１秒あたり10PFLOPS =10^16
仮に素数判定などをこの回数できるとして（実際は演算１回ではできるわけないですが）
10^16回×60×60×24×365
=10^23.5
日本一のスパコンを使っても，総当たりでは１年間に24桁いかない

この回答へのお礼

返答ありがとうございます


私の文面が悪いようです。


平文は16
公開鍵は5と21
秘密鍵は11

では公開鍵は5と21の素数が二つ
5の桁数は1桁
21の桁数は2桁
この桁数では実用的ではない。これは実験でわかりました。

>数百桁

なので、実際に使う公開鍵の一つを
840...84
とします。上の数は乱数で決めたとします。
しかし乱数で求めた数　840...84　は素数だとは限りません。むしろ素数ではないではない場合が圧倒的だと思います（一桁なら打率は56%ですが）。
求めた乱数の数が、素数かどうかを判定する方法も無い（力ずくならありますが）ので、素数が出てくるまで繰り返すのも愚かです。

私は小さなプログラムを作るときがあります（専業プログラマではありません）が、その立場なら例えば予め100桁（又は固定バイト数）の素数を最初から表に用意しておくのが定石です。その表の大きさは無限であってはならないし、大きな数の素数の密度は小さい筈なので巨大にはならないと思います。
ネットを検索すれば、今までに見つかった乱数の一覧が公表されているかもしれません（素数は無限にあるそうですが）。

これが正しいとすると、Ｃも同じ表を持っているでしょうから、それを使ってＢから発信された暗号を総当たりで解読することが出来てしまうのでは、と考えました。


実際には、この暗号法は実用となっているので上記の推論が正しくないのは明白ですが、どう間違っているのでしょうか。

お礼日時：2016/08/11 02:35

No.11 回答者： tantanmm 回答日時： 2016/08/06 18:06

No.9（No.2） です

>・20までしか成功していない
割り算の余りなので当然です．この場合は21未満（素数の積未満） の数しか使えません
実際は，もっと大きな素数を使用した上で，その数値以下になるように分割や変換します．

>・6,7,8や13などは暗号化されていません。素通りする場合が多い
これも，21よりももっと大きな数で割る場合には，素通りする割合はずっと小さくなります．
また，盗聴者（悪意のあるＣ）にはその数が素通りしたものなのか変化した数なのか区別ができません．

今回は３と７なので，その積21が割る数になり，変換する平文も暗号文も２0通りにしかなりません．
実際の応用では，素数が数百桁から千桁の数です．

この回答へのお礼

返答ありがとうございます


私は数学に詳しくありませんが、素数は大きくなるとそれが素数がどうか判断できないそうです。それならＡは用意されている素数表（があれば、それ）から使用する二つの素数を選んでいるのではないでしょうか。

大きな数になれば、それだけその中に因子を含んでいる可能性が高くなるので、

一桁では

1 2 3 4 5 6 7 8 9

上の９個のうち、

1,2,3,5,7

の５個なので素数の濃度は56%もありますが、二桁だと10%かもしれません。

>素数が数百桁から千桁の数です．

ならば濃度は1%かもしれません。すると数百桁の素数の個数はパソコンにとっては僅かです。総当たり方法でＣは解読を試みそうなのですが、違うのでしょうか。

お礼日時：2016/08/07 19:16

No.10 回答者： rinkun 回答日時： 2016/08/05 14:13

補足についてですが、公開鍵や秘密鍵はそのまま素数ではないので数字は変わります。

具体例を挙げると
公開鍵： 2279 と 1241の組
秘密鍵： 1649
が一つの事例です。(下記URL)
公開鍵から秘密鍵が推測できますか?

この例で、例えば平文1371を暗号化すると
1371の1241乗を2279で割った余り＝2003
が暗号文になります。
暗号文2003を復号すると
2003の1649乗を2279で割った余り＝1371
が元の平文です。

例をみると、暗号化・復号でも結構な演算が必要なことが分かると思います。

なお、2279が二つの素数の積であることや、どうやって秘密鍵を構成しているかは下記サイトの記載を参照ください。

# RSA の計算例
http://gbb60166.jp/cipher/example.htm

No.9 回答者： tantanmm 回答日時： 2016/08/05 14:03

補足を読んで：

２つの素数がそのまま 鍵になるのではありません．

理解してもらえるかわかりませんが，一応 書いてみます．
7と11では，桁数が大きくなってExcelで計算できませんでしたので，
素数を 「３」と「７」 とします．

公開鍵は「 21と5」．
21は 3×7（素数の積 ）で，暗号化 にも復号にも使用する数です．
5は， 自由に決められます（実際には条件はありますがここでは省略）

この場合の秘密鍵は 11 になります．
２つの鍵の積5×11を， (3-1)×(7-1)で割った余りが１になるような数が秘密鍵となる

平文 を 例えば 16 とします （割り算の余りを使うので，21未満の数）

暗号化：16の5乗 を21 で割った余り( 16^5 mod 21 と書きます）
暗号文： 4
復号： 4の11乗 を21 で割った余り( 4^11 mod 21 ）
計算結果は 16 になる．

おそらく 疑問に思われることとして，
暗号化ができるのに その手順を戻して復号化ができないのか．
できない理由として，べき乗していることと割り算の余りをつかっていることがあると思います．
平方根や３乗根なら簡単だが，大きな累乗の根を求める計算はかなりむつかしい．
暗号文は，割り算の”余り”だけなので 元の数の大小が分からない．

この回答へのお礼

理論は理解していませんが、次で実際に暗号化できることは分かりました。
私のエクセルでは平文の16を変化させるとオーバーフローするので、Maximaを使いました。
次でいいでしょうか。

平文は16
公開鍵は5と21
秘密鍵は11

a:16;
mod(a^5,21);
mod(%^11,21);
/* ============
(%i1) a:16
(%o1) 16
(%i2) mod(a^5,21)
(%o2) 4 <-- 暗号化文
(%i3) mod(%^11,21)
(%o3) 16 <-- 復号成功
============ */


同じことを、16だけでなく1から30まで全て行った結果が以下です：

for a:1 thru 30 do (print([a,b:mod(a^5,21),mod(b^11,21)]))$
/* ============
(%i1) for a thru 30 do print([a,b:mod(a^5,21),mod(b^11,21)])
[1, 1, 1]
[2, 11, 2]
[3, 12, 3]
[4, 16, 4]
[5, 17, 5]
[6, 6, 6]
[7, 7, 7]
[8, 8, 8]
[9, 18, 9]
[10, 19, 10]
[11, 2, 11]
[12, 3, 12]
[13, 13, 13]
[14, 14, 14]
[15, 15, 15]
[16, 4, 16]
[17, 5, 17]
[18, 9, 18]
[19, 10, 19]
[20, 20, 20]
[21, 0, 0]
[22, 1, 1]
文字数制限のため、以下割愛

これをみると
・20までしか成功していない
・6,7,8や13などは暗号化されていません。素通りする場合が多い
これでいいのでしょうか。

お礼日時：2016/08/06 03:07

No.8 回答者： rinkun 回答日時： 2016/08/04 15:30

既に出ている回答にもありますが、公開鍵暗号の本質は暗号化に使う鍵（公開鍵）から復号に使う鍵（秘密鍵）を推定することが困難(事実上不可能)という点にあります。

質問で例に出しているシーザー暗号は、もちろん公開鍵暗号の性質を満たしませんので論外です。
公開鍵暗号で使う鍵は例えば、2つの素数の積を計算するのは簡単だが、2つの素数の積を素因数分解するのは困難である、という事実を利用して作ります。(RSA暗号)
試しに221とか1147を素因数分解してみて、掛け算との難しさの違いを確認してください。なお実際のRSA暗号で扱うのは10進数で千桁に及ぶような大きな数値です。

参考までにRSA暗号を説明しているページを下記に示します。
RSA暗号
https://ja.wikipedia.org/wiki/RSA%E6%9A%97%E5%8F …

ほかに楕円曲線上の離散対数計算の困難さを利用した楕円曲線暗号などがあります。楕円曲線暗号はRSA暗号より複雑な計算を利用して小さめの数値でも暗号強度が保てるようにしています。

No.7 回答者： uyama33 回答日時： 2016/08/03 23:00

最初にＡからＢに公開鍵を送ります。

ある本によると公開鍵とは暗号法の一つだそうです。例えば
公開鍵は：
ABC...をBCD...に一文字ずらす方法

この本は、内容がひどすぎます。
著者に抗議のメールを送りましょう。

No.6 回答者： Tacosan 回答日時： 2016/08/03 01:12

そもそもこんなのを「公開鍵暗号」などとはいわない. 単純にずらすなら「シーザー暗号」, ばらばらに置き換えるなら「換字式暗号」と呼んだりするんだが, 今日のレベルではどちらも容易に解読できてしまうので場合によっては「暗号」とみなされないことすらある.

公開鍵暗号では
・平文を暗号文に変換する暗号化手続き (これは公開する)
・暗号文を平文に戻す復号化手続き (こっちは秘密にする)
の 2つが別々になっていて, かつ
暗号化手続きから復号化手続きが容易には導けない (より正確には「パラメータが容易に計算できない」というべきか)
ように構成されている. 実際のやり方はいろいろあるので勝手に調べてくれ.

多くの場合は復号化→暗号化の順にもできてこれが電子署名に使われたりもするんだが, これは公開鍵暗号系の要件ではない.

No.5 回答者： LEVELUP100 回答日時： 2016/08/02 19:06

暗号の話ついでに。

　つい先日に発表があったばかりの最新型暗号手法。

KDDI研究所、世界で誰にも解読されていない60次元LWE暗号の解読に成功
http://ascii.jp/elem/000/001/195/1195823/

No.4 回答者： tantanmm 回答日時： 2016/08/02 19:05

質問の例では 暗号化が[１文字"前に"ずらす]なので，

復号化が[１文字"後ろに"にずらす] とすぐにわかっています．

しかし公開鍵暗号方式（RSAが有名）は，[暗号鍵（鍵X とします）]と[復号鍵（鍵Y ）]が別であることが重要です．
鍵Xで暗号化した文は 鍵Yでしか復号化できないので，暗号化の方法がわかっても復号はできません
たとえるなら，南京錠（昔からある鍵です）のような感じです．
ロック（施錠）は誰でも簡単にできますが，開錠は 鍵がなくてはできません．

だから，一般に公開している鍵Xはロックの方法だけです．
開錠（復号化）できるのは，鍵Yをもっている「Ａ」だけです．
「Ｃ」は暗号化の方法を知っても，復号できない．

同じことが電子署名にも使われます．
公開鍵Xで復号できる文章をつくることができるのは，鍵Yをもっている「Ａ」しかいないので，
その文章はたしかに「Ａ」が書いた という証明になります．

で，２つの鍵には素数が使われています．
>難しい解説はご遠慮ください。
とのことなので，もし必要なら検索してみてください

No.3 回答者： tosa0824 回答日時： 2016/08/02 18:54

補足になりますが、公開鍵暗号では通信者は自分の公開鍵と秘密鍵を必ず両方持っています。

公開鍵は文字通り世間一般に公開しても大丈夫な鍵です。対して秘密鍵は絶対に誰にも公開してはいけません。

BさんからAさんに情報を送る場合には、以下のようにします。

(1)まず通信に先立って、Bさんは、Aさんの公開鍵を何らかの方法でAさんから入手しておきます。

(2)Bさんは、情報を"Aさんの"公開鍵で暗号化し、暗号文をAさんに送ります。

(3)Aさんは、届いた暗号文を、自分の(つまりAさんの)秘密鍵で解きます。すると、暗号が解けて情報を読むことができます。

ポイントは、

・相手の公開鍵で暗号化して、送る。
・届いたら、自分の秘密鍵で暗号を解く。

ということ。暗号文は公開鍵のペアの秘密鍵でしか解けません。なので誰に見られても安全なのです。

ただし、公開鍵暗号はビット数が共有鍵暗号よりも長く、計算が複雑なので、たくさんの情報を送るには適しません。メールくらいなら充分実用的ですが。