7 : 15 平方剰余の相互法則

← 7 - 14 p↑ もくじ i 7 - 16 n →

***と表示されるパスワードを読み取るツール

2003年 3月30日
記事ID d30330

Revelation 小粒でもピリリと辛いフリーウェアシリーズ、今回は「パスワード読みとり」つながりで SnadBoy's Revelation v2。

DeFFFTPとして、FFFTPが暗号化して保存しているパスワードをデコードする方法を説明した。 「わざわざデコードしなくても通信を監視すれば良い」だの「みえみえ系を使えば良い」という考えもあるだろうが、 アルゴリズムを解析して暗号を自力で解読するというアプローチそれ自体に多くのかたは興味を感じると信じる。 しかし、DeFFFTPは、その名の通りFFFTPの暗号解除にしか使えない。 一般のパスワード(Windowsのエディットボックスで *** のように表示されるもの)を直接読み取るツールを紹介する。

名前は Revelation 、SnadBoy Software からダウンロードできる。 2003年3月現在バージョン2.0。

使い方は「みえみえパスワード」系の標準で、起動した画面にある円形のカーソル を、 見たいエディットボックスの上にドラッグすれば良い。

*** と隠されているパスワードが読み取れると、ソフト画面内に表示される。

Windows 2000 で動作確認した。このツールは起動するとネットと通信しようとするが、通信を許可しなくても動作する。

リンク

関連記事
ほかの小粒ツールより
参考

この記事のURL

テキスト版省パケ版XML版


平方剰余へいほうじょうよの相互法則

2003年 3月26日
記事ID d30326

平方剰余へいほうじょうよというのは難しそうな名前だが、 早い話が「平方数」のことだ。 ふつうの整数で 4, 9, 16, 25, ... などは平方数(ある整数の二乗)だが、3, 6, 14, 23 などは平方数でない(ある整数の二乗にならない)。

7を法とする世界で考えよう。7を法とすると、
02 = 0 ≡ 0
12 = 1 ≡ 1
22 = 4 ≡ 4
32 = 9 ≡ 2 (9を7で割ると2余る)
42 = 16 ≡ 2 (16を7で割ると2余る)
52 = 25 ≡ 4 (25を7で割ると4余る)
62 = 36 ≡ 1 (36を7で割ると1余る)
となっているので、この世界では、0, 1, 2, 4 が平方数だ。 また、3, 5, 6 は平方数でない。「7を法とする平方数」「7を法とする平方数でない数」のことを、 「7の平方剰余」「7の平方非剰余」というのだが、言葉遣いが難しいと分かりにくくなるので、ここでは「平方数」で通す。

以下で説明する平方剰余の相互法則は、古典的整数論においては「基本」であると同時に「数の神秘」であり、ひとつの山場ともなっている。 イデアル論の立場からは別に神秘的でなく透明に理解することができるので、二次体を導入してから平方剰余の相互法則に進むのが現代的かもしれない。 しかし、平方剰余の相互法則の意味そのものは中学生にも理解できる。 巨大素数を扱う暗号学の立場からは、相互法則はヤコビ記号を使うソロベイ・ストラッセン・テストの基礎となっている。 確率的素数判定であるから、このテストをすりぬける「オイラー擬素数」の概念も生じる。

RSA暗号系から派生したネタとして、 フェルマーの小定理擬素数ラビン・ミラーのテストと強擬素数についてすでに書いた。 これらは暗号システムそのものというより「どうやって暗号に使う巨大素数を用意するのか」という下準備のような話だった。 話のついでなので、擬素数つながりで、ソロベイ・ストラッセン・テストとオイラー擬素数にもふれよう。 そのため、今回は平方剰余の相互法則を導入しておく。次回ルジャンドル記号とヤコビ記号を導入してオイラー擬素数まで行く予定だ。 なお、ここでは具体例の観察だけで証明はつけないので、詳しくは将来、自分で勉強してほしい。

ある数が平方数であるかないか

上でみたように、7を法とすると、0, 1, 2, 4 は平方数、3, 5, 6 は平方数でない。このことを次のように略記しよう:
0 R 7
1 R 7
2 R 7
4 R 7
3 N 7
5 N 7
6 N 7

a R b とは x2≡a (mod b) を満たす x が存在するということであり、 a N b とは x2≡a (mod b) に解がないことを言っている。

