前 5‒23 p ｜ 
もくじ i ｜ 次 5‒25 n 
これは2002年に書かれた記事です。 RSAのしくみについて、具体的な数値例を挙げて、具体的に説明しています。 「JavaScript: 触って分かる公開鍵暗号RSA」（2004年2月）を先に読まれたほうが、 全体が分かりやすいかもしれません。
公開鍵暗号系のうち最も簡単なRSA暗号系について、理論的な面をさわりだけ説明する。公開鍵暗号ソフト（PGP、GPG）の実際の使い方については、別の特集「やさしいPGP」、「公開鍵」の概念イメージについては「はじめてのPGP」、公開鍵暗号の哲学については「ネット世界における暗号の哲学」をごらんください。以下のメモには続編「JavaScriptでPGPもどき」があります。また、用いられる数学の基礎については「フェルマーの小定理」も参考になさってください。
0, 1, 2, 3 ……というふつうの整数は、どこまでも延々と一直線に続いていきますが、あるところまで行くと 0 に戻る、という「リングワールド」を考えることもできます。例えば、5 まで行くと次は 0 に戻ると考えてみます。
0+1=1, 1+1=2, 2+1=3, 3+1=4, 4+1=5, 5+1=6≡0, 6+1=7≡1, 7+1=8≡2, ...
5+1は、ふつうの計算では6ですが、「リングワールド」では6は0に等しいのです。以下では、ふつうの計算とリングワールドの計算の両方を使うので、混乱しないようにリングワールドの等しいは ≡ （合同記号）で表します。例えば
6≡0
37≡1
というのは、じつは「6を6で割ると余りは0」「37を6で割ると余りは1」と解釈できます。
何で割ったときの余りかハッキリさせるために、
37≡1 (mod 6)
と書いて、6を
37≡7 (mod 10)
は、37を10で割ると余りは7、ということです。このように≡の「等しい」は何を法にするかによって成り立ったり成り立たなかったりするので注意が必要です。前後の流れから分かるときは、法を明示しないこともあります。
「modを求める」演算（
19 + 36 = 55 ≡ 5 (mod 10)
これは55を10で割ると余りは5だ、というだけのことです（べつに難しいことじゃないです）。そして
19≡9 (mod 10)
36≡6 (mod 10)
19 + 36 ≡ 9 + 6 = 15 ≡ 5 (mod 10)
というふうに、先に余りを求めて、余りどうしを足しても、結果は同じです。実際、商 q1, q2 と余り r1, r2 を使って
a = 10q1 + r1
b = 10q2 + r2
となっているとき、和
a + b = 10(q1+q2) + (r1+r2)
の右辺第一項は10で割り切れるので、a+b を10で割ったときの余りは (r1+r2) にのみ依存します。これは先に余りを求めて余り同士を足しても同じ、ということを意味しています。法は10でなくても同じことです。足し算くらいだと、だからどーした？という感じですが、かけ算になると、先に余りを求められることが役立ちます。
953872≡2 (mod 10)
84539876523≡3 (mod 10)
この場合、953872×84539876523を実際に計算しなくても、この積は≡6 (mod 10) になります。2×3=6だから。とくに、
845398765234≡34=81≡1 (mod 10)
などとできます。84539876523の4乗を10で割ると余りはいくつか？というときには、素直にこのでかい数の4乗など計算しなくても、先に10で割って、その余りを4乗したほうがラクです。
以上の予備知識で本論に突入する。
公開鍵暗号系では、エンコード専用の公開鍵 E とデコード専用の秘密鍵 D とがあって、E は公開することができる。E が分かっても、そこから D を逆算することが困難なので、第三者に暗号を解読されてしまう心配がない ―― という考え方なのだ。
暗号化規則 E は、てきとーでは、いけない。例えば、4980 1234 というクレジットカード番号を暗号化するエンコード鍵 E として「各数字に1を足す(mod 10)」を採用したとする。4980 1234 は E によって 5091 2345 にエンコードされる。この場合、Eは公開されているのだから、Dが「各数字から１を引き算する」であることがすぐバレてしまうのであって、お話にならない。だれでも簡単に暗号を解読できカード番号が分かってしまうのだ。
RSAの公開鍵は理論上、2つの整数からなる。この整数は実際には、かなり大きくなければならない。例えば100桁とか200桁とかそのくらいのオーダーの数だ。けれど、ここでは説明のために、小さな数を使う。例えば、7 と 17441 を選ぶことができる。この場合の暗号化規則は「もとの数を7乗して、17441で割った余りを求める」となる。
カード番号 4980 1234 を上の規則で暗号化すると……
4980 → 49807 = 75963575698322238720000000 → 17441で割ると余り6943
1234 → 12347 = 4357186184021382204544 → 17441で割ると余り 90
すなわち、4980, 1234 は 6943, 90に暗号化された。
この場合、エンコード規則は分かっているが、どうやってデコードすればいいのか簡単には分からない。エンコード結果は17441で割った余りなので、0～17440までの17441通りの可能性がある。何をエンコードしたら6943になったのか知るのに、1をエンコードするとどうなるか？ 2をエンコードするとどうなるか？ とかたっぱしから調べていけば、いつかは何が6943になるか分かるわけだが、現実のRSAでは1万どころか200桁とかの数（10200）が使われるから、このような総当たり攻撃では事実上、解読不能である（毎秒1億パターンを検査しても、1年かかってまだ1016にも達しない）。
ところが、公開鍵を公開した当事者のところには「秘密鍵」があって、この秘密の抜け道を使えば、エンコードのアルゴリズムを逆算しなくても、あっというまに直接デコードが可能なのである。秘密鍵による秘密のデコード規則は「14719乗して17441で割った余りを求める」というもので、これを知っている「本人」にだけは、簡単に暗号解除ができる。公開鍵しか知らない第三者には、そういうことができないから、結局、第三者には解読できない暗号になる。
6943 をデコードするには、694314719を17441で割った余りを求めれば良い。答は 4980 だ。同様に、90 をデコードするには、9014719を17441で割った余りを求めれば良い。答は 1234 であり、これで暗号化されていたカード番号 4980 1234 が復元された。与えられた数 a をデコードする計算は、実際には次のように行えば良い。
14719 = 8192 + 4096 + 2048 + 256 + 64 + 32 + 16 + 8 + 4 + 2 + 1
であるから、一気に14719乗するかわりに
a8192 × a4096 × a2048 × a256 × a64 × a32 × a16 × a8 × a4 × a2 × a1
を考える。そして、かけ算の各因子ごとに余りを求めれば良い。具体的に、a = 6943 の場合、
69431 ≡ 6943
69432 ≡ 6943×6943 ≡ 15766
69434 ≡ 15766×15766 ≡ 15065
69438 ≡ 15065×15062 ≡ 11933
694316 ≡ 11933×11933 ≡ 8165
694332 ≡ 8162×8165 ≡ 7723
694364 ≡ 7723×7723 ≡ 13950
6943128 ≡ 13950×13950 ≡ 13263
6943256 ≡ 13263×13263 ≡ 14684
6943512 ≡ 14684×14684 ≡ 14214
69431024 ≡ 14214×14214 ≡ 1252
69432048 ≡ 1252×1252 ≡ 15255
69434096 ≡ 15255×15255 ≡ 17203
69438192 ≡ 17203×17203 ≡ 4321
である。太字部分の数を全部かけて17441で割った余りが、すなわち694314719を17441で割った余りであって、4980である。
ここで、例えば、69434を17441で割った余りを求めるのに、6943を実際に4乗しなくても、
「69432を17441で割った余りr」の自乗、を17441で割った余り
を求めても同じだということに注意する。実際、商がqと余りがrで
69432 = 17441q + r
と書いたとき、
69434 = (69432)2 = (17441q + r)2
=(17441q)2 + 2(17441qr) + r2 …… (*)
右辺の第一項と第二項は17441で割り切れるのだから、結局 (*) を17441で割ったときの余りは第三項の r2 にのみ依存する。
いちいち手計算でやっていては面倒だし間違いやすいので、スクリプトで書いてしまおう。配列を使ってもいいが、とりあえずベタに書いておく。より詳しくは、続編「JavaScriptでPGPもどき」参照。
var modulus = 17441;
function square_r( number ) {
return ( number * number ) % modulus;
}
function decrypt( the_encrypted ) {
var a1 = the_encrypted;
var a2 = square_r( a1 );
var a4 = square_r( a2 );
var a8 = square_r( a4 );
var a16 = square_r( a8 );
var a32 = square_r( a16 );
var a64 = square_r( a32 );
var a128 = square_r( a64 );
var a256 = square_r( a128 );
var a512 = square_r( a256 );
var a1024 = square_r( a512 );
var a2048 = square_r( a1024 );
var a4096 = square_r( a2048 );
var a8192 = square_r( a4096 );
return a8192 * a4096 % modulus * a2048 % modulus * a256 % modulus
* a64 % modulus * a32 % modulus * a16 % modulus * a8 % modulus
* a4 % modulus * a2 % modulus * a1 % modulus;
}
// alert(decrypt(6943));
秘密鍵が分かれば、暗号ソフトは上記のようなアルゴリズムで計算して、対応する公開鍵で暗号化された文章をたちまち解読できる。
RSA暗号による暗号化は、公開された2つの数 n, α ―― 上の例では n = 17441, α = 7 ―― にもとづいて行われる。n は法で、α は指数である。暗号を解除するときは、同じ法 n と秘密の指数β ―― 上の例では β = 14719 ―― を使う。βは公開してはいけない。いまスクリプトを示したように、秘密の指数が分かれば、暗号文はすぐに解読されてしまう。
このような秘密の指数は、そもそもどうやって生成されたのだろうか。
RSAの鍵ペアを生成するには、まず2つの素数 p, q を選ぶ。p, q は3以上でなければならない（実際には充分に巨大でなければならない）。いまの例では、じつは p=107, q=163 が選択されている。この2素数の積 n = pq = 17441 こそが公開鍵の第一の部分となる。
エンコード用の指数αは2以上で、 (p-1)(q-1) と互いに素であるように選ぶ。上の例では、
(p-1)(q-1) = 106*162 = 17172 = 22×34×53
なので、2でも3でも53でも割り切れない数なら何でも良い。上の例では、α=7 を選んである。これが公開鍵の第二の部分だ。
以上の条件で暗号化規則 E を「α乗して n で割った余りを求める」としたとき、E は
Zn = { 0, 1, 2, ... , n-1 }
から自分自身の上への一対一写像になっている（ここでは証明しない）。くだいていうと、規則Eは、入力が違えば、必ず違うコードにエンコードしてくれる。もし仮に異なる入力 a と b が同じ z にエンコードされたら、暗号 z を解読するとき原文が a だか b だか分からなくなって困ってしまう。
次に、秘密鍵βを、
αβ≡1 (mod (p-1)(q-1))
を満たすように選ぶ。くだいていうと、さっき決めた公開用のαとかけあわせて(p-1)(q-1)で割ったとき、余りが 1 になるようにする。
（これが秘密鍵βの満たすべき十分条件になっている。）
上の例ではα = 7, (p-1)(q-1) = 17172 であり、例えばでたらめに12345という数を選んだとして、
7×12345 = 86415 → 17172で割ると余り555
―― 余りが1でないので12345は条件を満たさない。すでに示したようにβ = 14719 とすると
7×14719 = 103033 → 17172で割ると余り1
となるから、14719が正しい秘密鍵の例だ。
上のようにして公開鍵 n, α を選んだときには、このような条件を満たす秘密鍵βが必ず存在する（ここでは証明しない）。そして、このβを使うと、「β乗して n で割った余りを求める」ことが暗号解除規則 D となる。要するに、写像 E に 写像 D を合成すると、恒等写像になる。くだいていえば、規則Eでコーディングしたものにさらに規則Dを継ぎ足すと、もとに戻る。
n と α が与えられたとしても、それだけではβを求められない。（もし求められたら、公開されている n と α から秘密鍵 β が求まってしまう。）総当たり的にβを決定するにしても、αとかけて何を法として 1 と等しくなるか、という情報、すなわち (p-1)(q-1) がいくつか？ が分かっていないといけない。
n の因数 p と q が分かっているなら、βは次のようにして簡単に決定できる。
var p = 107, q = 163, alpha = 7;
var u = ( p-1 ) * ( q-1 );
var u0 = u;
var a0 = alpha;
var t0 = 0, t = 1;
var r = u0 % a0;
var q = (u0-r)/a0;
var MAX_STEPS = 10000;
for(var i=0; r>0 && i<MAX_STEPS; i++) {
var tmp = t0 - q * t;
if( tmp >= 0 ) tmp = tmp % u;
else tmp = u - ( (-tmp) % u );
t0 = t, t = tmp, u0 = a0, a0 = r;
r = u0 % a0;
q = (u0-r)/a0;
}
var beta = t % u;
if( i >= MAX_STEPS ) document.write("<p>Error: too many steps.<\/p>");
else if( a0 == 1 ) document.write("<p>beta = " + beta + "<\/p>");
else document.write("<p>beta not exists.<\/p>");
要するに「n = 17441, α = 7」という公開鍵から秘密鍵βを計算できるかどうかは、
17441 = 107 × 163
という因数分解ができるかどうか、が本質的である。17441は公開鍵だから公開して良いのだが、それが二つの素数107と163の積として生成された、という事実は、絶対に秘密にしないといけない。
17441 のような小さな数であればいくら秘密にしたところでコンピュータを使って簡単に因数分解できるので、そうなると、上のようにして秘密鍵が計算されてしまう。実際のRSA暗号の実装においては、p と q は100桁程度、したがってそれらの積 n は200桁程度の大きな数である。現在までに知られているアルゴリズムでは、桁数が増加するにつれて因数分解に必要な計算時間は急激に増加して、このくらい大きな数は、事実上、因数分解できない。くだいていえば、巨大整数を因数分解するうまい方法が見つかっていない。「もし巨大整数の因数分解が高速にできるようになると、RSA暗号が破られる」というのは、こういうことだ。
以上の説明から、RSAを使う暗号ソフトが鍵生成のとき何をしているか察しがつくだろう。
暗号ソフトは、まず巨大な素数をランダムに2つ生成しなければならない。実際には素数っぽい数をランダムに生成して、それが本当に素数かどうか検証し、使える素数が見つかるまで続ける。（素因数分解は難しいが、素数であるか素数でないか、は、比較的、簡単に決定できる。）
必要な大きさの2素数 p, q が見つかったら、それらの積 pq = n を求める。また、(p-1)(q-1) からαの条件を決定し、条件を満たすαをランダムに選んで固定する。この n と α の組み合わせが公開鍵になる。一方、αを決定すると秘密鍵βが決まるので、それを保存するとともに、あなただけの秘密として大事にバックアップしてもらう。
あなたの公開鍵を公開すれば、それを使ってほかの人々は、あなたあての暗号文を生成できる。この暗号文は秘密鍵βを知っているあなたのソフトにとっては、容易に解読可能であるが、第三者には解読困難である。
第三者に暗号が読まれてしまう原因の大半は、暗号のクラックではなく、あなたがβを保存したファイルを盗まれてしまうことである。現代の暗号系は非常に強力であり、1億円のコストの計算時間を使っても解けない。それに比べて人間系はあきれるくらい
下記スクリプトは、公開鍵 n = 61293097, alpha = 643 によるRSA暗号化を行う。例文「My card number is visa 4980-1234-5678-9000.」は、次の暗号文に変換される。
59188269, 53486147, 31240161, 55632414, 51104084, 51963820, 50848936, 1724572, 46486308, 49607229, 8921146, 45609411, 25816484, 42186769, 9678617,
ある場所に秘密の動画をアップロードして、そのURLを下記スクリプトで暗号化したところ、次の出力を得た。
50353369, 26785443, 8043884, 41632749, 34747730, 52251519, 11487607, 54802, 51627438, 44212514, 29630823, 8597012, 49492462,
(1) http://～を下記のスクリプトで暗号化すると、上記と冒頭部分は同じになる。このことを知って、まず総当たり攻撃（変換表を作成して逆引きできるか）を試してください。
(2) n を因数分解して、(p-1)(q-1) を決定し、総当たり的にβを求められるか試してください。(p-1)(q-1) を法として、αとの積が1に等しくなるようにします。
(3) 本文であげたスクリプトを使って、直接βを決定してください。
(4) 「スマート」なクラックを実行するためのスクリプトを書いてください。下記スクリプトを使って生成されたどのような暗号文も、たちまち逆算解読できるようなスクリプトを作ってください。
var input = "http://sample.net/";
var modulus = 61293097;
function square_r( number ) {
return ( number * number ) % modulus;
}
function encrypt( the_plain ) {
var a1 = the_plain;
var a2 = square_r( a1 );
var a4 = square_r( a2 );
var a8 = square_r( a4 );
var a16 = square_r( a8 );
var a32 = square_r( a16 );
var a64 = square_r( a32 );
var a128 = square_r( a64 );
var a256 = square_r( a128 );
var a512 = square_r( a256 );
return a512 * a128 % modulus * a2 % modulus * a1 % modulus;
}
var output = "";
var char0, char1, char2;
var code0, code1, code2, code;
for(var i=0; i<input.length; i+=3) {
char0 = (input.substr( i , 1 ));
char1 = (input.substr( i+1 , 1 ));
char2 = (input.substr( i+2 , 1 ));
code0 = char0? char0.charCodeAt() : 0 ;
code1 = char1? char1.charCodeAt() : 0 ;
code2 = char2? char2.charCodeAt() : 0 ;
code = code0 * 128 * 128 + code1 * 128 + code2;
output += encrypt(code);
output += ", ";
}
document.write("<p>Encrypted: " + output + "<\/p>");
「高校数学で遊ぶ公開鍵暗号RSA」につづき、理解深めるために、JavaScript上でごく小さいRSAを実装してみる。
さらに大規模な実装例は次を参照:
/demo/PigPGP/0_2_3ja.php
JavaScriptで「ふつう」に扱える整数は 253 までである。単純に考えると52ビットまでの鍵を使える。しかし途中計算で積をとったりするので、その半分以下にしたほうが簡単だ。ここでは大きな数の計算を独自に実装することが目的でなく、あくまでRSAをJavaScript上で構築してみるのが目的だからだ（巨大整数の計算については別記事「JavaScriptで1000桁電卓」を参照）。以下では暗号強度を24ビットとする。
最初にいくつかの一般的な関数などを定義しとく。
function _debug( message ) {
document.write( "<p>Debug: " + message + ".<\/p>" );
}
function isPrime( number ) {
if( number < 2 || number != Math.floor(number) ) {
_debug("[ERROR] Unexpected input " + number + " at function isPrime");
return false;
}
for( var i=3; i <= Math.sqrt(number); i+=2 ) {
if( number % i ==0 ) {
_debug( number + " divisible by " + i );
return false;
}
}
_debug( "* " + number + " is prime" );
return true;
}
function log2( x ) {
return Math.log( x ) / Math.log( 2 );
}
var MAX_STEPS = 10000;
鍵を生成するために、2つの素数 p, q を見つける。ミリ秒単位のUnix秒から種を得る。種は一定の値の範囲の奇数になるようにする。素数が見つかるまで2ずつ増やしながら検索をつづける。この方法だと p, q は必ず隣同士の素数になり、n = pq の因数分解が容易になってしまう。しかし24ビットではどっちにせよもともと容易なので、気にしないことにしよう。
var strength = 24;
if(strength<24 || strength%2!=0 ) strength = 24;
_debug( strength + "-bit RSA");
var max = Math.pow( 2, (strength/2) ), min = Math.pow( 2, (strength/2 - 1) );
var objDate = new Date();
var seed = ( objDate.getTime() ) % max;
if( seed < min ) seed += min;
if( seed % 2 == 0 ) seed += 1;
_debug( "seed = " + seed );
var number, p = 0, q = 0, n;
for( var i=0; i<MAX_STEPS; i++ ) {
number = seed + i*2;
if( isPrime(number) ) {
if( p==0 ) p = number;
else {
q = number;
n = p * q;
break;
}
}
}
_debug("p = " + p );
_debug("q = " + q );
_debug("n = " + n );
_debug( "log<sub>2<\/sub>n = " + log2( n ) );
//isPrime( n );
次に公開指数αを決定する。αは u = (p-1)(q-1) と互いに素でなければならない。そのことを保証するためにあらかじめ (p-1)(q-1) の素因数を調べあげても良いが、ユークリッドの互除法を使ってαとuの最大公約数が1であることを確認したほうが手っ取り早い。
function gcd( a, b ) {
if( a<1 || b<1 || a!=Math.floor(a) || b!=Math.floor(b) ) {
_debug("[Error] a=" + a + ", b=" + b + " at function gcd(a, b)");
return 2;
}
var r0=a, r1=b, r=1;
for( var i=0; i<MAX_STEPS; i++) {
r = r0 % r1;
if(r==0) break;
r0 = r1, r1 = r;
}
_debug( "gcd(" + a + ", " + b + ") = " + r1 );
return r1;
}
var u = (p-1)*(q-1);
_debug("u = " + u );
var v = ( objDate.getTime() ) % max;
if( v < min*1.5 ) v += min*1.5;
if(v%2==0) v+=1;
_debug("v = " + v );
for( var i=0; i<MAX_STEPS; i++ ) {
if( gcd(u, v) == 1) break;
else v += 2;
}
var alpha = v;
_debug("alpha = " + alpha);
法 n と公開指数α が求まったので、秘密鍵βを決定することができる。
u=(p-1)*(q-1);
var u0 = u;
var a0 = alpha;
var t0 = 0, t = 1;
var r = u0 % a0;
var q = (u0-r)/a0;
for(var i=0; r>0 && i<MAX_STEPS; i++) {
var tmp = t0 - q * t;
if( tmp >= 0 ) tmp = tmp % u;
else tmp = u - ( (-tmp) % u );
t0 = t, t = tmp, u0 = a0, a0 = r;
r = u0 % a0;
q = (u0-r)/a0;
}
var beta = t % u;
if( a0 == 1 ) _debug("beta = " + beta);
else _debug("[ERROR] beta not exists");
_debug("log2(alpha*beta) = " + log2(alpha*beta) );
_debug("alpha*beta (mod u) = " + alpha*beta%u);
document.write("<dl>");
document.write("<dt>Public Key<\/dt>");
document.write("<dd>n = " + n + " , alpha = " + alpha + "<\/dd>");
document.write("<dt>Secret Key<\/dt>");
document.write("<dd>beta = " + beta + "<\/dd>");
document.write("<\/dl>");
生成された公開鍵を使って3つのサンプルを暗号化する。
暗号化指数αは大きいから、累乗は分けて計算する必要がある。
var sample1 = 123, sample2 = 7743, sample3 = n-5;
/*
n=17441,
alpha=7,
beta=14719;
sample1=4980;
sample2=1234;
*/
_debug("sample1 = " + sample1 );
_debug("sample2 = " + sample2 );
_debug("sample3 = " + sample3 );
var alpha_bin = alpha.toString(2);
var D_alpha = new Array();
for(var i=0; i<alpha_bin.length; i++) {
D_alpha[i] = alpha_bin.substr( alpha_bin.length-1 - i , 1 );
}
function encrypt( the_plain ) {
var Work = new Array();
var result = 1;
for(var i=0; i<alpha_bin.length; i++ ) {
if(i==0) Work[i] = the_plain;
else Work[i] = Work[i-1]*Work[i-1]%n;
if( D_alpha[i] == 1 ) {
result *= Work[i];
result %= n;
}
}
return result;
}
var e1 = encrypt( sample1 );
_debug( "sample1 encrypted: " + e1 );
var e2 = encrypt( sample2 );
_debug( "sample2 encrypted: " + e2 );
var e3 = encrypt( sample3 );
_debug( "sample3 encrypted: " + e3 );
秘密指数βを使って暗号を解除する。
var beta_bin = beta.toString(2);
var D_beta = new Array();
for(var i=0; i<beta_bin.length; i++) {
D_beta[i] = beta_bin.substr( beta_bin.length-1 - i , 1 );
}
function decrypt( the_encrypted ) {
var Work = new Array();
var result = 1;
for(var i=0; i<beta_bin.length; i++ ) {
if(i==0) Work[i] = the_encrypted;
else Work[i] = Work[i-1] * Work[i-1]%n;
if( D_beta[i] == 1 ) {
result *= Work[i];
result %= n;
}
}
return result;
}
var d1 = decrypt( e1 );
_debug( "sample1 decrypted: " + d1 );
var d2 = decrypt( e2 );
_debug( "sample2 decrypted: " + d2 );
var d3 = decrypt( e3 );
_debug( "sample2 decrypted: " + d3 );
