Merkle-Hellmanナップサック暗号

[かずま]

このトピックは、格納からの続きです。
ライトニングさんが「C で　MH暗号を作れ」という課題を出され、
かずまが、Wikipediaの Merkle-Hellmanナップサック暗号 をコーディングしたものです。
以下、次のプログラムをもとに MH暗号について議論します。

コード:

#include <stdio.h>    // cin, cout
#include <stdlib.h>   // rand, srand
#include <time.h>     // time
 
#define N  12
 
int gcd(int a, int b)    // 最大公約数
{
    int r;
    while (b != 0)
        r = a % b, a = b, b = r;
    return a;
}
 
int inverse(int a, int b)  // b を法とする整数の合同における a の逆元
{
    int x1 = 1, y1 = 0, z1 = a, x2 = 0, y2 = 1, z2 = b, q, t;
    while (z2 > 1)
        #define STEP(a, b)  (t = a - q * b, a = b, b = t)
        q = z1 / z2, STEP(x1, x2), STEP(y1, y2), STEP(z1, z2);
    return x2 < 0 ? x2 + b : x2;
}
 
void print_array(const char *name, const int *a, int n) // 配列の表示
{
    printf("%s = [", name);
    for (int i = 0; i < n; i++) printf(" %d", a[i]);
    printf(" ]\n");
}
 
void print_bin(const char *name, const int *a, int n) // 配列の表示
{
    printf("%s = [ ", name);
    for (int i = 0; i < n; i++) printf("%d", a[i]);
    printf(" ]\n");
}
 
int input_data(int *a)  // データの入力
{
    char buf[256];  int i;

    printf("\nEnter less than %d binary digits\n", N);
    if (!fgets(buf, sizeof buf, stdin)) return 0;
    for (i = 0; i < N; i++)
        if (buf[i] == '1') a[i] = 1;
        else if (buf[i] == '0') a[i] = 0;
        else break;
    return i;  // ビット数を返す
}
 
void generate_keys(int *b, int *w, int *q, int *r)  // 鍵の生成
{
    int sum;
    sum = 0;
    for (int i = 0; i < N; i++)               // 超増加列(秘密鍵 w)の生成
        sum += w[i] = sum + 1 + rand() % 10;
    print_array("  w", w, N);
    printf("  sum = %d\n", sum);
    *q = sum + 1 + rand() % 10;                        // 秘密鍵 q の生成
    for (*r = *q / 2; gcd(*r, *q) != 1; ++*r) ;        // 秘密鍵 r の生成
    for (int i = 0; i < N; i++) b[i] = *r * w[i] % *q; // 公開鍵 b の生成
}
 
int encrypt(int n, const int *a, const int *b)  // 暗号化
{
    int c = 0, i;
    for (i = 0; i < n; i++)
        if (a[i] == 1) c += b[i];
    return c;
}
 
int decrypt(int n, int c, const int *w, int q, int r, int *s)  // 復号
{
    int i, sum = c * inverse(r, q) % q;
    for (i = n; --i >= 0; )
        if (sum < w[i]) s[i] = 0;
        else sum -= w[i], s[i] = 1;
    return sum != 0; // 復号できれば 0、そうでなければ 1 を返す
}
 
int main(void)
{
    int w[N], q, r;  // 秘密鍵
    int b[N];        // 公開鍵
    int a[N];  // 暗号化する前のデータ
    int c;     // 暗号化されたデータ
    int s[N];  // 復号されたデータ
    int n;     // ビット数
 
    srand(time(0));
    generate_keys(b, w, &q, &r); // 鍵の生成
    printf("Private key\n");
    print_array("  w", w, N);
    printf("  q = %d\n  r = %d\n", q, r);
    printf("Public key\n");
    print_array("  b", b, N);
 
    while (n = input_data(a)) {    // データの入力
        print_bin("  a", a, n);        // 入力データの表示
        c = encrypt(n, a, b);          // 暗号化
        printf("  c = %d\n", c);       // 暗号化されたデータの表示
        decrypt(n, c, w, q, r, s);     // 復号
        print_bin("  s", s, n);        // 復号されたデータの表示
    }
    return 0;
}

実行例

コード:

  w = [ 8 15 32 65 126 250 504 1010 2012 4032 8059 16117 ]
  sum = 32230
Private key
  w = [ 8 15 32 65 126 250 504 1010 2012 4032 8059 16117 ]
  q = 32240
  r = 16121