問題: 17 R 13 か?
解答: はい。mod 13 では 17≡4 だから x2≡4 (mod 13) に解があるか考える。2を二乗すれば4なので解がある。22 = 4 ≡17 (mod 13)
問題: 13 R 17 か?
解答: はい。82 = 64 ≡ 13 (mod 17)(64を17で割ると3余り13なので)

第一の例から分かるように、13を法として4が平方数か?ということと17が平方数か?ということは、同じ意味になる。 4≡17 (mod 13) だからだ。つまりAが平方数かどうか?と尋ねているとき、実際にはAという特定の数について尋ねているというより、 Aと合同なすべて剰余類について尋ねていてAという数はその代表例にすぎない、と考えても良い。 だから厳密な用語としては「平方数」(数)でなくて、その数をひとつの代表例とするような「平方剰余」(剰余類)ということになる。 この区別は言葉の上の話で、あまり本質的でないので、分からなければ気にしなくて良い。

問題: 6は17を法として平方数か? 言い換えれば 6 R 17 か、それとも 6 N 17 か?
ちからまかせにやるには、全部の可能性をかたっぱしからチェックすれば良い。
02 ≡0
12 ≡1
22 ≡4
32 ≡9
42 ≡16
52 ≡8
62 ≡2
72 ≡15
82 ≡13
92 ≡13
102 ≡15
112 ≡2
122 ≡8
132 ≡16
142 ≡9
152 ≡4
162 ≡1
……17を法とする世界では何を平方しても6にはならないことが分かる。したがって答は「いいえ」だ。6 N 17 である。

ところで、さらによく観察すると、この場合、1の平方と16の平方は等しく、2の平方と15の平方は等しく……以下同様に、 nの平方と17-nの平方は等しくなっている。これは当たり前のことで、
(17-n)2 = 172 - 2·17·n + n2 ……①
の右辺第一項、第二項は17で割り切れるので、17で割った余りという観点ではこれらは0に等しく、
(17-n)2 ≡ n2 (mod 17)
だからだ。ということは、1の二乗、2の二乗……と計算していくと、半分の17/2より先には新しいものはでない。 言い換えれば、上の計算結果では、0は別にして、右辺には同じ数がぜんぶ2回ずつ現れる。 したがって、17を法とする世界では、すべての元が平方数ということは不可能で、0を除外した16個の要素のうち半分が平方数、 残りの半分が非平方数だ。実際、上の結果から、0は別にして、1, 2, 4, 8, 9, 13, 15, 16 の8個が平方数である。 法が7でなくても①と同様の式は成り立つので、かたっぱしから調べるにしても法の半分までで止めて良い。

ここで、与えられた整数 a が b を法として平方数になるかならないか、ちからまかせに調べる関数をとりあえず作っておく。

function test( a, b ) {
    a %= b;
    for( var i=0; i <= b/2; i++ ) {
        if( i*i % b === a ) return "R";
    }
    return "N";
}

この関数は、与えられた2数 a, b について、a R b なら "R" を返し、 a N b なら "N" を返す。

交換法則が成り立つか

与えられた2つの数 a, b が、a R b であるか a N b であるか。 つまり、a は平方数 (mod b) であるかどうか。 あとから説明するように、a, b はともに3以上の素数と仮定して良い。 それ以外の場合も、3以上の素数の計算に帰着させられるからだ。

a, b を3以上の素数として、a R b なのか a N b なのか一覧表を作ってみよう。 とりあえず20未満の範囲で実行する。

var Primes = [ 3, 5, 7, 11, 13, 17, 19 ];

d.write("<table>");
for( var i = 0; i < Primes.length; i++ ) {
    var a = Primes[i];
    d.write("<tr>");
    for( var j = 0; j < Primes.length; j++ ) {
        var b = Primes[j];
        if(test(a,b)=="R") d.write( "<td style='background:#cff'>" + a + "R" + b + "</td>");
        else d.write( "<td style='background:#fcc'>" + a + "N" + b + "</td>");
    }
    d.write("<\/tr>\n");
}
d.write("<\/table>");
3R33N53N73R113R133N173N19
5N35R55N75R115N135N175R19
7R37N57R77N117N137N177R19
11N311R511R711R1111N1311N1711R19
13R313N513N713N1113R1313R1713N19
17N317N517N717N1117R1317R1717R19
19R319R519N719N1119N1319R1719R19

