（役に立つか分かりませんがDSAサンプルコードをVS2010形式のプロジェクトで全部まとめて掲載しました。p,q,gを出すところは無いけどｗ）
（LibTomMathを使って任意精度整数を扱う方法はこちらに記載）
（DSA署名の概要はこちらに記載）
まずGenerator(署名付けモジュール)を作りますが、さらにその前に鍵を作っておきます。
DSA鍵の元(p, q, g) を決めます。「大きな素数pと素因数qを求め、mod p の世界で q 乗して初めて 1 になる数 g を探します。」何言ってるのか分かりません。でも大丈夫。DSAはJavaに実装されているのがあるので鍵を決めるところまではJavaを使えば出来ます。
public static void main(String[] args) { try { // KeyPairGeneratorの初期化 KeyPairGenerator keygen = KeyPairGenerator.getInstance("DSA"); SecureRandom random = new SecureRandom(); keygen.initialize(1024, random); // 鍵の生成 KeyPair keys = keygen.generateKeyPair(); PublicKey pubkey = keys.getPublic(); System.out.println(pubkey.toString()); } catch (Exception ex) { ex.printStackTrace(); } }で実行するとDSAの元（p,q,g）とyがダーッと表示されます（実行する度に新しく作られます）。yは公開鍵ですが、対応する秘密鍵xを表示させる方法が分からなかったので秘密鍵xと公開鍵yは作り直します。
p,q,gをディファインしましょう。
#define DSA_P "fd7f53811d75122952df4a9c2eece4e7f611b7523cef4400c31e3f80b65126694\ 55d402251fb593d8d58fabfc5f5ba30f6cb9b556cd7813b801d346ff26660b76b9950a5a49f9fe80\ 47b1022c24fbba9d7feb7c61bf83b57e7c6a8a6150f04fb83f6d3c51ec3023554135a169132f675f\ 3ae2b61d72aeff22203199dd14801c7" #define DSA_Q "9760508f15230bccb292b982a2eb840bf0581cf5" #define DSA_G "f7e1a085d69b3ddecbbcab5c36b857b97994afbbfa3aea82f9574c0b3d0782675\ 159578ebad4594fe67107108180b449167123e84c281613b7cf09328cc8a6e13c167a8b547c8d28e\ 0a3ae1e2bb3a675916ea37f0bfa213562f1fb627a01243bcca4f1bea8519089a883dfe15ae59f069\ 28b665e807b552564014c3bfecf492a"な感じ。折り返さなくても良いです。
秘密鍵は適当に決めて、（p,q,g,x）から公開鍵を作ります。
void Generator::generateKey() { mp_int p, q, g, y, x; mp_init(&p); mp_init(&q); mp_init(&g); mp_init(&y); mp_init(&x); mp_read_radix(&p, DSA_P, 16); mp_read_radix(&q, DSA_Q, 16); mp_read_radix(&g, DSA_G, 16); /*秘密鍵・公開鍵を作ります x を 0 < x < q で選んで秘密鍵とする y = (g^x) mod p を公開鍵とする*/ //秘密鍵xを選ぶ : qより小さければ良い(自由に決める） char x_str[] = "1234567890abcdef1234567890abcdef"; mp_read_radix(&x, x_str, 16); //y = (g^x) mod p mp_exptmod(&g, &x, &p, &y); char anschar[1000]; mp_tohex(&x, anschar); std::cout << "#define DSA_X \"" << anschar << "\"" << std::endl; mp_tohex(&y, anschar); std::cout << "#define DSA_Y \"" << anschar << "\"" << std::endl; }yを求める式でgのx乗が出てきます。これが引っ掛かったところで、累乗はLibTomMathの関数にありません。累乗はさすがに数が大きくなり過ぎるからなんでしょうか。代わりにmodと合わされたmp_exptmod関数があります。関数の説明には 「d = a**b (mod c)」とあります。累乗は「＾」で表すと思ってたので探すのに手間取りましたが「y = g**x(mod p)」でぴったりはまります。これを実行すると秘密鍵x、公開鍵yが出力されるのでディファインしておきます（もちろんxはもっとそれらしいランダム値が良いでしょう）。
#define DSA_X "1234567890ABCDEF1234567890ABCDEF" #define DSA_Y "9C878080D754D4C044D96E96CE68593D6C7F765881BF372609ADECE0216C6C294\ 4EC96A418242C212EEE6C2EBC666B81AE21E61F5107F91AF496C7CF508B419EED933A9EA505707AE\ C3740BB6FC27E23A4ABD937AA694EB6F798EDA867B272550D3AA90730039BDFAFC4CB2192D2A2F7C\ 2046758E7FEBD8EC61302DFCA8944F1"さて鍵が全部決まりました。
ここまでが準備で、ここからが署名付けの処理になります。
最初に平文からハッシュ値を計算します。平文は数値でないので、計算するにしても平文から数値に変換することが必要です。その数値に対して署名を計算するのです。もちろん平文と数値は１対１でなければなりません。というわけで平文からSHA1のハッシュ値を計算します（平文から数値に変換するのにSHA1を使う、というのもDSA署名の決まりです）。
SHA1はRFC文書のSHA1にC言語のコードが載っていますのでそれをそのまま使います。実際はバイナリ値で出るのでそれを16進数文字列に変換する関数を追加しました。この辺は省略します（実際のコードはこんな感じ、最後にコッソリと関数が追加されてますｗ）。
//平文のHash値を求める mp_int z; mp_init(&z); char buf[SHA1HashSize * 2 + 1]; SHA1GenerateHash(hira_bun.c_str(), buf); mp_read_radix(&z, buf, 16);平文はstringのhira_bunに入っているとします。SHA1GenerateHashでbufに16進文字列でハッシュ値が入るとして、zに代入します。
//DSAの元や鍵を読込む mp_int p, q, g, x; mp_init(&p); mp_init(&q); mp_init(&g); mp_init(&x); mp_read_radix(&p, DSA_P, 16); mp_read_radix(&q, DSA_Q, 16); mp_read_radix(&g, DSA_G, 16); mp_read_radix(&x, DSA_X, 16);元や鍵を全部読込みます（公開鍵yは使いません）。
/*ｒ、ｓを求める r = (g^k mod p) mod q s = k^(-1) (z + x r) mod q (kは0以外のランダムな数字） */ mp_int r, s, k, zero; mp_init(&r); mp_init(&s); mp_init(&k); mp_init(&zero); mp_int t1, t2, t3; mp_init(&t1); mp_init(&t2); mp_init(&t3); mp_zero(&r); mp_zero(&s); mp_zero(&zero); while (mp_cmp(&r, &zero) == 0 || mp_cmp(&s, &zero) == 0) { //kを選ぶ (ランダム、のつもり・・) srand((unsigned)clock()); int k_int = rand() + 1; mp_set_int(&k, k_int); //r = (g^k mod p) mod q mp_exptmod(&g, &k, &p, &t1); mp_mod(&t1, &q, &r); //s = k^(-1) (z + x r) mod q mp_mul(&x, &r, &t1); mp_add(&z, &t1, &t2); mp_invmod(&k, &q, &t3); mp_mul(&t2, &t3, &s); }署名ｒ、ｓを求めるのですが、kというパラメータがいきなり出てきます。 0 < k < q の中でランダムで決めて良いようです。intで適当に決めています（もっと大きな数の方が良いのかもしれません）。Whileループはkの決め方によってｒかｓが0になってしまう場合があるようなのでその場合はｋを選ぶところからやり直すようになっています。大抵は1回で通るのであまり気にしません。
ｒを求める式に「(gk mod p)」があります。鍵を求めるのと同様にmp_exptmodを使います。
ｓを求める式は「s = k-1 (z + x r) mod q」です。（ｚ＋ｘｒ）は先に計算するので問題ありません。t3に代入しておきます。問題は次の「 k-1 t3 mod q」です。ｋのマイナス１乗ですがｋで割り算するとうまくいきません。この式に対応する、mp_invmodがあり、関数の説明は「c = 1/a (mod b)」となっています。ぴったり当てはまります。
どうもこういった計算をプログラムに置き換えるにはexptmodだのinvmodだのの関数を知ってるかどうかが重要で、これさえ知っていれば順番に式を当てはめて行けば出来そうです。
これで署名は全部揃いました。
秘密鍵のxと平文のハッシュ値z以外をstd::mapで返すことにします(簡単なので)。
//署名を戻り値にセット。 std::map<char, std::string> map; char anschar[1000]; map['p'] = DSA_P; map['q'] = DSA_Q; map['g'] = DSA_G; mp_tohex(&r, anschar); map['r'] = anschar; mp_tohex(&s, anschar); map['s'] = anschar; map['y'] = DSA_Y; return map;適当なプログラムですがデバッグで見てみるとこうなります。
鍵を作る関数と、平文を与えると署名の入ったmapが返ってくる、という関数だけで良いです。（本当は（p,q,g）も作るようにしたいですが…）
次はVerifier(署名確認モジュール)です。
Verifierはシンプルに署名の入ったmapと平文を与えるとTRUEかFALSE（１か０）が返ってくる関数だけです。まずmapからmp_intに読込みます。
mp_int p, q, g, y, r, s; mp_init(&p); mp_init(&q); mp_init(&g); mp_init(&y); mp_init(&r); mp_init(&s); mp_read_radix(&p, map['p'].c_str(), 16); mp_read_radix(&q, map['q'].c_str(), 16); mp_read_radix(&g, map['g'].c_str(), 16); mp_read_radix(&y, map['y'].c_str(), 16); mp_read_radix(&r, map['r'].c_str(), 16); mp_read_radix(&s, map['s'].c_str(), 16);平文からSHA1のハッシュ値を求めます。
//平文のHash値を求める mp_int z; mp_init(&z); char buf[SHA1HashSize * 2 + 1]; SHA1GenerateHash(hira_bun.c_str(), buf); mp_read_radix(&z, buf, 16);当然全く同じコードです。で、署名の正当性チェックですが、「((gz yr)(s-1) mod p) mod q = r」が成立するかどうか、だそうです。累乗が沢山あるしこれはさすがに厄介です。
そこで作ったのが以下のコードです。
mp_int w, v; mp_init(&w); mp_init(&v); mp_invmod(&s, &q, &w); // generate W generateV(&v, &y, &p, &q, &g, &w, &r, &z); if (mp_cmp(&r, &v) == 0) { return TRUE; } else { return FALSE; }中のgenerateV関数は↓です。
void Verifier::generateV(mp_int* v, mp_int* y, mp_int* p, mp_int* q, mp_int* g, mp_int* w, mp_int* r, mp_int* z) { mp_int u1, u2, u3, u4, t1, t2, t3, t4; mp_init(&u1); mp_init(&u2); mp_init(&u3); mp_init(&u4); mp_init(&t1); mp_init(&t2); mp_init(&t3); mp_init(&t4); mp_mul(z, w, &u1); mp_mod(&u1, q, &u2); // remainderの代わり mp_mul(r, w, &u3); mp_mod(&u3, q, &u4); // remainderの代わり mp_exptmod(g, &u2, p, &t1); mp_exptmod(y, &u4, p, &t2); mp_mul(&t1, &t2, &t3); mp_mod(&t3, p, &t4); // remainderの代わり mp_mod(&t4, q, v); // remainderの代わり mp_clear(&u1); mp_clear(&u2); mp_clear(&u3); mp_clear(&u4); mp_clear(&t1); mp_clear(&t2); mp_clear(&t3); mp_clear(&t4); }Q:これは何？さっきの式がどうしてこうなるの？
A:どうしてそういうこと聞くの？（´・ω・`）
というわけでgenerateVを行うとvに先ほどの式の結果が代入されますのでrと比較し、同値ならTRUE、違うならFALSEを返します。
上記コードはJavaのDSA署名のチェックコードをそのままC++に置き換えたのでイマイチ説明できません（generateWとgenerateVに分かれれるのもそのせいです）。もちろん、掛け算、mod演算、invmod演算、exptmod演算だけでやってるので式をよーく変形すれば出来るのでしょう（近くの数学の得意そうな人に聞けばきっと喜んで説明してくれると思います）。コード中でremainderの代わり、と書いてあるのはJavaではreminder関数を使っていますが、LibTomMathには無かったのでmodで代用しました、と言うメモです。要は割り算の余りが分かれば良いらしいので問題無いでしょう。
動かしてみれば分かりますがこれで立派に平文と署名の正当性チェックは出来ます。ズルしようが何しようが動くコードを入手するのが最優先なのです。コードパクるのは最後の手段だけどね。
サンプルコードのプロジェクトはSAMPLE/SAMPLE.cppがメインです。出力とかもしないのでDebug実行して値を確認する用です。
署名はサンプルコード内では16進文字列でやりとりしていますが、実際はDSA暗号であることも隠すため、ちょこっと暗号化して付加します。数は全部2倍しておくとか、決まった数を足しておくとか、それをZip圧縮してBase64でエンコードするとか、GeneratorとVerifierで示し合わせて簡単には署名や元が取り出せないような暗号化です。DSAと組み合わさると強力です。
また、サンプルはmapに署名と鍵全部の情報を入れましたが署名はｒとｓだけで、（p,q,g,y）はどのファイルでも変わらないのでVerifierに埋め込んじゃっても良いと思います。
もちろんGeneratorは切り離して作り、間違って外に出さないことが必要です。
あとVerifierを分かり易い名前で外部DLLにすると、せっかく頑張ったのに必ずTRUEを返す偽DLLに差し替えられるとかのハック手段があるかも知れません。正しい認証のためには正しい公開鍵を使って正しいモジュールで計算して認証する、という前提が必要です。
0 件のコメント:
コメントを投稿