2008年11月2日(更新)
2001年12月14日(公開)
このページはライター橋本晋之介の著作を紹介しています。また、本文や付属プログラムの誤りの訂正、よくあるご質問に対する回答などを掲載しています。
2008年11月2日
訂正等を追加しました。
2002年8月12日
ZDNetの報道によると確定的素数判定法の決定的なアルゴリズムが開発されたようです。同ページから論文のPDFファイルがリンクされています。このアルゴリズムについての評価に関する情報がありましたら橋本までお教え下さい。
2003年2月20日現在、訂正が9点あります。
| 書名 | RSA 暗号技術の基礎からC++による実装まで |
|---|---|
| 著者 | 橋本晋之介（はしもと しんのすけ） |
| 発行 | ソフトバンクパブリッシング |
| 発行日 | 2001年12月27日 |
| ページ数 | 211ページ |
| 価格 | 2,600円 |
| ISBN | 4-7973-1702-7 |
| 内容 | 暗号技術の基礎の解説。RSA暗号のサンプルプログラム付属。全ソースコード解説。CD-ROM付属（数値計算クラスライブラリ、RSA鍵生成/暗号化/復号化） |
| 目次 |
|
印刷・発行後に発見された誤りなどについて報告します。読者の皆様にお詫びいたします。また、ご連絡・ご指摘を下さった皆様にお礼を申し上げます。
読者から「23は素数」とのご指摘をいただきました。その通りです。失礼いたしました。
// 試験数36個 9, 15, 21, 23, 25は素数ではない 他は素数
// 試験数36個 9, 15, 21, 25は素数ではない 他は素数
サンプルプログラムはVC++ 6.0で開発していますので、当時のANSI C++に準拠しています。VC++ .NET 2003は標準C++準拠ですので、名前空間の扱いが変更されています。以下の通り修正してください。
#include <iostream> //<iostream.h>から変更 #include <iomanip> //追加 using namespace std; //追加
#include <iostream> //<iostream.h>から変更 using namespace std; //追加
#include <iostream> //<iostream.h>から変更 using namespace std; //追加
読者より訂正内容に誤りがあるとの指摘がありました。
CMPI gcd()において、本文では仮引数がconst & 宣言されていますが、付属CD-ROMのソースではconst & 宣言がありません。
付属CD-ROMのソースが正しいです。const & 宣言すると関数内で代入ができません。本文を訂正してください。
CMPI gcd( // 結果
const CMPI& a, // 演算数1
const CMPI& b ) // 演算数2
{
:
:
}
CMPI gcd( // 結果
CMPI a, // 演算数1
CMPI b ) // 演算数2
{
:
:
}
暗号文を他の復号化プログラムに渡したところ、正常に復号化できないとのご指摘がありました。その方が調べたところ、CMPI::CMPI( const u_short* vi, const int li )で数値の格納語順が逆なためだとのご指摘を頂きました。
このコンストラクタは与えられたメモリ領域をそのまま使用しています。本サンプルプログラムでは暗号化・復号化の両方で同じ仕組みを使っているので問題ありませんが、一方に他のプログラムを使用される場合は、メッセージの構成などについて詳細に整合性を取る必要があります。この点説明が不十分でしたので、ここに記します。
他のプログラムと連携させる場合、RFC2440（付属CD-ROMにも収録）が参考になります。
読者から指摘がありました。添え字の範囲を示す定数の使い方が誤っていました。また、結果の取り出しと繰り上がり処理が本文と異なっていました。さらに、スペースの使い方でうまく表示できていない部分があることをご指摘いただきました。 以下の通り再訂正します。
for( l = 0; l < m; l++ )
c[l] = 0; // 結果の初期化
for( i = 0; i < n; i++ ){ // bの各桁について
k = 0; //繰り上がりの初期化
for(j = 0; j < m; j++){ // aの各桁について
s = a[j] * b[i] + c[i+j] +k; // (*1)
c[i+j] = s % UNIT; // i+j桁目の結果(*2)
k = s / UNIT; // 繰り上がり
}
c[i+m] = k; // 繰り上がり
}
*:UNITは基数。10進数ならUNITの値は10
for( l = 0; l < n+m-1; l++ )
c[l] = 0; // 結果の初期化
for( i = 0; i < m; i++ ){ // bの各桁について 訂正：m <- n
k = 0; //繰り上がりの初期化
for(j = 0; j < n; j++){ // aの各桁について 訂正：n <- m
s = a[j] * b[i] + c[i+j] +k; // (*1)
c[i+j] = s & MASK; // i+j桁目の結果(*2) 訂正：(& MASK) <- (% UNIT)
k = s >> LENGTH; // 繰り上がり(*3) 訂正：(>> LENGTH) <- (/ UNIT)
}
c[i+m] = k; // 繰り上がり
}
*2: MASKは1桁分を取り出すためのマスク 訂正
*3: LENGTHは1桁分のビット数 追加
読者から指摘がありました。本文とソースが矛盾していますが、本文が正しいです。ソースを以下の通り訂正します。
z[i] = UNIT - a[i] - t; // (*)
z[i] = UNIT + a[i] - t; // (*)
読者から「Release構成でメモリアクセスエラーが発生する」とのご指摘を頂きました。ご指摘の通り、要求メモリサイズが1桁分足りませんでした。以下の通り訂正します。付属CD-ROMのソースも修正してください。
ce = (char*)new( char[e.getMaxColumn()*4+1] ); cd = (char*)new( char[d.getMaxColumn()*4+1] ); cn = (char*)new( char[n.getMaxColumn()*4+1] );
ce = (char*)new( char[ (e.getMaxColumn()+1) *4+1] ); cd = (char*)new( char[ (d.getMaxColumn()+1) *4+1] ); cn = (char*)new( char[ (n.getMaxColumn()+1) *4+1] );
読者から「判定の範囲は3からその数の半分ではなくその数の平方根までで十分」とのご指摘を頂きました。また、「奇数で割るよりも素数で割った方が能率的」とのご指摘も頂きました。確かにその通りです。以下の通り訂正します。
理屈では、3からその数の半分までの奇数で割ってみて、余りが0なものが1つでもあれば素数ではありません。しかし、除算は速度の遅い計算ですし、256ビットで表せる数の半分とは2の256乗個もあります。繰り返し回数が多すぎてこの判定方法は使えません。
理屈では、3からその数の平方根までの既知の素数で割ってみて、余りが0なものが1つでもあれば素数ではありません。しかし、除算は速度の遅い計算ですし、256ビットで表せる数の平方根とは2の128乗個もあります。繰り返し回数が多すぎますし、それだけの素数表を作っておくこともたいへんです。この判定方法は使えません。
読者から「1は素数ではない」とのご指摘をいただきました。その通りです。失礼いたしました。
1,2,3,5,7,11などの数が素数です。
2,3,5,7,11などの数が素数です。
「素数の数」について読者からのご指摘を頂きました。参考文献(2)の「暗号理論入門」のP.15にも書かれていました。失礼しました。
素数が無限に存在するかどうかは証明されていませんが、経験的に無限に存在するといわれています。
素数は無限に存在することが証明されています。
上記のご指摘に伴い、ソースの一部を訂正します。お手数ですが、付属ソースプログラムを修正してください。
if ( n == 0 ) return 0; // 0は素数ではない if ( n == 1 || n == 2 ) return 1; // 1,2は素数
if ( n == 0 || n == 1 ) return 0; // 0,1は素数ではない if ( n == 2 ) return 1; // 2は素数
このページはフリーライター橋本晋之介（はしもとしんのすけ）が運営しています。
他にも誤りなどがあれば、お手数ですがご連絡ください。よろしくお願いいたします。
トップページに戻る