この表を観察すると、左上から右下への対角線にそって、だいたい対称になっている。 a R b なら b R a 、a N b なら b N a であることが多いようだが、多少、例外もある。 この問題をハッキリさせるため、次の形式で表を出力してみる。

var Primes = [ 3, 5, 7, 11, 13, 17, 19 ];

d.write("<table>");
for( var i = 0; i < Primes.length; i++ ) {
    var a = Primes[i];
    for( var j = 0; j < i; j++ ) {
        d.write("<tr>");
        var b = Primes[j];
        if(test(a,b)=="R") d.write( "<td style='background:#cff'>" + a + "R" + b + "</td>");
        else d.write( "<td style='background:#fcc'>" + a + "N" + b + "</td>");

        if(test(b,a)=="R") d.write( "<td style='background:#cff'>" + b + "R" + a + "</td>");
        else d.write( "<td style='background:#fcc'>" + b + "N" + a + "</td>");

        d.write("<\/tr>\n");
    }
}
d.write("<\/table>");
5N33N5
7R33N7
7N55N7
11N33R11
11R55R11
11R77N11
13R33R13
13N55N13
13N77N13
13N1111N13
17N33N17
17N55N17
17N77N17
17N1111N17
17R1313R17
19R33N19
19R55R19
19N77R19
19N1111R19
19N1313N19
19R1717R19

(7, 3), (11, 7), (19, 3), (19, 7), (19, 11) の組み合わせでは、 式の2つの数字を入れ替えると R か N か?の性質が変わる。 これらの数が入っていても、(7, 5) や (13, 7) は問題なく交換できている。 同じ素数でも、5, 13, 17 が入っている場合は交換法則が成り立ち、3, 7, 11, 19 同士では成り立たない。 いま、5, 13, 17 を「バニラ素数」と呼び、 3, 7, 11, 19 を「チョコレート素数」と呼ぶと、

交換できない、といっても、では予想がつかない結果になるのか?というと、そうではなく、 ここで「交換できない」という意味は、a R b なら b N a になり、a N b なら b R a になるということ、 つまり R と N が正確に入れ替わることを意味している。

4で割って1余る素数、4で割って3余る素数

5, 13, 17, ... のような「バニラ素数」の正体は、4で割って1余る素数であり、 3, 7, 11, 19, ... の「チョコレート素数」は4で割って3余る素数だ。 (素数なので4で割れば必ず余りが出る。2を除外して奇数を考えているので、4で割って2余ることはなく、必ず1か3余る。) 目で見て分かりやすくするために、バニラ素数とチョコレート素数を区別して表示させてみよう。

var d = document;
function display( a, b ) {
    var test1 = test( a, b );
    var test2 = test( b, a );
    var A = flavor( a );
    var B = flavor( b );

    if( test1 === "R" ) {
        d.write('<td style="background:#cff">' + A + 'R' + B + '<\/td>');
    } else {
        d.write('<td style="background:#fcc">' + A + 'N' + B + '<\/td>');
    }

    if( test2 === "R" ) {
        d.write('<td style="background:#cff">' + B + 'R' + A + '<\/td>');
    } else {
        d.write('<td style="background:#fcc">' + B + 'N' + A + '<\/td>');
    }

    if( test1 === test2 ) {
        d.write('<td style="background:#fff; color:green">入れ替えても同じ<\/td>');
    } else {
        d.write('<td style="background:#ffd; color:red; font-weight:bold">入れ替えると逆転<\/td>');
    }

    if( a % 4 === 1 || b % 4 === 1 ) {
        d.write('<td style="background:#fff; color:blue">バニラを含む<\/td>');
    } else {
        d.write('<td style="background:#ffd; color:maroon; font-weight:bold">チョコレート同士<\/td>');
    }
}
function flavor( n ) {
    if( n % 4 === 1 ) return '<em style="color:blue; background:white">' + n + '<\/em>';
    else return '<strong style="color:maroon">' + n + '<\/strong>';
}

var Primes = [ 3, 5, 7, 11, 13, 17, 19, 23, 29 ];