Public key
  b = [ 8 16135 32 16185 126 250 504 1010 2012 4032 24179 32237 ]

Enter less than 12 binary digits
101011001111
  a = [ 101011001111 ]
  c = 62876
  s = [ 101011001111 ]

Enter less than 12 binary digits
111
  a = [ 111 ]
  c = 16175
  s = [ 111 ]

Enter less than 12 binary digits
1010110011
  a = [ 1010110011 ]
  c = 6460
  s = [ 1010110011 ]

Enter less than 12 binary digits
.

[ライトニング]

わざわざトピックたてありがとうございます。

NTLの質問こちらでしていいでしょうか？

コード:

  w = [ 9 15 27 55 109 221 439 881 1760 3525 ... ]
  sum = 7041
Private key
  w = [ 9 15 27 55 109 221 439 881 1760 3525 ... ]
  q = 7046
  r = 3525
Public key
  b = [ 3541 3553 3577 3633 3741 3965 4401 5285 3520 3527 ... ]

Enter less than 10 binary digits
1010101010
  a = [ ]
  c = 0
  s = [ ]

Enter less than 10 binary digits

かずまさんのNTLのプログラムをとりあえずNを１０にしてやってみたのですがこのようになってしまいました。なぜでしょうか？

[かずま]

NTLの質問こちらでしていいでしょうか？

ここは、MH暗号のトピックです。

NTL の質問をするなら、NTL とは何か、MH暗号との関係は何かなどを
ちゃんと説明してからにしてください。

かずまさんのNTLのプログラムをとりあえずNを１０にしてやってみたのですがこのようになってしまいました。なぜでしょうか？

新しいトピックなので、どのプログラムかわかりません。
リンクでなく、そのプログラムをここに貼り付けてください。

また、どんな環境で、どんなコマンドでプログラムをコンパイルし、
実行したのかなど、できるだけ詳しく報告してください。

環境とは、Linux か Windows の cygwin かなどです。

[ライトニング]

NTLとは大きな桁数を持つ数同士の演算を行うためのC++ライブラリです。
MH暗号は１００bit以上ないと安全ではないと言われているので
C言語だとbit数が足りないのでNTlというライブラリを使い新たな変数を使い大きい値でも実行できるようにします

かずまさんが書いたNo1のプログラムをNTLになおしたものです

コード:

#include <iostream>  // cin, cout
#include <cstdlib>   // rand, srand
#include <ctime>     // time
#include <NTL/ZZ.h>
 
using namespace std;
using namespace NTL;
 
#define N  10
 
ZZ gcd(ZZ a, ZZ b)    // 最大公約数
{
    ZZ r;
    while (b != 0)
        r = a % b, a = b, b = r;
    return a;
}
 
ZZ inverse(ZZ a, ZZ b)  // b を法とする整数の合同における a の逆元
{
    ZZ x1, y1, z1 = a, x2, y2, z2 = b, q, t;
    x1 = 1, y1 = 0, x2 = 0, y2 = 1;
    while (z2 > 1)
        #define STEP(a, b)  (t = a - q * b, a = b, b = t)
        q = z1 / z2, STEP(x1, x2), STEP(y1, y2), STEP(z1, z2);
    return x2 < 0 ? x2 + b : x2;
}
 
void print_array(const char *name, const ZZ *a, int n) // 配列の表示
{
    cout << name << " = [";
    if (n > 10) n = 10;
    for (int i = 0; i < n; i++) cout << ' ' << a[i];
    cout << " ... ]\n";
}
 
void print_bin(const char *name, const int *a, int n) // 配列の表示
{
    cout << name << " = [";
    for (int i = 0; i < n; i++) cout << a[i];
    cout << " ]\n";
}
 
int input_data(int *a)  // データの入力
{
    string buf;
    cout << "\nEnter less than " << N << " binary digits\n";
    if (!getline(cin, buf)) return 0;
    size_t i, n = buf.size();
    if (n >= N) return 0;
    for (i = 0; i < n; i++)
        if (buf[i] == '1') a[i] = 1;
        else if (buf[i] == '0') a[i] = 0;
        else break;
    if (i != n) return 0;
    return n;  // ビット数を返す
}
 
