目の変化びと

感覚のとつぜんの不可逆的な変化

< 新しい記事

新着記事一覧(全4289件)

過去の記事 >

2016年01月10日

AさんとBさんが、電話で数字（自然数）をいくつかしゃべり、その数字が盗聴されても、AさんとBさんだけの秘密の数字を作ることができます。

たとえば、電話でNとMという数字を決めます。

実用的にする（解読されない）には、Mはすごく大きな素数でなければいけないのですが、とりあえずここでは、かんたんに試せるよう、Mは13にします。Nは2にします。

AさんとBさんは、それぞれ自分だけの数字（相手に教えないので、盗聴されません）を決めます。

自分だけの数字は、1から（M-2）までの整数から選びます。
ここではM＝13なので、1から11までの整数から選びます。

Aさんが整数aを、Bさんが整数bを選びます。
たとえば、Aさんが4、Bさんが5、を選んだとします。

AさんはNをa乗します。（aはAさんにとって、自分だけの数字です）

そして、16をM（＝13）で割った余り、3をBさんに伝えます。

BさんがAさんから伝えられた数をcとします。
Bさんはcをb乗します。（bはBさんにとって、自分だけの数字です）
ここではc＝3、b＝5、なので、243です。
243をM（＝13）で割った余り、9が秘密の数字（＊）になります。

立場を逆にしてみましょう。

BさんはNをb乗します。
ここではN＝2、b＝5、なので、32です。
そして、32をM（＝13）で割った余り、6をAさんに伝えます。

AさんがBさんから伝えられた数をdとします。
Aさんはdをa乗します。

1296をM（＝13）で割った余り、9が秘密の数字（＊と同じです）になります。

ちなみに、1296を13で割った余りを電卓で出す方法は、

電卓で割算の余りを求める方法（クリックしてね）

ということで、AさんとBさんは、たとえ盗聴されたとしても、二人だけの秘密の数字（ここでは9）を作ることができました。

さて、どういう仕組みになっているかというと、

AさんはNをa乗します。（aはAさんにとって、自分だけの数字です）

（Nのa乗）＝eM＋c、という形の式になるので、
c＝（Nのa乗）-eM、です。

BさんはAさんから伝えられた数、cをb乗します。（bはBさんにとって、自分だけの数字です）
c＝（Nのa乗）-eM、をb乗するというのは、
（（Nのa乗）-eM）をb回かけることなので、計算してまとめると、
（cのb乗）＝（（Nのa乗）-eM）のb乗＝（（Nのa乗）のb乗）＋DM、という形の式になります。
これをMで割った余りは、DMがMで割り切れるので、（（Nのa乗）のb乗）をMで割った余りと同じになります。
（（Nのa乗）のb乗）＝（Nのab乗）なので、
（cのb乗）をMで割った余りは、（Nのab乗）をMで割った余り（秘密の数字＊＊）になります。

立場を逆にして計算すると、

BさんはNをb乗します。
そして、（Nのb乗）をMで割った余り、dをAさんに伝えます。
（Nのb乗）＝fM＋d、という形の式になるので、
d＝（Nのb乗）-fM、です。

AさんはBさんから伝えられた数、dをa乗します。
d＝（Nのb乗）-fM、をa乗するというのは、
（（Nのb乗）-fM）をa回かけることなので、計算してまとめると、
（dのa乗）＝（（Nのb乗）-fM）のa乗＝（（Nのb乗）のa乗）＋EM、という形の式になります。
これをMで割った余りは、EMがMで割り切れるので、（（Nのb乗）のa乗）をMで割った余りと同じになります。
（（Nのb乗）のa乗）＝（Nのab乗）なので、
（dのa乗）をMで割った余りは、（Nのab乗）をMで割った余り（秘密の数字で、＊＊と同じです）になります。

ということで、AさんとBさんは、電話でやりとりした数字、N、M、c、d、をすべて盗聴されたとしても、二人だけの秘密の数字（（Nのab乗）をMで割った余り）を作ることができるのでした！

お気に入りの記事を「いいね！」で応援しよう