d.write('<table>');
d.write('<tr><th>元の式<\/th><th>入れ替えた式<\/th><th>R か N か<\/th><th>式の内容<\/th><\/tr>\n');
for( var i = 0; i < Primes.length; i++ ) {
    var a = Primes[i];
    for( var j = 0; j < i; j++ ) {
        d.write("<tr>");
        var b = Primes[j];
        display( a, b );
        d.write("<\/tr>\n");
    }
}
d.write("<\/table>");
元の式入れ替えた式R か N か式の内容
5N33N5入れ替えても同じバニラを含む
7R33N7入れ替えると逆転チョコレート同士
7N55N7入れ替えても同じバニラを含む
11N33R11入れ替えると逆転チョコレート同士
11R55R11入れ替えても同じバニラを含む
11R77N11入れ替えると逆転チョコレート同士
13R33R13入れ替えても同じバニラを含む
13N55N13入れ替えても同じバニラを含む
13N77N13入れ替えても同じバニラを含む
13N1111N13入れ替えても同じバニラを含む
17N33N17入れ替えても同じバニラを含む
17N55N17入れ替えても同じバニラを含む
17N77N17入れ替えても同じバニラを含む
17N1111N17入れ替えても同じバニラを含む
17R1313R17入れ替えても同じバニラを含む
19R33N19入れ替えると逆転チョコレート同士
19R55R19入れ替えても同じバニラを含む
19N77R19入れ替えると逆転チョコレート同士
19N1111R19入れ替えると逆転チョコレート同士
19N1313N19入れ替えても同じバニラを含む
19R1717R19入れ替えても同じバニラを含む
23N33R23入れ替えると逆転チョコレート同士
23N55N23入れ替えても同じバニラを含む
23R77N23入れ替えると逆転チョコレート同士
23R1111N23入れ替えると逆転チョコレート同士
23R1313R23入れ替えても同じバニラを含む
23N1717N23入れ替えても同じバニラを含む
23R1919N23入れ替えると逆転チョコレート同士
29N33N29入れ替えても同じバニラを含む
29R55R29入れ替えても同じバニラを含む
29R77R29入れ替えても同じバニラを含む
29N1111N29入れ替えても同じバニラを含む
29R1313R29入れ替えても同じバニラを含む
29N1717N29入れ替えても同じバニラを含む
29N1919N29入れ替えても同じバニラを含む
29R2323R29入れ替えても同じバニラを含む

バニラ素数同士や、バニラ素数とチョコレート素数は、ひっくり返しにしても R ないし N の性質は変わらないが、 チョコレート素数同士の場合、ひっくり返しにすると R だったものは N に、N だったものは R に変わる。 以上が「平方剰余の相互法則」の内容だ。

今回のまとめ

2つの素数 p, q について、
x2 ≡ p (mod q) …… ①
が解を持つかどうか?は、ひっくり返した
x2 ≡ q (mod p) …… ②
が解を持つかどうか?と神秘的な関係にある。

すなわち、p, q が両方とも ≡3 (mod 4) 型の素数であるときに限って、 一方にのみ解があり、他方には解がない。 p または q の少なくともどちらか一方が ≡1 (mod 4) 型の素数であれば、 ①と②はどちらも解を持つか、または、どちらも解を持たない。

例題

x2 ≡ 3 (mod 23977) …… ① には解があるか?

答: 3はチョコレート素数だが、もう一方の数23977は4で割ると1余り、バニラ味だ。 したがってひっくり返しても判定結果は変わらない。
x2 ≡ 23977 (mod 3) …… ② には解があるか?

23977≡1 (mod 3) だから、要するに
x2 ≡ 1 (mod 3) には解があるか?
と尋ねている。ということは ② には x = 1 という解があるので、①にも解がある。

ちなみに、①の具体的な解は 6033であり、60332 = 36397089 を 23977 で割ると3余る。 ソロベイ・ストラッセン・テストによる素数性判定では、①の形の式を実際に解く必要はなく、単に解があるかないかだけ知りたい。 したがって泥臭い数値計算をする必要はなく、今回説明した平方剰余の相互法則と、次回以降に説明するヤコビ記号の性質によって、 高速に判定を実行できる。 なお、両方とも4で割って3余る形の数でも、 計算上、支障はない。 その場合、ひっくり返すと平方数か平方数でないか?の性質が入れ替わる。

この記事のURL

テキスト版省パケ版XML版



webmaster@faireal.net