void generate_keys(ZZ *b, ZZ *w, ZZ& q, ZZ& r)  // 鍵の生成
{
    ZZ sum;
    sum = 0;
    for (int i = 0; i < N; i++)  // 超増加列(秘密鍵)の生成
        sum += w[i] = sum + 1 + rand() % 10;
    print_array("  w", w, N);
    cout << "  sum = " << sum << endl;
    q = sum + 1 + rand() % 10;  // 秘密鍵 q の生成
    for (r = q / 2; gcd(r, q) != 1; ++r) ;  // 秘密鍵 r の生成
    for (int i = 0; i < N; i++)  // 公開鍵の生成
        b[i] = r * w[i] % q;
}
 
ZZ encrypt(int n, const int *a, const ZZ *b)  // 暗号化
{
    ZZ c;
    c = 0;
    for (int i = 0; i < n; i++)
        if (a[i] == 1) c += b[i];
    return c;
}
 
int decrypt(int n, ZZ c, const ZZ *w, ZZ q, ZZ r, int *s)  // 復号
{
    ZZ sum = c * inverse(r, q) % q;
    for (int i = n; --i >= 0; ) {
        if (sum >= w[i])
            sum -= w[i], s[i] = 1;
        else
            s[i] = 0;
    }
    return sum != 0; // 復号できれば 0、そうでなければ 1 を返す
}
 
int main(void)
{
    ZZ w[N], q, r;  // 秘密鍵
    ZZ b[N];        // 公開鍵
    int a[N];  // 暗号化する前のデータ
    ZZ c;      // 暗号化されたデータ
    int s[N];  // 復号されたデータ
    int n;     // ビット数
 
    srand(time(0));
    generate_keys(b, w, q, r); // 鍵の生成
    cout << "Private key\n";
    print_array("  w", w, N);
    cout << "  q = " << q << "\n  r = " << r << endl;
    cout << "Public key\n";
    print_array("  b", b, N);
 
    while (n == input_data(a)) {    // データの入力
        print_bin("  a", a, n);        // 入力データの表示
        c = encrypt(n, a, b);          // 暗号化
        cout << "  c = " << c << endl; // 暗号化されたデータの表示
        decrypt(n, c, w, q, r, s);     // 復号
        print_bin("  s", s, n);        // 復号されたデータの表示
    }
    return 0;
}

[\code]
これをiMacのEmacsで作りターミナルで
g++ -o ntltest ntltest.cpp -lntl -lgmpg++ -o ntltest ntltest.cpp -lntl -lgmp
ように実行した所No2のような実行結果になってしまいました。
どのように治せばいいか分からない状態です。

[かずま]

かずまさんが書いたNo1のプログラムをNTLになおしたものです
　　:
これをiMacのEmacsで作りターミナルで
g++ -o ntltest ntltest.cpp -lntl -lgmpg++ -o ntltest ntltest.cpp -lntl -lgmp
ように実行した所No2のような実行結果になってしまいました。
どのように治せばいいか分からない状態です。

このトピックの No.1 のプログラムは C のプログラムです。
NTL を使う C++ プログラムによく変更できたなあ、と思ったら、
前のトピック、格納の No.89 のプログラムを 2行だけ修正したものでした。
ちゃんと事実を書かないと、バグの原因は追求できませんよ。
変更箇所は
9行目 #define N 128 を #define N 10 に、
111行目 while (n = input_data(a)) { の = を == に。
なぜ、そういう変更をするんですか？

codeタグの使い方も、コマンドラインの
g++ -o ntltest ntltest.cpp -lntl -lgmpg++ -o ntltest ntltest.cpp -lntl -lgmp
も間違っています。

[ライトニング]

すみません言葉足らずでした。
かずまさんが書いた格納のNo.89のプログラムを実行したのですが
実行画面で128ビットをうてばいいのかわならなかったので
とりあえず低い値の10ビットをでやってみようと思いビット変えるなら NUM 128を変えれば良いとお聞きしたので 128を10に変更しました
そしたらNo.2のような結果になってしまいました
111行目の部分は何故変更されてたのか自分も分からず治してそのまま実行しました。

コードは
g++ −o ntltest ntltest.cpp −lntl −lgmp
./ntltest
で実行しました

[ライトニング]

すみません言葉足らずでした。
かずまさんが書いた格納のNo.89のプログラムを実行したのですが
実行画面で128ビットをうてばいいのかわならなかったので
とりあえず低い値の10ビットをでやってみようと思いビット変えるなら NUM 128を変えれば良いとお聞きしたので 128を10に変更しました
そしたらNo.2のような結果になってしまいました
111行目の部分は何故変更されてたのか自分も分からず治してそのまま実行しました。

コードは
g++ −o ntltest ntltest.cpp −lntl −lgmp
./ntltest
で実行しました

[かずま]

肝心なことを書くのを忘れていました。

No.1 のプログラムも 前のトピックの No.89のプログラムも
input_data() は N ビット未満の 2進数値を受け付けます。
Nビット入力してしまうと、エラーになり 0 を返します。
Nビット未満だと、そのビット数を返します。
n = input_data(a) で入力されたビット数を n に代入して、
暗号化、復号処理を行います。
n == input_data(a) にすると、初期化されていない n に たまたま
0 が入っていて、input_data(a) が返す 0 と等しかったので、
0ビットの暗号化、復号を処理して、No.2 の結果になったんだと
思います。
No.89 の実行例でも分かるように入力するビット数は N 未満なら
何ビットでもかまいません。

[ライトニング]

Nビット以下の二進数を入力しても何も表示されず実行が終わってしまうのですが
それは何故でしょうか？

[かずま]

Nビット以下の二進数を入力しても何も表示されず実行が終わってしまうのですが
それは何故でしょうか？

N はいくつにしましたか？
== は = に戻しましたか？
コンパイルしなおしましたか？
具体的にどういう 2進数を入力しましたか？
何も表示されずにというのは No.2 とは異なるということですか？

[ライトニング]

コード:

 w = [ 5 15 22 47 95 185 374 745 1492 2988 ... ]
  sum = 7395495711181278755917080807353
Private key
  w = [ 5 15 22 47 95 185 374 745 1492 2988 ... ]
  q = 7395495711181278755917080807357
  r = 3697747855590639377958540403678
Public key
  b = [ 3697747855590639377958540403676 3697747855590639377958540403671 7395495711181278755917080807346 3697747855590639377958540403655 3697747855590639377958540403631 3697747855590639377958540403586 7395495711181278755917080807170 3697747855590639377958540403306 7395495711181278755917080806611 7395495711181278755917080805863 ... ]

Enter less than 100 binary digits
111110000000000

Nを１０や１２８になどどの値にしてもこれで実行が終わってしまいます。
＝＝は戻しました
コンパイルは何度もやり直しました。

[かずま]

Nを１０や１２８になどどの値にしてもこれで実行が終わってしまいます。
＝＝は戻しました
コンパイルは何度もやり直しました。

そのコンパイルしたソースを貼ってください

[ライトニング]

$ g++ -o mhtest mhtest.cpp -lntl -lgmp
$ ./mhtest

このようにコンパイルしました

[かずま]

120行くらいのソースプログラムを貼ってください。
こちらでコンパイルしてみるので。

[ライトニング]

コード:

#include <iostream>  // cin, cout
#include <cstdlib>   // rand, srand
#include <ctime>     // time
#include <NTL/ZZ.h>
 
using namespace std;
using namespace NTL;
 
#define N  10
 
ZZ gcd(ZZ a, ZZ b)    // 最大公約数
{
    ZZ r;
    while (b != 0)
        r = a % b, a = b, b = r;
    return a;
}
 
ZZ inverse(ZZ a, ZZ b)  // b を法とする整数の合同における a の逆元
{
    ZZ x1, y1, z1 = a, x2, y2, z2 = b, q, t;
    x1 = 1, y1 = 0, x2 = 0, y2 = 1;
    while (z2 > 1)
        #define STEP(a, b)  (t = a - q * b, a = b, b = t)
        q = z1 / z2, STEP(x1, x2), STEP(y1, y2), STEP(z1, z2);
    return x2 < 0 ? x2 + b : x2;
}
 
void print_array(const char *name, const ZZ *a, int n) // 配列の表示
{
    cout << name << " = [";
    if (n > 10) n = 10;
    for (int i = 0; i < n; i++) cout << ' ' << a[i];
    cout << " ... ]\n";
}
 
void print_bin(const char *name, const int *a, int n) // 配列の表示
{
    cout << name << " = [";
    for (int i = 0; i < n; i++) cout << a[i];
    cout << " ]\n";
}
 
int input_data(int *a)  // データの入力
{
    string buf;
    cout << "\nEnter less than " << N << " binary digits\n";
    if (!getline(cin, buf)) return 0;
    size_t i, n = buf.size();
    if (n >= N) return 0;
    for (i = 0; i < n; i++)
        if (buf[i] == '1') a[i] = 1;
        else if (buf[i] == '0') a[i] = 0;
        else break;
    if (i != n) return 0;
    return n;  // ビット数を返す
}
 
void generate_keys(ZZ *b, ZZ *w, ZZ& q, ZZ& r)  // 鍵の生成
{
    ZZ sum;
    sum = 0;
    for (int i = 0; i < N; i++)  // 超増加列(秘密鍵)の生成
        sum += w[i] = sum + 1 + rand() % 10;
    print_array("  w", w, N);
    cout << "  sum = " << sum << endl;
    q = sum + 1 + rand() % 10;  // 秘密鍵 q の生成
    for (r = q / 2; gcd(r, q) != 1; ++r) ;  // 秘密鍵 r の生成
    for (int i = 0; i < N; i++)  // 公開鍵の生成
        b[i] = r * w[i] % q;
}
 
ZZ encrypt(int n, const int *a, const ZZ *b)  // 暗号化
{
    ZZ c;
    c = 0;
    for (int i = 0; i < n; i++)
        if (a[i] == 1) c += b[i];
    return c;
}
 
int decrypt(int n, ZZ c, const ZZ *w, ZZ q, ZZ r, int *s)  // 復号
{
    ZZ sum = c * inverse(r, q) % q;
    for (int i = n; --i >= 0; ) {
        if (sum >= w[i])
            sum -= w[i], s[i] = 1;
        else
            s[i] = 0;
    }
    return sum != 0; // 復号できれば 0、そうでなければ 1 を返す
}
 
int main(void)
{
    ZZ w[N], q, r;  // 秘密鍵
    ZZ b[N];        // 公開鍵
    int a[N];  // 暗号化する前のデータ
    ZZ c;      // 暗号化されたデータ
    int s[N];  // 復号されたデータ
    int n;     // ビット数
 
    srand(time(0));
    generate_keys(b, w, q, r); // 鍵の生成
    cout << "Private key\n";
    print_array("  w", w, N);
    cout << "  q = " << q << "\n  r = " << r << endl;
    cout << "Public key\n";
    print_array("  b", b, N);
 
    while (n == input_data(a)) {    // データの入力
        print_bin("  a", a, n);        // 入力データの表示
        c = encrypt(n, a, b);          // 暗号化
        cout << "  c = " << c << endl; // 暗号化されたデータの表示
        decrypt(n, c, w, q, r, s);     // 復号
        print_bin("  s", s, n);        // 復号されたデータの表示
    }
    return 0;
}

これでいいでしょうか？

[かずま]

コード:

    while (n == input_data(a)) {    // データの入力

これでいいでしょうか？

== は駄目。

[ライトニング]

コード:

 
while (n = input_data(a)) {    // データの入力
             ^
             ==

にするとこのようになるので==にしたのですがダメでしょうか？

[ライトニング]

コード:

mhtest.cpp:111:14: note: use '==' to turn this assignment into an equality
      comparison
    while (n = input_data(a)) {    // データの入力
             ^
             ==

抜けてましたこのようなエラーでした

[かずま]

コード:

mhtest.cpp:111:14: note: use '==' to turn this assignment into an equality
      comparison
    while (n = input_data(a)) {    // データの入力
             ^
             ==

抜けてましたこのようなエラーでした

error ではありません。
note となっているだけでしょう。
while の括弧の中だから、ひょっとして == と書くつもりが
間違って = と書いたのじゃありませんか？
と注意しているだけです。

では、
while ((n = input_data(a)) != 0) {
にしてください。

[ライトニング]

intで宣言してるnなどは32bit以上使うことがないからintで宣言しているのでしょうか？

[かずま]

intで宣言してるnなどは32bit以上使うことがないからintで宣言しているのでしょうか？

自分で int を ZZ に変えてコンパイルしてみれば分かるはずですが？

コード:

    for (int i = 0; i < n; i++) cout << a[i];

配列の添え字に ZZ は使えません。だから i は int。
それと比較する n も int。
1 と 0 だけを入れる a[N] と s[N] は、ZZ にできるけど、int で十分。
なんなら char にしてもいいくらいです。char は 1バイトの整数です。

[ライトニング]

ありがとうございます。色々と疑問点が分かる事が出来ました。


最後にかずまさんに見て欲しいファイルがあるのですがここでは少し
見せれない理由があるので
こちらがスカイプIDか何かを教えるので見て頂く事は可能でしょうか？

もしこういった事を聞くのが規約違反などかずまさんが
不快に思われたり面倒臭いなら無視して頂いて結構です。
困っているのでもしよろしければよろしくお願いします。