課題

ライトニング · #1

何度もトピック投稿申し訳ないです。以前質問させて頂いたＭＨ暗号の応用なのですが
どうしても来週中に作らないといけないプログラムがあるのですが
詳細は貼ってある画像のものを作らないといけないですが

C言語でつくり、それをNTLというＣ＋＋のライブラリを使って作らないとだめなのですが

これに書いてあるアルゴリズム通り作っていったらいいと言われたのですが全くどういうアルゴリズムが分からない状態です。

どたなか分かる方教えていただけないでしょうか？

[

ライトニング · #2

http://www.fastpic.jp/viewer.php?file=0230557220.jpg
http://www.fastpic.jp/viewer.php?file=5849045876.jpg
http://www.fastpic.jp/viewer.php?file=6496563589.jpg

すみません画像がうまくはれていませんでした。

ライトニング · #3

コード:

#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 *a,int *z,int *x,int *y,int *j)  // 鍵の生成
{
    int sum;
    sum = 0;
    for (int i = 0; i < N; i++)               // 超増加列の生成
        sum += w[i] = sum + 1 + rand() % 10;
int sum1;
sum1=0;
 
    for (x[0] = i = 1; i < N; i++)　　　//奇数シフト数列の作成
        x[i] = 2 * a[i-1];
 
    for (sum = i = 0; i < N; i++) {
        int t = sum + rand() % 10 + 1;
        sum += y[i] = (t & 1) ? t : ++t;
	{
    for (j = N, i = 0; i < N; i++)
        z[i] = x[i] * y[--j];

    double d=pow(2.0,N);
　　w[i]=w[i]*d+z[i];

    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, a, x, y, z, &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)) != 0) {     // データの入力
        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;
}

Emacsのgcc -oでコンパイルしてるのですが。

上記に貼った画像と作りたものが少し違うのですがとりあえず鍵の生成の部分でてこづっているのですが
超増加列のwに奇数シフト数列cと２のN乗を掛け合わせたものを足しあわて、暗号化行いたいのですが
うまくいかない状態です。どなたかアドバイスお願いします。

ライトニング · #4

コード:

 
#include <stdio.h>    // cin, cout
#include <stdlib.h>   // rand, srand
#include <time.h>     // time
#include <limits.h>

#define N  6
#define NN 12
#define PLUS 6
#define BINARY_DIGIT 32

int gcd(int a, int b)    // 最大公約数
{
    int r;
    while (b != 0)
        r = a % b, a = b, b = r;
    return a;
}

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");
}

int bitcount(unsigned long n)
{
    int c = 0;

    while (n) {
        ++c;
        n = n >> 1;
    }

    return c;
}

void DtoB(int decimal_number, char binary_number[]) {
  int i;
  for (i = BINARY_DIGIT - 1; i >= 0; i--) {
    binary_number[i] = (decimal_number >> i) & 1;
  }
}

void generate_keys(int *b, int *w, int *q, int *r, int *z, int *y, int *s)  // 鍵の生成
{
  int sum = 0;
  int i, j;
  int bit[NN + PLUS];
  char binary_number[BINARY_DIGIT] = {0}; /* テスト */

  srand((unsigned)time(NULL));

  /* SO: 1   SI: 0 */
  int SOSI_FLAG[NN];
  for (i = 0; i < NN; i++) {
    SOSI_FLAG[i] = i % 2;
  }

  /* 2の等比数列 */
  for (bit[0] = i = 1; i < NN + PLUS; i++)
    bit[i] = 2 * bit[i-1];
  int X = bit[NN + PLUS - 1];

  /******************/
  /* 奇数シフト数列 */
  /******************/
  for (sum = i = 0; i < N; i++) {
    int t = sum + rand() % 10 + 1;
    sum += y[i] = (t & 1) ? t : ++t;
  }
  
  /* テスト */
  printf("奇数シフト\n");
  /* テスト */

  for (i = 0, j = N - 1; i < N; i++, j--) {
    z[i] = y[i] * bit[j];

    /* テスト */
    DtoB(z[i], binary_number);
    for (int k = BINARY_DIGIT - 1; k >= 0; k--) {
      printf("%d", binary_number[k]);
    }
    printf("\n");
    /* テスト */
    
  }

  /* テスト */
  printf("MH数列\n");
  /* テスト */

  int randnum;
  int SO_count = 0;
  sum = 0;
  /* SO: 1   SI: 0 */
  for (i = 0; i < NN; i++) {
    if (SOSI_FLAG[i] == 0) {
      /* SI */
      randnum = rand() % y[SO_count];
      randnum = randnum * bit[N - 1 - SO_count];
      sum += w[i] = sum + 1 + rand() % 10; // 超増加
      s[i] = randnum * X + w[i];

      /* テスト */
      DtoB(s[i], binary_number);
      for (int k = BINARY_DIGIT - 1; k >= 0; k--) {
	printf("%d", binary_number[k]);
      }
      printf("\n");
      /* テスト */

    } else {
      /* SO */
      sum += w[i] = sum + 1 + rand() % 10; // 超増加
      s[i] = z[SO_count] * X + w[i];
      SO_count++;

      /* テスト */
      DtoB(s[i], binary_number);
      for (int k = BINARY_DIGIT - 1; k >= 0; k--) {
	printf("%d", binary_number[k]);
      }
      printf("\n");
      /* テスト */
    }
  }

  *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 * s[i] % *q; // 公開鍵 b の生成
  

}

int main(int argc, char* argv[]) {
  if (argc != 1) {
    fprintf(stderr, "usage: %s\n", argv[0]);
    exit(EXIT_FAILURE);
  }

  int y[N], z[N], w[N];
  int s[NN];  // 秘密鍵
  int q, r;  // 秘密鍵
  int b[N];        // 公開鍵
  
  generate_keys(b, w, &q, &r, z, y, s); // 鍵の生成

  print_array("  w", w, NN);
  print_array("  z", z, N);
  print_array("  s", s, NN);
  printf("  q = %d\n  r = %d\n", q, r);
  print_array("  b", b,N);

  return 0;
}

なんとかsは作れたのですが
公開鍵のbを作って実行してみたところ変な値になるのですが原因がわからない状態です...連投申し訳ないのですがアドバイスお願いします...

かずま · #5

SOSI が何か分かりません。
[Generation of SOSI] のアルゴリズムで、A と B と L(i) が何か分かりません。
[Decryption with SOSI] があるのに [Encryption with SOSI] がないので、
暗号化方法が分かりません。
変なプログラムが示され、やっぱり何のことか分かりませんでした。

件名も「課題」という、他のトピックとは区別のできない不適切なものでした。

だから、この問題は放置していました。

でも、[Decryption with SOSI] をよく見てみると、
M が暗号文で、X と alpha と beta が秘密鍵らしいと気づいたので、
A, B, L(i) を適当に決めて、アルゴリズムの通りにコーディングしてみました。

コード:

#include <stdio.h>   // printf, fgets, stdin
#include <stdlib.h>  // srand, rand

#define N 10

void print_array(const char *name, const int *a, int n)
{
    int i;
    printf("  %s = [ %d", name, a[0]);
    for (i = 1; i < n; i++) printf(" %d", a[i]);
    printf(" ]\n");
}

int input_data(int *d)
{
    int i;
    char buf[256];
    printf(">> ");
    if (!fgets(buf, sizeof buf, stdin)) return 0;
    for (i = 0; i < N && (buf[i] == '1' || buf[i] == '0'); i++)
        d[i] = buf[i] - '0';
    return i;
}

int generate_keys(int *a, int *b, int *s)
{
    int i = N - 1;
    int X = a[i] = rand() % 10 + 10;
    while (--i >= 0)
        if (i & 1)
            X += a[i] = X - 1 - rand() % 10;
        else 
            X += a[i] = X + 1 + rand() % 10;
    X += 1 + rand() % 10;
    for (b[0] = i = 1; i < N; i++)
        b[i] = b[i-1] * 2;
    for (i = 0; i < N; i++)
        s[i] = b[i] * X + a[i];
    return X;
}

int encrypt(const int *d, int *s, int n)
{
    int M = 0, i;
    for (i = 0; i < n; i++)
        if (d[i]) M += s[i];
    return M;
}

void decrypt(int M, int X, const int *a, const int *b, int *m, int n)
{
    int i, Q = M / X, R = M % X;

    for (i = 0; i < n; i++)
        if (i % 1)
            if (R >= a[i])
                m[i] = 1, R -= a[i], Q -= b[i];
            else
                m[i] = 0;
        else
            if (Q % (1 << i+1) == 1 << i)
                m[i] = 1, R -= a[i], Q -= b[i];
            else
                m[i] = 0;
}

int main(void)
{
    int a[N], b[N], X;  // 秘密鍵
    int s[N];   // 公開鍵
    int d[N];   // 入力データ
    int n;      // 入力ビット長
    int M;      // 暗号化データ
    int m[N];   // 復号データ

    X = generate_keys(a, b, s);
    print_array("a", a, N);
    print_array("b", b, N);
    print_array("s", s, N);
    printf("  X = %d\n", X);
        
    while ((n = input_data(d))) {
        printf("  n = %d\n", n);
        print_array("d", d, n);
        M = encrypt(d, s, n);
        printf("  M = %d\n", M);
        decrypt(M, X, a, b, m, n);
        print_array("m", m, n);
    }
    return 0;
}

想像で書いたので、これが正しいプログラムかどうか分かりません。

かずま · #6

55行目の if (i % 1) は if (i & 1) の間違いでした。

間違いでも、正しいような結果がなぜ出たのかが分かりません。
やっぱりこのプログラム自体が間違っているようです。取り消します。

ライトニング · #7

SOが超増加数列で　SIが奇数シフト数列でそれ合わせたのがSOSIという状況です
A B L(i)は自分もあまり理解できていない状況で暗号化はMH暗号と一緒の状態です

コード:

#include <stdio.h>    // cin, cout
#include <stdlib.h>   // rand, srand
#include <time.h>     // time
#include <limits.h>

#define N  6
#define NN 12
#define PLUS 6
#define BINARY_DIGIT 32

int gcd(int a, int b)    // 最大公約数
{
    int r;
    while (b != 0)
        r = a % b, a = b, b = r;
    return a;
}

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");
}


int input_data(int *a)  // データの入力
{
    char buf[256];  int i;
 
    printf("\nEnter less than %d binary digits\n", NN);
    if (!fgets(buf, sizeof buf, stdin)) return 0;
    for (i = 0; i < NN; i++)
        if (buf[i] == '1') a[i] = 1;
        else if (buf[i] == '0') a[i] = 0;
        else break;
    return i;  // ビット数を返す
}
 

int bitcount(unsigned long n)
{
    int c = 0;

    while (n) {
        ++c;
        n = n >> 1;
    }

    return c;
}

void DtoB(int decimal_number, char binary_number[]) {
  int i;
  for (i = BINARY_DIGIT - 1; i >= 0; i--) {
    binary_number[i] = (decimal_number >> i) & 1;
  }
}

void generate_keys(int *b, int *w, int *q, int *r, int *z, int *y, int *s)  // 鍵の生成
{
  int sum = 0;
  int i, j;
  int bit[NN + PLUS];
  char binary_number[BINARY_DIGIT] = {0}; /* テスト */

  srand((unsigned)time(NULL));

  /* SO: 1   SI: 0 */
  int SOSI_FLAG[NN];
  for (i = 0; i < NN; i++) {
    SOSI_FLAG[i] = i % 2;
  }

  /* 2の等比数列 */
  for (bit[0] = i = 1; i < NN + PLUS; i++)
    bit[i] = 2 * bit[i-1];
  int X = bit[NN + PLUS - 1];

  /******************/
  /* 奇数シフト数列 */
  /******************/
  for (sum = i = 0; i < N; i++) {
    int t = sum + rand() % 10 + 1;
    sum += y[i] = (t & 1) ? t : ++t;
  }
  
  /* テスト */
  printf("奇数シフト\n");
  /* テスト */

  for (i = 0, j = N - 1; i < N; i++, j--) {
    z[i] = y[i] * bit[j];

    /* テスト */
    DtoB(z[i], binary_number);
    for (int k = BINARY_DIGIT - 1; k >= 0; k--) {
      printf("%d", binary_number[k]);
    }
    printf("\n");
    /* テスト */
    
  }

  /* テスト */
  printf("MH数列\n");
  /* テスト */

  int randnum;
  int SO_count = 0;
  sum = 0;
  /* SO: 1   SI: 0 */
  for (i = 0; i < NN; i++) {
    if (SOSI_FLAG[i] == 0) {
      /* SI */
      randnum = rand() % y[SO_count];
      randnum = randnum * bit[N - 1 - SO_count];
      sum += w[i] = sum + 1 + rand() % 10; // 超増加
      s[i] = randnum * X + w[i];

      /* テスト */
      DtoB(s[i], binary_number);
      for (int k = BINARY_DIGIT - 1; k >= 0; k--) {
	printf("%d", binary_number[k]);
      }
      printf("\n");
      /* テスト */

    } else {
      /* SO */
      sum += w[i] = sum + 1 + rand() % 10; // 超増加
      s[i] = z[SO_count] * X + w[i];
      SO_count++;

      /* テスト */
      DtoB(s[i], binary_number);
      for (int k = BINARY_DIGIT - 1; k >= 0; k--) {
	printf("%d", binary_number[k]);
      }
      printf("\n");
      /* テスト */
    }
  }
  sum += s[i] = sum + 1 + rand() % 10;
  *q = sum + 1 + rand() % 10;                        // 秘密鍵 q の生成
  for (*r = *q / 2; gcd(*r, *q) != 1; ++*r) ;        // 秘密鍵 r の生成
  for (int i = 0; i < NN; i++) b[i] = *r * s[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 =c+b[i];
    return c;
#include <stdio.h>    // cin, cout
#include <stdlib.h>   // rand, srand
#include <time.h>     // time
#include <limits.h>

#define N  6
#define NN 12
#define PLUS 6
#define BINARY_DIGIT 32

int gcd(int a, int b)    // 最大公約数
{
    int r;
    while (b != 0)
        r = a % b, a = b, b = r;
    return a;
}

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");
}


int input_data(int *a)  // データの入力
{
    char buf[256];  int i;
 
    printf("\nEnter less than %d binary digits\n", NN);
    if (!fgets(buf, sizeof buf, stdin)) return 0;
    for (i = 0; i < NN; i++)
        if (buf[i] == '1') a[i] = 1;
        else if (buf[i] == '0') a[i] = 0;
        else break;
    return i;  // ビット数を返す
}
 

int bitcount(unsigned long n)
{
    int c = 0;

    while (n) {
        ++c;
        n = n >> 1;
    }

    return c;
}

void DtoB(int decimal_number, char binary_number[]) {
  int i;
  for (i = BINARY_DIGIT - 1; i >= 0; i--) {
    binary_number[i] = (decimal_number >> i) & 1;
  }
}

void generate_keys(int *b, int *w, int *q, int *r, int *z, int *y, int *s)  // 鍵の生成
{
  int sum = 0;
  int i, j;
  int bit[NN + PLUS];
  char binary_number[BINARY_DIGIT] = {0}; /* テスト */

  srand((unsigned)time(NULL));

  /* SO: 1   SI: 0 */
  int SOSI_FLAG[NN];
  for (i = 0; i < NN; i++) {
    SOSI_FLAG[i] = i % 2;
  }

  /* 2の等比数列 */
  for (bit[0] = i = 1; i < NN + PLUS; i++)
    bit[i] = 2 * bit[i-1];
  int X = bit[NN + PLUS - 1];

  /******************/
  /* 奇数シフト数列 */
  /******************/
  for (sum = i = 0; i < N; i++) {
    int t = sum + rand() % 10 + 1;
    sum += y[i] = (t & 1) ? t : ++t;
  }
  
  /* テスト */
  printf("奇数シフト\n");
  /* テスト */

  for (i = 0, j = N - 1; i < N; i++, j--) {
    z[i] = y[i] * bit[j];

    /* テスト */
    DtoB(z[i], binary_number);
    for (int k = BINARY_DIGIT - 1; k >= 0; k--) {
      printf("%d", binary_number[k]);
    }
    printf("\n");
    /* テスト */
    
  }

  /* テスト */
  printf("MH数列\n");
  /* テスト */

  int randnum;
  int SO_count = 0;
  sum = 0;
  /* SO: 1   SI: 0 */
  for (i = 0; i < NN; i++) {
    if (SOSI_FLAG[i] == 0) {
      /* SI */
      randnum = rand() % y[SO_count];
      randnum = randnum * bit[N - 1 - SO_count];
      sum += w[i] = sum + 1 + rand() % 10; // 超増加
      s[i] = randnum * X + w[i];

      /* テスト */
      DtoB(s[i], binary_number);
      for (int k = BINARY_DIGIT - 1; k >= 0; k--) {
	printf("%d", binary_number[k]);
      }
      printf("\n");
      /* テスト */

    } else {
      /* SO */
      sum += w[i] = sum + 1 + rand() % 10; // 超増加
      s[i] = z[SO_count] * X + w[i];
      SO_count++;

      /* テスト */
      DtoB(s[i], binary_number);
      for (int k = BINARY_DIGIT - 1; k >= 0; k--) {
	printf("%d", binary_number[k]);
      }
      printf("\n");
      /* テスト */
    }
  }
  sum += s[i] = sum + 1 + rand() % 10;
  *q = sum + 1 + rand() % 10;                        // 秘密鍵 q の生成
  for (*r = *q / 2; gcd(*r, *q) != 1; ++*r) ;        // 秘密鍵 r の生成
  for (int i = 0; i < NN; i++) b[i] = *r * s[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 =c+b[i];
    return c;

}

   
int main(void)
{

  int y[N], z[N], w[N];
  int s[NN];  // 秘密鍵
  int q, r;  // 秘密鍵
  int b[N];        // 公開鍵
  int a[N];  // 暗号化する前のデータ
  int c;     // 暗号化されたデータ
  int n;     // ビット数

   srand(time(0));
  generate_keys(b, w, &q, &r, z, y, s); // 鍵の生成
  print_array("  w", w, NN);
  print_array("  z", z, N);
  print_array("  s", s, NN);
  printf("  q = %d\n  r = %d\n", q, r);
  print_array("  b", b,NN);

   
while ((n = input_data(a)) != 0) {     // データの入力
        print_array("  a", a, n);        // 入力データの表示
        c = encrypt(n, a, b);          // 暗号化
        printf("  c = %d\n", c);       // 暗号化されたデータの表示
  }

  return 0;
}

}

   
int main(void)
{

  int y[N], z[N], w[N];
  int s[NN];  // 秘密鍵
  int q, r;  // 秘密鍵
  int b[N];        // 公開鍵
  int a[N];  // 暗号化する前のデータ
  int c;     // 暗号化されたデータ
  int n;     // ビット数

   srand(time(0));
  generate_keys(b, w, &q, &r, z, y, s); // 鍵の生成
  print_array("  w", w, NN);
  print_array("  z", z, N);
  print_array("  s", s, NN);
  printf("  q = %d\n  r = %d\n", q, r);
  print_array("  b", b,NN);

   
while ((n = input_data(a)) != 0) {     // データの入力
        print_array("  a", a, n);        // 入力データの表示
        c = encrypt(n, a, b);          // 暗号化
        printf("  c = %d\n", c);       // 暗号化されたデータの表示
  }

  return 0;
}

とりあえずコンパイルは通ったのですがbの公開鍵の値がおかしくなる状態です。
値あふれが原因かと思ってるのですが今一わからない状態です。

ライトニング · #8

コード:


#include <stdio.h>    // cin, cout
#include <stdlib.h>   // rand, srand
#include <time.h>     // time
#include <limits.h>

#define N  6
#define NN 12
#define PLUS 6
#define BINARY_DIGIT 32

int gcd(int a, int b)    // 最大公約数
{
    int r;
    while (b != 0)
        r = a % b, a = b, b = r;
    return a;
}

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");
}


int input_data(int *a)  // データの入力
{
    char buf[256];  int i;
 
    printf("\nEnter less than %d binary digits\n", NN);
    if (!fgets(buf, sizeof buf, stdin)) return 0;
    for (i = 0; i < NN; i++)
        if (buf[i] == '1') a[i] = 1;
        else if (buf[i] == '0') a[i] = 0;
        else break;
    return i;  // ビット数を返す
}
 

int bitcount(unsigned long n)
{
    int c = 0;

    while (n) {
        ++c;
        n = n >> 1;
    }

    return c;
}

void DtoB(int decimal_number, char binary_number[]) {
  int i;
  for (i = BINARY_DIGIT - 1; i >= 0; i--) {
    binary_number[i] = (decimal_number >> i) & 1;
  }
}

void generate_keys(int *b, int *w, int *q, int *r, int *z, int *y, int *s)  // 鍵の生成
{
  int sum = 0;
  int i, j;
  int bit[NN + PLUS];
  char binary_number[BINARY_DIGIT] = {0}; /* テスト */

  srand((unsigned)time(NULL));

  /* SO: 1   SI: 0 */
  int SOSI_FLAG[NN];
  for (i = 0; i < NN; i++) {
    SOSI_FLAG[i] = i % 2;
  }

  /* 2の等比数列 */
  for (bit[0] = i = 1; i < NN + PLUS; i++)
    bit[i] = 2 * bit[i-1];
  int X = bit[NN + PLUS - 1];

  /******************/
  /* 奇数シフト数列 */
  /******************/
  for (sum = i = 0; i < N; i++) {
    int t = sum + rand() % 10 + 1;
    sum += y[i] = (t & 1) ? t : ++t;
  }
  
  /* テスト */
  printf("奇数シフト\n");
  /* テスト */

  for (i = 0, j = N - 1; i < N; i++, j--) {
    z[i] = y[i] * bit[j];

    /* テスト */
    DtoB(z[i], binary_number);
    for (int k = BINARY_DIGIT - 1; k >= 0; k--) {
      printf("%d", binary_number[k]);
    }
    printf("\n");
    /* テスト */
    
  }

  /* テスト */
  printf("MH数列\n");
  /* テスト */

  int randnum;
  int SO_count = 0;
  sum = 0;
  /* SO: 1   SI: 0 */
  for (i = 0; i < NN; i++) {
    if (SOSI_FLAG[i] == 0) {
      /* SI */
      randnum = rand() % y[SO_count];
      randnum = randnum * bit[N - 1 - SO_count];
      sum += w[i] = sum + 1 + rand() % 10; // 超増加
      s[i] = randnum * X + w[i];

      /* テスト */
      DtoB(s[i], binary_number);
      for (int k = BINARY_DIGIT - 1; k >= 0; k--) {
	printf("%d", binary_number[k]);
      }
      printf("\n");
      /* テスト */

    } else {
      /* SO */
      sum += w[i] = sum + 1 + rand() % 10; // 超増加
      s[i] = z[SO_count] * X + w[i];
      SO_count++;

      /* テスト */
      DtoB(s[i], binary_number);
      for (int k = BINARY_DIGIT - 1; k >= 0; k--) {
	printf("%d", binary_number[k]);
      }
      printf("\n");
      /* テスト */
    }
  }
  sum += s[i] = sum + 1 + rand() % 10;
  *q = sum + 1 + rand() % 10;                        // 秘密鍵 q の生成
  for (*r = *q / 2; gcd(*r, *q) != 1; ++*r) ;        // 秘密鍵 r の生成
  for (int i = 0; i < NN; i++) b[i] = *r * s[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 =c+b[i];
    return c;

}

   
int main(void)
{

  int y[N], z[N], w[N];
  int s[NN];  // 秘密鍵
  int q, r;  // 秘密鍵
  int b[N];        // 公開鍵
  int a[N];  // 暗号化する前のデータ
  int c;     // 暗号化されたデータ
  int n;     // ビット数

   srand(time(0));
  generate_keys(b, w, &q, &r, z, y, s); // 鍵の生成
  print_array("  w", w, NN);
  print_array("  z", z, N);
  print_array("  s", s, NN);
  printf("  q = %d\n  r = %d\n", q, r);
  print_array("  b", b,NN);

   
while ((n = input_data(a)) != 0) {     // データの入力
        print_array("  a", a, n);        // 入力データの表示
        c = encrypt(n, a, b);          // 暗号化
        printf("  c = %d\n", c);       // 暗号化されたデータの表示
  }

  return 0;
}

すみませんソースを少し間違ってましたこっちです

ライトニング · #9

コード:

 
#include <stdio.h>    // cin, cout
#include <stdlib.h>   // rand, srand
#include <time.h>     // time
#include <limits.h>

#define N  6
#define NN 12
#define PLUS 6
#define BINARY_DIGIT 32

int gcd(int a, int b)    // 最大公約数
{
    int r;
    while (b != 0)
        r = a % b, a = b, b = r;
    return a;
}

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");
}

int bitcount(unsigned long n)
{
    int c = 0;

    while (n) {
        ++c;
        n = n >> 1;
    }

    return c;
}

int input_data(int *a)  // データの入力
{
    char buf[256];  int i;
 
    printf("\nEnter less than %d binary digits\n", NN);
    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 DtoB(int decimal_number, char binary_number[]) {
  int i;
  for (i = BINARY_DIGIT - 1; i >= 0; i--) {
    binary_number[i] = (decimal_number >> i) & 1;
  }
}

void generate_keys(int *b, int *w, int *q, int *r, int *z, int *y, int *s)  // 鍵の生成
{
  int sum = 0;
  int i, j;
  int bit[NN + PLUS];
  char binary_number[BINARY_DIGIT] = {0}; /* テスト */

  srand((unsigned)time(NULL));

  /* SO: 1   SI: 0 */
  int SOSI_FLAG[NN];
  for (i = 0; i < NN; i++) {
    SOSI_FLAG[i] = i % 2;
  }

  /* 2の等比数列 */
  for (bit[0] = i = 1; i < NN + PLUS; i++)
    bit[i] = 2 * bit[i-1];
  int X = bit[NN + PLUS - 1];

  /******************/
  /* 奇数シフト数列 */
  /******************/
  for (sum = i = 0; i < N; i++) {
    int t = sum + rand() % 10 + 1;
    sum += y[i] = (t & 1) ? t : ++t;
  }
  
  /* テスト */
  printf("奇数シフト\n");
  /* テスト */

  for (i = 0, j = N - 1; i < N; i++, j--) {
    z[i] = y[i] * bit[j];

    /* テスト */
    DtoB(z[i], binary_number);
    for (int k = BINARY_DIGIT - 1; k >= 0; k--) {
      printf("%d", binary_number[k]);
    }
    printf("\n");
    /* テスト */
    
  }

  /* テスト */
  printf("MH数列\n");
  /* テスト */

  int randnum;
  int SO_count = 0;
  sum = 0;
  /* SO: 1   SI: 0 */
  for (i = 0; i < NN; i++) {
    if (SOSI_FLAG[i] == 0) {
      /* SI */
      randnum = rand() % y[SO_count];
      randnum = randnum * bit[N - 1 - SO_count];
      sum += w[i] = sum + 1 + rand() % 10; // 超増加
      s[i] = randnum * X + w[i];

      /* テスト */
      DtoB(s[i], binary_number);
      for (int k = BINARY_DIGIT - 1; k >= 0; k--) {
	printf("%d", binary_number[k]);
      }
      printf("\n");
      /* テスト */

    } else {
      /* SO */
      sum += w[i] = sum + 1 + rand() % 10; // 超増加
      s[i] = z[SO_count] * X + w[i];
      SO_count++;

      /* テスト */
      DtoB(s[i], binary_number);
      for (int k = BINARY_DIGIT - 1; k >= 0; k--) {
	printf("%d", binary_number[k]);
      }
      printf("\n");
      /* テスト */
    }
  }

  
  *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 * s[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 main(int argc, char* argv[]) {
  if (argc != 1) {
    fprintf(stderr, "usage: %s\n", argv[0]);
    exit(EXIT_FAILURE);
  }

  int y[N], z[N], w[N];
  int s[NN];  // 秘密鍵
  int q, r;  // 秘密鍵
  int b[N];        // 公開鍵
   int a[N];  // 暗号化する前のデータ
    int c;     // 暗号化されたデータ
    int n;     // ビット数

  
  generate_keys(b, w, &q, &r, z, y, s); // 鍵の生成

  print_array("  w", w, NN);
  print_array("  z", z, N);
  print_array("  s", s, NN);
  print_array("  b", b,NN);
 printf("  q = %d\n  r = %d\n", q, r);

 
  while ((n = input_data(a)) != 0) {     // データの入力
        print_array("  a", a, n);        // 入力データの表示
        c = encrypt(n, a, b);          // 暗号化
        printf("  c = %d\n", c);       // 暗号化されたデータの表示
  }

  
  return 0;
}

先ほど貼ったプログラムも何か色々直しておかしくなってました。
今この状態でqがwの値を全てたしあわせた値より大きい乱数になってますが
これをsの数列の値を全て足しあわせて値より大きい乱数の数列の合計値より大きい乱数にしたいのですがそうしようとたいのが先ほどのプログラムなのですが先程のようにすると今度wの値もおかしくなってしまった状態です。
今このプログラムからとりあえずbをうまく表示させたい状態です。

ライトニング · #10

自分の中でもあまり理解出来ておらず説明が難しいのですが
SO=超増加数列で
超増加数列でも1bit,3bit,5bitと奇数番目のみ超増加していく数列です。
2bit目ダミーとしては1bit目より大きい乱数、3bit目は1bitと2bitを足しわせた値より大きい値で、4bit目またダミーで3bit目よりかは大きいけど1~3bitを足しあわせた値より大きい値ではダメです。
それが交互に行われていく状態がこの場合SOで　画像でいうaを生成するとこみたいです。

SIは逆で2bit目,4bitと偶数番目のみ超増加していく奇数シフト数列を作るという状況です。
1bit目はダミーの1bitの乱数で2bit目は2bitの奇数乱数で、3bit目はダミーの乱数....
みたいな感じです。

これが画像でいうBみたいらしいです。

それを足しあわせたもの（Bi*X+ai)がSOSIです。
上のプログラムだと
s = z[SO_count] * X + w;
がSOSIでsが秘密鍵になります。

Xは２のbit数乗で計算するみたいです。

今とりあえず上記のプログラムが先程も書いたのですが
ちゃんと作れているかわからないのですがsまでとりあえず作った状態なのですがそこからうまく暗号化ができていない状態です。

本当に連投ばかりで申し訳ないのですが本当に難しくてうまくいかないので御指摘お願いいたします。
わかりにくい部分があれば出来る限り頑張って説明します。

かずま · #11

ライトニングさんが書きました: それを足しあわせたもの（Bi*X+ai)がSOSIです。
上のプログラムだと
s = z[SO_count] * X + w;
がSOSIでsが秘密鍵になります。

[Generation of SOSI] の Step 4 の式は、s_i = β_i X + α_i です。

なぜ、それを s = z[SO_count] * X + w; と書くのか説明してください。
普通に考えたら、s = b * X + a; でしょう。

[Decryption with SOSI] のアルゴリズム 7 で、s は使われていません。
a, b[i], X が秘密鍵なのではありませんか？

暗号化のアルゴリズムの説明はないのですか？
私は、s[i] は暗号化に使用する公開鍵だと考えました。

ライトニングさんが書きました: Xは２のbit数乗で計算するみたいです。

X > Σⁿ _k=1α_k と書いてあるのに、それとは異なる解釈をするのはなぜですか？

ライトニングさんが書きました: 今とりあえず上記のプログラムが先程も書いたのですが
ちゃんと作れているかわからないのですがs[i]までとりあえず作った状態なのですがそこからうまく暗号化ができていない状態です。

No.9 のプログラムについてですが、
配列 w, y, z が何を表しているのか説明してください。
w は、int w[N]; と宣言されていますが、113行目から始まる forループでは、
NN 個の w[i] に書き込んでいて、領域破壊を起こしているように見えます。

148行目の b[i] = *r * s[i] % *q; でオーバーフローしているようです。

b[i] = (long long)*r * s[i] % *q; とすることで、32ビットの int の
*r が 64ビットの long long に変換され、掛け算をするために、s[i] も
long long に変換され、オーバーフローを防ぐことができます。

しかし、こんな計算をすると、MH暗号のように復号には、*r の逆元が必要に
なりませんか？

また、プログラムのインデントをちゃんとしてください。

ライトニング · #12

s = z[SO_count] * X + w;
と書いたのは以前のMH暗号からプログラムを変えて作ったので自分でわかりやすいように超増加数列の宣言はwのままでやりました。
z[SO_count]*はまず普通の超増加数列と奇数シフト数列を作成してからそこからダミーの乱数を入れた数列を工夫して組み合わせようとして分かりやすい宣言をしようとしたらこのようになりました。

私も完璧に理解はしていないのですが秘密鍵はa, b, X,s,q,rかもしれません。

暗号化はMH暗号と同じように
上記の場合s = z[SO_count] * X + w; がメイン？の秘密鍵の数列であり
このsの数列の値を全て足しあわせた値より大きい整数qを生成しそのqと素になるようなrを決めます。

X > Σn k=1αk と書いてあるのに、それとは異なる解釈をするのはなぜですか？
この部分なのですがそこは自分もあまりわからないのですが
http://www.fastpic.jp/viewer.php?file=0230557220.jpg
この画像のように超増加数列と奇数数列を交互に組み込む場合はXの値は２のビット数上にすると綺麗に？具体的にはわからないのですが作れるみたいです。　
もう一つ超増加数列と奇数シフト数列をランダムで組み合わせる場合はX > Σn k=1αkにするのがいいみたいです。この部分は自分もまだはっきりと理解できていないので説明不足ですいません。

wは全ビットが超増加している数列、偶数番目にダミーの乱数を入れる前の状態です。
yは全ビットが超増加している奇数の数列です
zはそのyに２の等比数列を掛け合わせた全ビットが超増加している奇数シフト数列です。
上に貼った画像SOSIの黒く四角で塗りつぶされている部分が超増加している部分です。

復号もMH暗号と同じようにrの逆元を使って平文を復号します。

復号した値が奇数シフト数列だった場合shifted-oddtypeで画像のようにshifted-oddtypeで復号します
その次は交互になっているのでSuper-Increasing Typeなので画像のように復号します。
これを交互に行っていき復号していくみたいです。

インデントは申し訳ないです。

ライトニング · #13

コード:

#include <stdio.h>    // cin, cout
#include <stdlib.h>   // rand, srand
#include <time.h>     // time
#include <limits.h>

#define N  6
#define NN 12
#define PLUS 6
#define BINARY_DIGIT 32

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");
}

int bitcount(unsigned long n)
{
    int c = 0;

    while (n) {
        ++c;
        n = n >> 1;
    }

    return c;
}

int input_data(int *a)  // データの入力
{
    char buf[256];  int i;
 
    printf("\nEnter less than %d binary digits\n", NN);
    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 DtoB(int decimal_number, char binary_number[]) {
  int i;
  for (i = BINARY_DIGIT - 1; i >= 0; i--) {
    binary_number[i] = (decimal_number >> i) & 1;
  }
}

void generate_keys(int *b, int *w, int *q, int *r, int *z, int *y, int *s)  // 鍵の生成
{
  int sum = 0;
  int i, j;
  int bit[NN + PLUS];
  char binary_number[BINARY_DIGIT] = {0}; /* テスト */

  srand((unsigned)time(NULL));

  /* SO: 1   SI: 0 */
  int SOSI_FLAG[NN];
  for (i = 0; i < NN; i++) {
    SOSI_FLAG[i] = i % 2;
  }

  /* 2の等比数列 */
  for (bit[0] = i = 1; i < NN + PLUS; i++)
    bit[i] = 2 * bit[i-1];
  int X = bit[NN + PLUS - 1];

  /******************/
  /* 奇数シフト数列 */
  /******************/
  for (sum = i = 0; i < N; i++) {
    int t = sum + rand() % 10 + 1;
    sum += y[i] = (t & 1) ? t : ++t;
  }
  
  /* テスト */
  printf("奇数シフト\n");
  /* テスト */

  for (i = 0, j = N - 1; i < N; i++, j--) {
    z[i] = y[i] * bit[j];

    /* テスト */
    DtoB(z[i], binary_number);
    for (int k = BINARY_DIGIT - 1; k >= 0; k--) {
      printf("%d", binary_number[k]);
    }
    printf("\n");
    /* テスト */
    
  }

  /* テスト */
  printf("MH数列\n");
  /* テスト */

  int randnum;
  int SO_count = 0;
  sum = 0;
  /* SO: 1   SI: 0 */
  for (i = 0; i < NN; i++) {
    if (SOSI_FLAG[i] == 0) {
      /* SI */
      randnum = rand() % y[SO_count];
      randnum = randnum * bit[N - 1 - SO_count];
      sum += w[i] = sum + 1 + rand() % 10; // 超増加
      s[i] = randnum * X + w[i];

      /* テスト */
      DtoB(s[i], binary_number);
      for (int k = BINARY_DIGIT - 1; k >= 0; k--) {
	printf("%d", binary_number[k]);
      }
      printf("\n");
      /* テスト */

    } else {
      /* SO */
      sum +=w[i] = sum + 1 + rand() % 10; // 超増加
      s[i] = z[SO_count] * X + w[i];
      SO_count++;
      
      /* テスト */
      DtoB(s[i], binary_number);
      for (int k = BINARY_DIGIT - 1; k >= 0; k--) {
	printf("%d", binary_number[k]);
      }
      printf("\n");
      /* テスト */
    }
  }

  int goukei;
  for (i = 0; i <NN; i++)
    goukei=s[i];
  
  *q = goukei + 1 + rand() % 10;                        // 秘密鍵 q の生成
  for (*r = *q / 2; gcd(*r, *q) != 1; ++*r) ;        // 秘密鍵 r の生成
  for (int i = 0; i < N; i++)b[i] = (long long)*r * s[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 main(int argc, char* argv[]) {
  if (argc != 1) {
    fprintf(stderr, "usage: %s\n", argv[0]);
    exit(EXIT_FAILURE);
  }

  int y[N], z[N], w[N];
  int s[NN];  // 秘密鍵
  int q, r;  // 秘密鍵
  int b[N];        // 公開鍵
  int a[N];  // 暗号化する前のデータ
  int c;     // 暗号化されたデータ
  int n;     // ビット数
    
  
  generate_keys(b, w, &q, &r, z, y, s); // 鍵の生成

  print_array("  w", w, NN);
  print_array("  z", z, N);
  print_array("  s", s, NN);
  print_array("  b", b,NN);
  printf("  q = %d\n  r = %d\n", q, r);

  
  while ((n = input_data(a)) != 0) {     // データの入力
    print_array("  a", a, n);        // 入力データの表示
    c = encrypt(n, a, b);          // 暗号化
    printf("  c = %d\n", c);       // 暗号化されたデータの表示
  }

  
  return 0;
}

long longで宣言したら桁あふれは直せました。
けれどもsの数列の要素を全て足しあわせているのが多分うまくいけていなくてqが正しく作れていないです。
またsも多分うまく作れていない状態です....

かずま · #14

コード:

#define N  6
#define NN 12
#define PLUS 6

これは何ですか？

int w[N]; で w[0]～w[NN-1] に書き込んでしまう件はどうするんですか？
b を求めるところのオーバーフローの件は解決ですか？

暗号化のアルゴリズムの説明画像はないのですか？
鍵(SOSI)の生成と、SOSIを使った復号の説明画像はありますが、
MH暗号の鍵生成と復号の説明画像はないのですか？

ライトニング · #15

http://www.fastpic.jp/viewer.php?file=3510112095.png
http://www.fastpic.jp/viewer.php?file=5031538500.png
http://www.fastpic.jp/viewer.php?file=0492923854.png
http://www.fastpic.jp/viewer.php?file=2774361201.png

SO・SI/の生成と復号は上記の画像のようにやるみたいです。

#define N 6　はSOとSIのビット数です
#define NN 12　はSOとSIを交互に組み合わせないといけないのでSOのビット数とSIのビット数を足しあわせた１２です
#define PLUS 6 は鍵生成の部分は教えてもらいながらつくったので自分もまだ完璧に理解できていない部分です...

int w[N]; で w[0]～w[NN-1] に書き込んでしまう件はどうするんですか？
ごめんなさい、この質問はどういう意味でしょうか？

bのオーバーフローは一応治ったのですがqの値がうまく作れていないので解決とは言えない状態です。

かずま · #16

ライトニングさんが書きました: int w[N]; で w[0]～w[NN-1] に書き込んでしまう件はどうするんですか？
ごめんなさい、この質問はどういう意味でしょうか？

No.13 のプログラムで、
178行目 int y[N], z[N], w[N];
int w[6]; ですから、w[0]～w[5] の 6個しかメモリを確保していません。

122行目の for (i = 0; i < NN; i++) {
127行目の sum += w = sum + 1 + rand() % 10; // 超増加

NN は 12 ですから、 w[0]～w[11] に書き込みが生じます。

ライトニング · #17

それは多分ミスなので178行目 int y[N], z[N], w[N];の部分を
No.13のプログラムをw[NN]に訂正しました。

とりあえず今わからないのがNo.13のプログラムでsをうまく作りたいのと
154行目のgoukeiにsの数列の要素を全て足しあわせたものを入れたい状況です。

かずま · #18

断片的な情報から次のようなプログラムを書いてみました。

コード:

#include <stdio.h>   // printf, putchar, fgets, stdin
#include <stdlib.h>  // srand, rand
#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)   // a の逆元 (mod b)
{
    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)
{
    int i;
    printf("  %s = [ %d", name, a[0]);
    for (i = 1; i < n; i++) printf(" %d", a[i]);
    printf(" ]\n");
}
 
void print_sosi(int n, int val)
{
    int i = 32;
    printf("  sosi[%2d] = ", n);
    while (--i >= 0) putchar('0' + (val>>i & 1));
    putchar('\n');
}
 
int input_message(int *m)
{
    int i; char buf[256];

    printf(">> ");
    if (!fgets(buf, sizeof buf, stdin)) return 0;
    for (i = 0; i < N && (buf[i] | 1) == '1'; i++)
        m[i] = buf[i] - '0';
    return i;
}
 
void generate_keys(int *si, int *so, int *pub, int *pX, int *pP, int *pw)
{
    int sosi[N], i = N, X = 0, P, w;
    while (--i >= 0)
        if (i & 1)
            X += si[i] = X + 1 + rand() % 10;  // 秘密鍵 si の生成
        else 
            X += si[i] = 1 + rand() % 10;      // ダミーの si の生成
    X += 1 + rand() % 10;                      // 秘密鍵 X の生成
    for (so[0] = i = 1; i < N; i++)
        so[i] = so[i-1] * 2;                   // 秘密鍵 so の生成
    for (P = i = 0; i < N; i++) {
        P += sosi[i] = so[i] * X + si[i];
        print_sosi(i, sosi[i]);
    }
    P += 1 + rand() % 10;                      // 秘密鍵 P の生成
    for (w = P / 2; gcd(w, P) != 1; w++) ;     // 秘密鍵 w の生成
    for (i = 0; i < N; i++)
        pub[i] = (long long)w * sosi[i] % P;   // 公開鍵 pub の生成
    *pX = X, *pP = P, *pw = w;
}
 
int encrypt(const int *m, int *pub, int n)
{
    int M = 0, i;
    for (i = 0; i < n; i++)
        if (m[i]) M += pub[i];
    return M;
}
 
int decrypt(int C, const int *si, const int *so,
        int X, int P, int inv_w, int *m, int n)
{
    int M = (long long)C * inv_w % P;
    int Q = M / X, R = M % X, i;
    for (i = 0; i < n; i++)
        if (i & 1)
            if (R >= si[i])
                m[i] = 1, R -= si[i], Q -= so[i];
            else
                m[i] = 0;
        else
            if (Q & (1 << i+1)-1)       // if (Q % (1 << i+1) == 1 << i)
                m[i] = 1, R -= si[i], Q -= so[i];
            else
                m[i] = 0;
    return R | Q;   // 0:成功, 0以外:失敗
}
 
int main(void)
{
    int si[N], so[N];   // 秘密鍵
    int X, P, w, inv_w; // 秘密鍵
    int pub[N]; // 公開鍵
    int m[N];   // 入力メッセージ
    int n;      // 入力ビット長
    int C;      // 暗号文
    int d[N];   // 復号データ
 
    srand(time(0));
    generate_keys(si, so, pub, &X, &P, &w);
    inv_w = inverse(w, P);
    print_array("si", si, N);
    print_array("so", so, N);
    printf("  X = %d\n", X);
    printf("  P = %d\n", P);
    printf("  w = %d\n", w);
    printf("  inv_w = %d\n", inv_w);
    print_array("public key", pub, N);
        
    while ((n = input_message(m)) != 0) {
        printf("  length = %d\n", n);
        print_array("message input ", m, n);
        C = encrypt(m, pub, n);
        printf("  cypher text = %d\n", C);
        decrypt(C, si, so, X, P, inv_w, d, n);
        print_array("decrypted data", d, n);
    }
    return 0;
}

とにかく、情報が不足しています。
こちらは授業を受けていたり、テキストを持っていたりするわけではありません。
だから、このプログラムも間違っているかもしれません。

著作物を引用する場合は出典を明らかにしないといけないことになっています。
今回の画像の引用元の書名を教えていただけませんか？

あるいは、今回の暗号についてのネット上のサイトなどはありませんか？

前回の MH暗号では、Wikipedia へのリンクがあったので、
プログラムが書けました。

ライトニング · #19

貼っている画像は先輩の論文の一部を貼っているのでここでは全部のせれない感じです...
かずまさんがよければ私のスカイプなりなんなり教えるのでファイルを送らせていただきたいのですが...

とりあえず自分なりに説明してみます。

もしＳＯとSIが5bitなら

全体は10bitになります

最初SIが超増加するような形を作り下のbitから作っていくとしたら

全体10bit　　　　　　　　　　　　　　　　　　　　　　　　この値がs
例　　　　　　　　　　　　　　　　　　　↓
SO　10011 10111 SI　→　1+2+4+16+(32+64+512)*2^10=622615
SO 01110 10101 SI →　1+4+16+64+(128+256)*2^10=
SO 11110 01011 SI →　1+2+8+64+(128+256+512)*2^10=
SO 11100 01011 SI ・
SO 11100 00101 SI ・
SO 11000 00101 SI ・
SO 11000 00011 SI ・
SO 10000 00010 SI　　　　　　・
SO 10000 00001 SI　　　　　　・
SO 00000 00001 SI ・

こんな感じに最初（下から見て）SIが超増加をし次にＳＯが超増加していくようなのを
組み合わせて交互にあわせていくような感じです。（画像でいうと四角の黒い部分が1で超増加している部分)
SIの条件として2bit目は1bit目より大きい　3bit目は1bit目と2bit目を足し合わせたものより大きい　4bit目は3bit目よりかは大きいけど1~3bitを足し合わせた値より大きくなってはいけない　5bit目は１～４bitを足し合わせたものより大きい値のようにしていくかんじです。

全体が10bitなのでXは2^10です。
このSOSIが秘密鍵になるみたいです。
暗号化はＭＨ暗号と一緒で
復号はr逆元をかけ暗号を元にもどしその値をＸで割ります。
SOの場合Xで割った値の余りの値を判定しMH暗号のようにその値からひけるなら１を返す　ひけないなら０を返す
SIの場合Ｘで割った商の値を判定しその値を2で割り偶数なら１を返し　奇数なら０を返す

もの凄く下手くそな説明ですがおおまかな全体の説明はこのような感じになります。
現在これを今作りたい状態です.....

ライトニング · #20

とりあえずこのsがあってるとして暗号化はまでは出来たのですが
復号を画像のようにうまいこと出来るか試してみたいのですがかずまさんが書いたプログラムをうまく合わせたいのですがどうすればいいでしょうか？

コード:

#include <stdio.h>    // cin, cout
#include <stdlib.h>   // rand, srand
#include <time.h>     // time
#include <limits.h>

#define N  6            // 超増加や奇数シフトのそれぞれの数
#define NN 12           // MH暗号のビット数の数
#define PLUS 6          // 2の等比数列を作るのにNNより多く作る数
#define BINARY_DIGIT 32 // テストに表示するビット数

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");
}

int bitcount(unsigned long n)
{
    int c = 0;

    while (n) {
        ++c;
        n = n >> 1;
    }

    return c;
}

int input_data(int *a)  // データの入力
{
    char buf[256];  int i;
 
    printf("\nEnter less than %d binary digits\n", NN);
    if (!fgets(buf, sizeof buf, stdin)) return 0;
    for (i = 0; i < NN; i++)
        if (buf[i] == '1') a[i] = 1;
        else if (buf[i] == '0') a[i] = 0;
        else break;
    return i;  // ビット数を返す
}
 

void DtoB(int decimal_number, char binary_number[]) {
  int i;
  for (i = BINARY_DIGIT - 1; i >= 0; i--) {
    binary_number[i] = (decimal_number >> i) & 1;
  }
}

void generate_keys(int *b, int *w, int *q, int *r, int *z, int *y, int *s)  // 鍵の生成
{
  int sum = 0;
  int i, j;
  int bit[NN + PLUS];
  char binary_number[BINARY_DIGIT] = {0}; /* テスト */

  srand((unsigned)time(NULL));

  /* SO: 1   SI: 0 */
  int SOSI_FLAG[NN];
  for (i = 0; i < NN; i++) {
    SOSI_FLAG[i] = i % 2;
  }

  /* 2の等比数列 */
  for (bit[0] = i = 1; i < NN + PLUS; i++)
    bit[i] = 2 * bit[i-1];
  int X = bit[NN + PLUS - 1];

  /******************/
  /* 奇数シフト数列 */
  /******************/
  for (sum = i = 0; i < N; i++) {
    int t = sum + rand() % 10 + 1;
    sum += y[i] = (t & 1) ? t : ++t;
  }
  
  /* テスト */
  printf("奇数シフト\n");
  /* テスト */

  for (i = 0, j = N - 1; i < N; i++, j--) {
    z[i] = y[i] * bit[j];

    /* テスト */
    DtoB(z[i], binary_number);
    for (int k = BINARY_DIGIT - 1; k >= 0; k--) {
      printf("%d", binary_number[k]);
    }
    printf("\n");
    /* テスト */
    
  }

  /* テスト */
  printf("MH数列\n");
  /* テスト */

  int randnum;
  int SO_count = 0;
  sum = 0;
  /* SO: 1   SI: 0 */
  for (i = 0; i < NN; i++) {
    if (SOSI_FLAG[i] == 0) {
      /* SI */
      randnum = rand() % y[SO_count];
      randnum = randnum * bit[N - 1 - SO_count];
      sum += w[i] = sum + 1 + rand() % 10; // 超増加
      s[i] = randnum * X + w[i];

      /* テスト */
      DtoB(s[i], binary_number);
      for (int k = BINARY_DIGIT - 1; k >= 0; k--) {
	printf("%d", binary_number[k]);
      }
      printf("\n");
      /* テスト */

    } else {
      /* SO */
      sum +=w[i] = sum + 1 + rand() % 10; // 超増加
      s[i] = z[SO_count] * X + w[i];
      SO_count++;
      
      /* テスト */
      DtoB(s[i], binary_number);
      for (int k = BINARY_DIGIT - 1; k >= 0; k--) {
	printf("%d", binary_number[k]);
      }
      printf("\n");
      /* テスト */
    }
  }

  int goukei=0;
  for (i = 0; i <NN; i++)
    goukei+=s[i];
  
 *q = goukei + 1 + rand() % 10;                        // 秘密鍵 q の生成
  for (*r = *q / 2; gcd(*r, *q) != 1; ++*r) ;        // 秘密鍵 r の生成
  for (int i = 0; i < N; i++)b[i] = (long long)*r * s[i] % *q;  // 公開鍵 b の生成
}
int encrypt(int n, const int *a, const int *b)  // 暗号化
{
  long long c = 0, i;
  for (i = 0; i < n; i++)
    if (a[i] == 1) c += b[i];
  return c;

/*
int decrypt(int c, const int *w, const int *z,   // 復号
        int X, int q, int r, int *m, int n)
{
    int M = (long long)c * inverse(r, q) % q;
    int Q = M / X, R = M % X, i;
    for (i = 0; i < n; i++)
        if (i & 1)
            if (R >= si[i])
                m[i] = 1, R -= si[i], Q -= so[i];
            else
                m[i] = 0;
        else
            if (Q & (1 << i+1)-1)       // if (Q % (1 << i+1) == 1 << i)
                m[i] = 1, R -= w[i], Q -= z[i];
            else
                m[i] = 0;
    return R | Q;   // 0:成功, 0以外:失敗

*/
}

int main(int argc, char* argv[]) {
  if (argc != 1) {
    fprintf(stderr, "usage: %s\n", argv[0]);
    exit(EXIT_FAILURE);
  }

  int y[N], z[N], w[NN];
  int s[NN];  // 秘密鍵
  int q, r;  // 秘密鍵
  int b[N];        // 公開鍵
  int a[N];  // 暗号化する前のデータ
  int c;     // 暗号化されたデータ
  int n;     // ビット数
 
        
    
  
  generate_keys(b, w, &q, &r, z, y, s); // 鍵の生成

  print_array("  w", w, N);
  print_array("  z", z, N);
  print_array("  s", s, NN);
  print_array("  b", b,NN);
  printf("  q = %d\n  r = %d\n", q, r);

  
  while ((n = input_data(a)) != 0) {     // データの入力
    print_array("  a", a, n);        // 入力データの表示
    c = encrypt(n, a, b);          // 暗号化
    printf("  c = %d\n", c);       // 暗号化されたデータの表示
  }

  
  return 0;
}

ライトニング · #21

とりあえず復号しようとしてみたのですがうまく出来ない状態です。
実行してみたらよくわからない状態になってしまいました...どこがおかしいのでしょうか？

コード:

#include <stdio.h>    // cin, cout
#include <stdlib.h>   // rand, srand
#include <time.h>     // time
#include <limits.h>

#define N  6            // 超増加や奇数シフトのそれぞれの数
#define NN 12           // MH暗号のビット数の数
#define PLUS 6          // 2の等比数列を作るのにNNより多く作る数
#define BINARY_DIGIT 32 // テストに表示するビット数

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");
}

int bitcount(unsigned long n)
{
    int c = 0;

    while (n) {
        ++c;
        n = n >> 1;
    }

    return c;
}

int input_data(int *a)  // データの入力
{
    char buf[256];  int i;
 
    printf("\nEnter less than %d binary digits\n", NN);
    if (!fgets(buf, sizeof buf, stdin)) return 0;
    for (i = 0; i < NN; i++)
        if (buf[i] == '1') a[i] = 1;
        else if (buf[i] == '0') a[i] = 0;
        else break;
    return i;  // ビット数を返す
}
 

void DtoB(int decimal_number, char binary_number[]) {
  int i;
  for (i = BINARY_DIGIT - 1; i >= 0; i--) {
    binary_number[i] = (decimal_number >> i) & 1;
  }
}

void generate_keys(int *b, int *w, int *q, int *r, int *z, int *y, int *s)  // 鍵の生成
{
  int sum = 0;
  int i, j;
  int bit[NN + PLUS];
  char binary_number[BINARY_DIGIT] = {0}; /* テスト */

  srand((unsigned)time(NULL));

  /* SO: 1   SI: 0 */
  int SOSI_FLAG[NN];
  for (i = 0; i < NN; i++) {
    SOSI_FLAG[i] = i % 2;
  }

  /* 2の等比数列 */
  for (bit[0] = i = 1; i < NN + PLUS; i++)
    bit[i] = 2 * bit[i-1];
  int X = bit[NN + PLUS - 1];

  /******************/
  /* 奇数シフト数列 */
  /******************/
  for (sum = i = 0; i < N; i++) {
    int t = sum + rand() % 10 + 1;
    sum += y[i] = (t & 1) ? t : ++t;
  }
  
  /* テスト */
  printf("奇数シフト\n");
  /* テスト */

  for (i = 0, j = N - 1; i < N; i++, j--) {
    z[i] = y[i] * bit[j];

    /* テスト */
    DtoB(z[i], binary_number);
    for (int k = BINARY_DIGIT - 1; k >= 0; k--) {
      printf("%d", binary_number[k]);
    }
    printf("\n");
    /* テスト */
    
  }

  /* テスト */
  printf("MH数列\n");
  /* テスト */

  int randnum;
  int SO_count = 0;
  sum = 0;
  /* SO: 1   SI: 0 */
  for (i = 0; i < NN; i++) {
    if (SOSI_FLAG[i] == 0) {
      /* SI */
      randnum = rand() % y[SO_count];
      randnum = randnum * bit[N - 1 - SO_count];
      sum += w[i] = sum + 1 + rand() % 10; // 超増加
      s[i] = randnum * X + w[i];

      /* テスト */
      DtoB(s[i], binary_number);
      for (int k = BINARY_DIGIT - 1; k >= 0; k--) {
	printf("%d", binary_number[k]);
      }
      printf("\n");
      /* テスト */

    } else {
      /* SO */
      sum +=w[i] = sum + 1 + rand() % 10; // 超増加
      s[i] = z[SO_count] * X + w[i];
      SO_count++;
      
      /* テスト */
      DtoB(s[i], binary_number);
      for (int k = BINARY_DIGIT - 1; k >= 0; k--) {
	printf("%d", binary_number[k]);
      }
      printf("\n");
      /* テスト */
    }
  }

  int goukei=0;
  for (i = 0; i <NN; i++)
    goukei+=s[i];
  
 *q = goukei + 1 + rand() % 10;                        // 秘密鍵 q の生成
  for (*r = *q / 2; gcd(*r, *q) != 1; ++*r) ;        // 秘密鍵 r の生成
  for (int i = 0; i < N; i++)b[i] = (long long)*r * s[i] % *q;  // 公開鍵 b の生成
}
int encrypt(int n, const int *a, const int *b)  // 暗号化
{
  long long c = 0, i;
  for (i = 0; i < n; i++)
    if (a[i] == 1) c += b[i];
  return c;
  
}

int decrypt(int c, const int *w, const int *z,   // 復号
        int X, int q, int r, int *m, int n)
{
    int M = (long long)c * inverse(r, q) % q;
    int Q = M / X, R = M % X, i;
    for (i = 0; i < n; i++)
        if (i & 1)
            if (R >= w[i])
                m[i] = 1, R -= w[i], Q -= z[i];
            else
                m[i] = 0;
        else
            if (Q & (1 << i+1)-1)       // if (Q % (1 << i+1) == 1 << i)
                m[i] = 1, R -= w[i], Q -= z[i];
            else
                m[i] = 0;
    return R | Q;   // 0:成功, 0以外:失敗


}

int main(int argc, char* argv[]) {
  if (argc != 1) {
    fprintf(stderr, "usage: %s\n", argv[0]);
    exit(EXIT_FAILURE);
  }

  int y[N], z[N], w[NN];
  int s[NN];  // 秘密鍵
  int q, r;  // 秘密鍵
  int b[N];        // 公開鍵
  int a[N];  // 暗号化する前のデータ
  int c;     // 暗号化されたデータ
  int n;     // ビット数
  
  int d[N];   // 復号データ
  int X;
      
    
  
  generate_keys(b, w, &q, &r, z, y, s); // 鍵の生成

  print_array("  w", w, N);
  print_array("  z", z, N);
  print_array("  s", s, NN);
  print_array("  b", b,NN);
  printf("  q = %d\n  r = %d\n", q, r);

  
  while ((n = input_data(a)) != 0) {     // データの入力
    print_array("  a", a, n);        // 入力データの表示
    c = encrypt(n, a, b);          // 暗号化
    printf("  c = %d\n", c);       // 暗号化されたデータの表示

    
    decrypt(c, w, z, X, q, r, d, n);
    print_array("decrypted data", d, n);
    
  }

  
  return 0;
}

コード:

  w = [ 9 16 27 58 111 231 ]
  z = [ 224 272 200 220 226 219 ]
  s = [ 20971529 29360144 29360155 35651642 11534447 26214631 9437642 28836752 3147556 29625932 26090647 28719401 ]
  b = [ 128989477 264270411 124795164 261124662 133708018 126367926 0 0 20971529 29360144 29360155 35651642 ]
  q = 278950483
  r = 139475241

Enter less than 12 binary digits
1111
  a = [ 1 1 1 1 ]
  c = 779179714
Floating point exception: 8
[/code=text]

ライトニング · #22

最終的にNTLというZZ型と新しい変数？を定義して大きい値でも実行できるようなC++のライブラリを使って作りたいのですが
一部直せてないのですが何とか暗号化までコンパイル出来るところまできました。
後復号され終わればいいのですが上のプログラムの通りうまくいかない状態です。本当に何回も連投ばっかで申し訳ないのですが
アドバイスの方お願いします。

コード:

#include <iostream>  // cin, cout
#include <cstdlib>   // rand, srand
#include <ctime>     // time
#include <NTL/ZZ.h>
 


using namespace std;
using namespace NTL;

#define N  10            // 超増加や奇数シフトのそれぞれの数
#define NN 20           // MH暗号のビット数の数
#define PLUS 10          // 2の等比数列を作るのにNNより多く作る数
#define BINARY_DIGIT 32 // テストに表示するビット数

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 " << NN << " binary digits\n";
    if (!getline(cin, buf)) return 0;
    size_t i, n = buf.size();
    if (n >= N) return 0;
    for (i = 0; i < NN; 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;  // ビット数を返す
}
ZZ bitcount(int n)
{
  ZZ c;
  c = 0;

    while (n) {
        ++c;
        n = n >> 1;
    }

    return c;
}

void DtoB(ZZ decimal_number, char binary_number[]) {
  int i;
  for (i = BINARY_DIGIT - 1; i >= 0; i--) {
    //binary_number[i] = (decimal_number >> i) & 1;
  }
}

void generate_keys(ZZ *b, ZZ *w, ZZ *q, ZZ *r, ZZ *z, ZZ *y, ZZ *s)  // 鍵の生成
{
  ZZ sum;
  sum = 0;
  int i, j;
  ZZ bit[NN + PLUS];
  char binary_number[BINARY_DIGIT] = {0}; /* テスト */

  srand((unsigned)time(NULL));

  /* SO: 1   SI: 0 */
  ZZ SOSI_FLAG[NN];
  for (i = 0; i < NN; i++) {
    SOSI_FLAG[i] = i % 2;
  }

  /* 2の等比数列 */
  for (bit[0] = i = 1; i < NN + PLUS; i++)
    bit[i] = 2 * bit[i-1];
  ZZ X = bit[NN + PLUS - 1];

  /******************/
  /* 奇数シフト数列 */
  /******************/
  for (sum = i = 0; i < N; i++) {
    ZZ t = sum + rand() % 10 + 1;
    //    sum += y[i] = (t & 1) ? t : ++t;
    if (t%2) t++;
    y[i]=t;
    sum+=y[i];
  }
  
  /* テスト */
cout<<"奇数シフト\n";
  /* テスト */


  for (i = 0, j = N - 1; i < N; i++, j--) {
    z[i] = y[i] * bit[j];

    /* テスト */
    DtoB(z[i], binary_number);
    for (int k = BINARY_DIGIT - 1; k >= 0; k--) {
      cout<<binary_number[k]<<" ";
    }
    cout<<"\n";
    /* テスト */
    
  }

  /* テスト */
cout<<"MH数列\n";
  /* テスト */

 ZZ randnum;
 int SO_count;
 SO_count = 0;
  sum = 0;
  /* SO: 1   SI: 0 */
  for (i = 0; i < NN; i++) {
    if (SOSI_FLAG[i] == 0) {
      /* SI */
      ZZ nnn;
      nnn = 100000000000000;
      randnum = RandomBnd(nnn) % y[SO_count];
      randnum = randnum * bit[N - 1 - SO_count];
      sum += w[i] = sum + 1 + rand() % 10; // 超増加
      s[i] = randnum * X + w[i];

      /* テスト */
      DtoB(s[i], binary_number);
      for (int k = BINARY_DIGIT - 1; k >= 0; k--) {
	cout<<binary_number[k]<<" ";
      }
      cout<<"\n";
      /* テスト */

    } else {
      /* SO */
      sum +=w[i] = sum + 1 + rand() % 10; // 超増加
      s[i] = z[SO_count] * X + w[i];
      SO_count++;
      
      /* テスト */
      DtoB(s[i], binary_number);
      for (int k = BINARY_DIGIT - 1; k >= 0; k--) {
	cout<<binary_number[k]<<" ";
      }
      cout<<"\n";
      /* テスト */
    }
  }

  ZZ goukei;
  goukei = 0;
  for (i = 0; i <NN; i++)
    goukei+=s[i];
  
 *q = goukei + 1 + rand() % 10;                        // 秘密鍵 q の生成
  for (*r = *q / 2; gcd(*r, *q) != 1; ++*r) ;        // 秘密鍵 r の生成
  for (int i = 0; i < N; i++)b[i] = *r * s[i] % *q;  // 公開鍵 b の生成
}
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 main(void)
{
    ZZ y[N], z[N], w[NN];  // 秘密鍵
    ZZ s[NN];        // 公開鍵
    ZZ b[N];
    ZZ q, r;
    int a[N];  // 暗号化する前のデータ
    ZZ c;      // 暗号化されたデータ
    int n;     // ビット数
 
    srand(time(0));
   generate_keys(b, w, &q, &r, z, y, s); // 鍵の生成
    print_array("  w", w, N);
    print_array("  z", z, N);
    cout << "Private key\n";
    print_array("  s", s, NN);
    cout << "  q = " << q << "\n  r = " << r << endl;
    cout << "Public key\n";
    print_array("  b", b, N);



    
      // データの入力
   while ((n = input_data(a)) != 0) {
        print_bin("  a", a, n);        // 入力データの表示
        c = encrypt(n, a, b);          // 暗号化
        cout << "  c = " << c << endl; // 暗号化されたデータの表示
     
    }
    return 0;
}

かずま · #23

ライトニングさんが書きました:自分の中でもあまり理解出来ておらず説明が難しいのですが
SO=超増加数列で
超増加数列でも1bit,3bit,5bitと奇数番目のみ超増加していく数列です。

SO は、Shift-Odd Sequence で、奇数シフト数列です。
SI は、Super-Increasing Sequence で、超増加数列です。

超増加数列は、(3, 7, 12, 25, 48, 99) のように、ある項が、直前までのすべて
の項の和より大きい数列です。
この数列の特徴は、部分和が与えられると、どの項の和であるかが分かることです。
例えば、67 になるのは 7 + 12 + 48 だけです。
(1, 3, 5, 7, 9, 11) は増加数列ですが、超増加ではないので、12 が与えられて
も、それが 3 + 9 なのか、5 + 7 なのか分かりません。
67 は、48 の直前まで総和が 48 より小さいので 48 を含むことが分かります。
残りは、67 - 48 = 19 ですが、これは 25 を含まない。
12 を含み、残りが 7 だと分かります。

入力の平文のビット列から、どの項の部分和かが決まり、その部分和が暗号文です。
ただ、この超増加数列をそのまま、公開すると、だれでも暗号化も復号もできて
しまいます。

だから、互いに素である 2つの整数 a, b を使い、数列の各項を a倍して b で
割った余りを公開鍵にするのです。公開鍵からは a と b を求めることはできない
ので安全になります。a と b を知っていると mod b における a の逆元を使い、
暗号文を部分和に戻すことができます。

ここまでが、Marcle-Hellmanナップサック暗号でした。

奇数シフト数列は、奇数数列の各項を、(項番号-1)ビット左にシフトしたものです。
例えば、(1, 5, 3, 7, 9, 3) という奇数数列から、
(1<<0. 5<<1, 3<<2, 7<<3, 9<<4, 3<<5)、すなわち
(1*1, 5*2, 3*4, 7*8, 9*16, 3*32)、すなわち
(1, 10, 12, 56, 144, 96) という奇数シフト数列が作れます。
各項を 2進で表すと、
(00000001, 00001010, 00001100, 00111000, 10010000, 01100000)
最下位の 1 が右(LSB) から何ビット目にあるかで、第何項かが分かります。
部分和が与えられると、最下位の 1 が何ビット目にあるかで、それがどの項を
含むかが分かり、その値を引くことで、残りの部分和の項も分かります。

この 2つの数列を組み合わせることで、複雑な暗号ができます。
例えば、偶数番目の項は SI を、奇数番目の項は SO を使うとします。
ここで注意しなければならないのは、SO は下位のビットから処理しなければ
ならないので、数列の初項から見ていきますが、SI は大きな値から処理して
いかなければならないので、数列の末項から見ていきます。
そこで、数列を逆順にしておきます。

SI = (99, 48, 25, 12, 7, 3)
SO = (1, 10, 12, 56, 144, 96)

SI は偶数番目だけ、SO は奇数番目だけとすると、

SI = (xx, 48, xx, 12, xx, 3)
SO = (1, xx, 12, xx, 144, xx)
xx は使わないので何でもよいことになります。
SI の xx を小さな値にすることによって、値の増加を少なくすることができます。

SI の総和より大きい値を X とすると、
SOSI = SO * X + SI で、2つの数列を合成でき、
SOSI の部分和 M を作ると、
Q = M / X
R = M % X
で、SO の部分和 Q と、SI の部分和 R に分離することができます。

(a₁, a₂, ..., a₆) という数列は、
C のプログラムでは、a[0], a[1], ..., a[5] という配列になって、
添え字の奇数偶数が入れ替わることに注意が必要です。

このように考えてできたのが次のプログラムです。

コード:

#include <stdio.h>   // printf, putchar, fgets, stdin
#include <stdlib.h>  // srand, rand
#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)   // a の逆元 (mod b)
{
    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)
{
    int i;
    printf("  %s = [ %d", name, a[0]);
    for (i = 1; i < n; i++) printf(" %d", a[i]);
    printf(" ]\n");
}
 
int input_message(int *m)
{
    int i; char buf[256];
 
    printf(">> ");
    if (!fgets(buf, sizeof buf, stdin)) return 0;
    for (i = 0; i < N && (buf[i] | 1) == '1'; i++)
        m[i] = buf[i] - '0';
    return i;
}
 
void generate_keys(int *si, int *so, int *pub, int *pX, int *pP, int *pw)
{
    int sosi[N], i = N, X = 0, P, w;
    while (--i >= 0)
        if (i & 1)
            X += si[i] = X + 1 + rand() % 10;  // 秘密鍵 si の生成
        else 
            X += si[i] = 1 + rand() % 10;      // ダミーの si の生成
    X += 1 + rand() % 10;                      // 秘密鍵 X の生成
    for (i = 0; i < N; i++)
        so[i] = (rand() % 10 | 1) << i;        // 秘密鍵 so の生成
    for (P = i = 0; i < N; i++)
        P += sosi[i] = so[i] * X + si[i];
    P += 1 + rand() % 10;                      // 秘密鍵 P の生成
    for (w = P / 2; gcd(w, P) != 1; w++) ;     // 秘密鍵 w の生成
    for (i = 0; i < N; i++)
        pub[i] = (long long)w * sosi[i] % P;   // 公開鍵 pub の生成
    *pX = X, *pP = P, *pw = w;
}
 
int encrypt(const int *m, int *pub, int n)
{
    int M = 0, i;
    for (i = 0; i < n; i++)
        if (m[i]) M += pub[i];
    return M;
}
 
int decrypt(int C, const int *si, const int *so,
        int X, int P, int inv_w, int *m, int n)
{
    int M = (long long)C * inv_w % P;
    int Q = M / X, R = M % X, i;
    for (i = 0; i < n; i++)
        if (i & 1)
            if (R >= si[i])
                m[i] = 1, R -= si[i], Q -= so[i];
            else
                m[i] = 0;
        else
            if (Q >> i & 1)       // if (Q % (1 << i+1) == 1 << i)
                m[i] = 1, R -= si[i], Q -= so[i];
            else
                m[i] = 0;
    return R | Q;   // 0:成功, 0以外:失敗
}
 
int main(void)
{
    int si[N], so[N];   // 秘密鍵
    int X, P, w, inv_w; // 秘密鍵
    int pub[N]; // 公開鍵
    int m[N];   // 入力メッセージ
    int n;      // 入力ビット長
    int C;      // 暗号文
    int d[N];   // 復号データ
 
    srand(time(0));
    generate_keys(si, so, pub, &X, &P, &w);
    inv_w = inverse(w, P);
    print_array("si", si, N);
    print_array("so", so, N);
    printf("  X = %d\n", X);
    printf("  P = %d\n", P);
    printf("  w = %d\n", w);
    printf("  inv_w = %d\n", inv_w);
    print_array("public key", pub, N);
        
    while ((n = input_message(m)) != 0) {
        printf("  length = %d\n", n);
        print_array("message input ", m, n);
        C = encrypt(m, pub, n);
        printf("  cypher text = %d\n", C);
        decrypt(C, si, so, X, P, inv_w, d, n);
        print_array("decrypted data", d, n);
    }
    return 0;
}

NTL を使うため C++ に書き直すと、

コード:

#include <NTL/ZZ.h>
#include <stdlib.h>  // srand, rand
#include <time.h>    // time
 
using namespace std;
using namespace NTL;

#define N 50
#define DISP_N 15
 
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)   // a の逆元 (mod b)
{
    ZZ x1, y1, z1, x2, y2, z2, q, t;
    x1 = 1, y1 = 0, z1 = a, x2 = 0, y2 = 1, z2 = b;
    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 << " = [ " << a[0];
    if (n > DISP_N) n = DISP_N;
    for (int i = 1; i < n; i++) cout << " " << a[i];
    cout << " ]\n";
}
 
void print_bin(const char *name, const int *a, int n)
{
    cout << "  " << name << " = [ " << a[0];
    for (int i = 1; i < n; i++) cout << a[i];
    cout << " ]\n";
}
 
int input_message(int *m)
{
    int i;
    string buf;
    cout << ">> ";
    if (!getline(cin, buf)) return 0;
    for (i = 0; i < N && (buf[i] | 1) == '1'; i++)
        m[i] = buf[i] - '0';
    return i;
}
 
void generate_keys(ZZ *si, ZZ *so, ZZ *pub, ZZ *pX, ZZ *pP, ZZ *pw)
{
    ZZ sosi[N], X, P, w, t;
    int i = N;
    X = 0;
    while (--i >= 0)
        if (i & 1)
            X += si[i] = X + 1 + rand() % 10;  // 秘密鍵 si の生成
        else 
            X += si[i] = 1 + rand() % 10;      // ダミーの si の生成
    X += 1 + rand() % 10;                      // 秘密鍵 X の生成
    for (i = 0; i < N; i++) {
        t = rand() % 10 | 1;
        so[i] = t << i;                        // 秘密鍵 so の生成
    }
    for (P = i = 0; i < N; i++)
        P += sosi[i] = so[i] * X + si[i];
    P += 1 + rand() % 10;                      // 秘密鍵 P の生成
    for (w = P / 2; gcd(w, P) != 1; w++) ;     // 秘密鍵 w の生成
    for (i = 0; i < N; i++)
        pub[i] = w * sosi[i] % P;              // 公開鍵 pub の生成
    *pX = X, *pP = P, *pw = w;
}
 
ZZ encrypt(const int *m, ZZ *pub, int n)
{
    ZZ M;
    M = 0;
    for (int i = 0; i < n; i++)
        if (m[i]) M += pub[i];
    return M;
}
 
int decrypt(ZZ C, const ZZ *si, const ZZ *so,
        ZZ X, ZZ P, ZZ inv_w, int *m, int n)
{
    ZZ M = C * inv_w % P;
    ZZ Q = M / X, R = M % X;
    for (int i = 0; i < n; i++)
        if (i & 1)
            if (R >= si[i])
                m[i] = 1, R -= si[i], Q -= so[i];
            else
                m[i] = 0;
        else
            if ((Q >> i) % 2 == 1)       // if (Q % (1 << i+1) == 1 << i)
                m[i] = 1, R -= si[i], Q -= so[i];
            else
                m[i] = 0;
    return R != 0 || Q != 0;  // 0:成功, 0以外:失敗
}
 
int main(void)
{
    ZZ si[N], so[N];   // 秘密鍵
    ZZ X, P, w, inv_w; // 秘密鍵
    ZZ pub[N];  // 公開鍵
    int m[N];   // 入力メッセージ
    int n;      // 入力ビット長
    ZZ C;       // 暗号文
    int d[N];   // 復号データ
 
    srand(time(0));
    generate_keys(si, so, pub, &X, &P, &w);
    inv_w = inverse(w, P);
    print_array("si", si, N);
    print_array("so", so, N);
    cout << "  X = " << X << "\n";
    cout << "  P = " << P << "\n";
    cout << "  w = " << w << "\n";
    cout << "  inv_w = " << inv_w << "\n";
    print_array("public key", pub, N);
        
    while ((n = input_message(m)) != 0) {
        cout << "  length = " << n << "\n";
        print_bin("message input ", m, n);
        C = encrypt(m, pub, n);
        cout << "  cypher text = " << C << "\n";
        decrypt(C, si, so, X, P, inv_w, d, n);
        print_bin("decrypted data", d, n);
    }
    return 0;
}

ライトニング · #24

細かいご回答アドバイスありがとうございます。

かずまさんがかいたこの部分なのですが
SI = (xx, 48, xx, 12, xx, 3)
SO = (1, xx, 12, xx, 144, xx)
xx は使わないので何でもよいことになります

xxは条件があるみたいで上記の数列の場合　SIの最初のxx（右からみて）は　3<xx<12 次のxxは12<xx<48
のように前の値よりかは大きいが次の値よりかは大きくなってはならない条件にしないといけないみたいです。
さらにその12はそのXX+3<12　次の48は　3+xx+12+xx<48　のような調整をしないといけないみたいです。

後No.22のプログラムを一度復号してみたいのですがNo.22の復号をかずまさんが書いたNo.23のように復号したらどのようにかくか教えて頂けないでしょうか？

ライトニング · #25

さらにその12はそのXX+3<12　次の48は　3+xx+12+xx<48　のような調整をしないといけないみたいです。
すみませんこの部分ちょっと変な言い方しました。
１２の部分ははxx+3より大きい値ではないとだめ　４８の部分は　3+xx+12（3+xx）+xxを足し合わせた値より大きい値ではだめと言いたかったです。

かずま · #26

ライトニングさんが書きました: xxは条件があるみたいで上記の数列の場合　SIの最初のxx（右からみて）は　3<xx<12 次のxxは12<xx<48
のように前の値よりかは大きいが次の値よりかは大きくなってはならない条件にしないといけないみたいです。
さらにその12はそのXX+3<12　次の48は　3+xx+12+xx<48　のような調整をしないといけないみたいです。

その条件は、説明資料の画像のどこにありますか？
No.23のプログラムの次の部分を変更すればよいでしょう。

コード:

            X += si[i] = 1 + rand() % 10;      // ダミーの si の生成

を

コード:

[code=c]
            X += si[i] = si[i-1] +1 + rand() % 10;  // ダミーの si の生成

に。ただし、奇数偶数に注意して si[-1]を参照しないようにしないといけません。

ライトニングさんが書きました: 後No.22のプログラムを一度復号してみたいのですがNo.22の復号をかずまさんが書いたNo.23のように復号したらどのようにかくか教えて頂けないでしょうか？

No.23 の 2つのプログラムを十分理解して、No.22 に復号処理を追加してください。
No.23 についての質問は受け付けますが、No.22 のプログラムは見たくありません。
変数の名前もコメントも無茶苦茶ですから。
decrypt で必要な X が generate_keys の中にしか無いし。

ライトニング · #27

すみません、説明資料のどの部分かは分からないです。
課題で口頭でそのような条件で作るようにと言われました。

コード:

            X += si[i] = si[i-1] +1 + rand() % 10;  // ダミーの si の生成

このようになおしたのですが実行するとsの値がおかしくなりました。
かずまさんが書いた
ただし、奇数偶数に注意して si[-1]を参照しないようにしないといけません。

この部分が今一わからないのですが上記の部分だけ治すだけじゃだめなのでしょうか？

かずま · #28

ライトニングさんが書きました:
コード:
            X += si[i] = si[i-1] +1 + rand() % 10;  // ダミーの si の生成
このようになおしたのですが実行するとsの値がおかしくなりました。
かずまさんが書いた
ただし、奇数偶数に注意して si[-1]を参照しないようにしないといけません。

この部分が今一わからないのですが上記の部分だけ治すだけじゃだめなのでしょうか？

すみません。si は逆順なので、si[i-1] ではなく、si[i+1] でした。

コード:

            X += si[i] = si[i+1] + 1 + rand() % 10;  // ダミーの si の生成

今は、#deifne N 12 なので、これで問題なのですが、
例えば、#define N 11 にすると、最初にこの行が実行され、
存在しない si[N] を参照してしまうので、注意が必要です。
次のようにするなどで対応してください。

コード:

            X += si[i] = (i<N-1 ? si[i+1] : 0) + 1 + rand() % 10;

ライトニング · #29

SOのほうのxxはどうなってるのでしょうか？
これも口頭で言われたてあまり理解できてないのですが
SOは例えば１０bitの場合
１０bitの奇数×2^0　次に
9bitの乱数×2^1
9bitの奇数乱数×2^1
8bitの乱数×2^2
8bitの奇数乱数×2^2
　　　　　・
　　　　　・
　　　　　・
という条件？があるみたいです

かずま · #30

kビットの乱数: rand() & ((1<<k) - 1) | (1 << (k-1))
kビットの奇数乱数: rand() & ((1<<k) - 1) | (1 << (k-1)) | 1

ライトニング · #31

コード:

    
if (i & 1)
      so[i] =  rand() & ((1<<k) - 1) | (1 << (k-1))        // 秘密鍵 so の生成
           else
      so[i] =   rand() & ((1<<k) - 1) | (1 << (k-1)) | 1

書いてものを入れようとしたのですがどのように入れればいいのでしょうか？
とりあえずこのようにしてみたのですがうまく動作しなくて...

ライトニング · #32

また上記にも書いた通りこの乱数に2の等比数列を上から掛け合わせたいのですがどうすればいいでしょうか...
聞いてばかりで本当申し訳ないです。

ライトニング · #33

siはうまくできたので
後はこれのso偶数番目だけ奇数シフトできれば完成だと思うのですが
うまく実行できません。後確認のため sosiを１０進数を２進数に変えて表示もしたいのですがそれもうまく表示できていない状態です。
何度も連投ばっかになってしまうのですが締め切りが近いためご指摘お願いします。

コード:

#include <NTL/ZZ.h>
#include <stdlib.h>  // srand, rand
#include <time.h>    // time
 
using namespace std;
using namespace NTL;
 
#define N 10
#define DISP_N 15
 
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)   // a の逆元 (mod b)
{
    ZZ x1, y1, z1, x2, y2, z2, q, t;
    x1 = 1, y1 = 0, z1 = a, x2 = 0, y2 = 1, z2 = b;
    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 << " = [ " << a[0];
    if (n > DISP_N) n = DISP_N;
    for (int i = 1; i < n; i++) cout << " " << a[i];
    cout << " ]\n";
}
 
void print_bin(const char *name, const int *a, int n)
{
    cout << "  " << name << " = [ " << a[0];
    for (int i = 1; i < n; i++) cout << a[i];
    cout << " ]\n";
}
 
int input_message(int *m)
{
    int i;
    string buf;
    cout << ">> ";
    if (!getline(cin, buf)) return 0;
    for (i = 0; i < N && (buf[i] | 1) == '1'; i++)
        m[i] = buf[i] - '0';
    return i;
}

void generate_keys(ZZ *si, ZZ *so, ZZ *pub, ZZ *pX, ZZ *pP, ZZ *pw)
{
    ZZ sosi[N], X, P, w, t;
    int i = N;
   
    X = 0;
    while (--i >= 0)
        if (i & 1)
	  X += si[i] = X + 1 + rand() % 10;  // 秘密鍵 si の生成
        else 
	  X += si[i] = si[i+1] + 1 + rand() % 10;      // ダミーの si の生成
          X += 1 + rand() % 10;                      // 秘密鍵 X の生成
	  for (i = 0; i < N; i++) {
      t = rand() % 10 | 1;
      if (i & 1)
	so[i] = rand() & ((1<<N) - 1) | (1 << (N-1));   // 秘密鍵 so の生成
      else
	so[i+1] = rand() & ((1<<N) - 1) | (1 << (N-1)) | 1;  // ダミー so の生成
      for (P = i = 0; i < N; i++)
	  P += sosi[i] = so[i] * X + si[i];
	P += 1 + rand() % 10;                      // 秘密鍵 P の生成
	for (w = P / 2; gcd(w, P) != 1; w++) ;     // 秘密鍵 w の生成
	for (i = 0; i < N; i++)
      pub[i] = w * sosi[i] % P;              // 公開鍵 pub の生成
    *pX = X, *pP = P, *pw = w;


}

    
ZZ encrypt(const int *m, ZZ *pub, int n)
{
    ZZ M;
    M = 0;
    for (int i = 0; i < n; i++)
        if (m[i]) M += pub[i];
    return M;
}
 
int decrypt(ZZ C, const ZZ *si, const ZZ *so,
        ZZ X, ZZ P, ZZ inv_w, int *m, int n)
{
    ZZ M = C * inv_w % P;
    ZZ Q = M / X, R = M % X;
    for (int i = 0; i < n; i++)
        if (i & 1)
            if (R >= si[i])
                m[i] = 1, R -= si[i], Q -= so[i];
            else
                m[i] = 0;
        else
            if ((Q >> i) % 2 == 1)       // if (Q % (1 << i+1) == 1 << i)
                m[i] = 1, R -= si[i], Q -= so[i];
            else
                m[i] = 0;
    return R != 0 || Q != 0;  // 0:成功, 0以外:失敗
}
 
int main(void)
{
    ZZ si[N], so[N];   // 秘密鍵
    ZZ X, P, w, inv_w; // 秘密鍵
    ZZ pub[N];  // 公開鍵
    int m[N];   // 入力メッセージ
    int n;      // 入力ビット長
    ZZ C;       // 暗号文
    int d[N];   // 復号データ
 
    srand(time(0));
    generate_keys(si, so, pub, &X, &P, &w);
    inv_w = inverse(w, P);
    print_array("si", si, N);
    print_array("so", so, N);
    cout << "  X = " << X << "\n";
    cout << "  P = " << P << "\n";
    cout << "  w = " << w << "\n";
    cout << "  inv_w = " << inv_w << "\n";
    print_array("public key", pub, N);
        
    while ((n = input_message(m)) != 0) {
        cout << "  length = " << n << "\n";
        print_bin("message input ", m, n);
        C = encrypt(m, pub, n);
        cout << "  cypher text = " << C << "\n";
        decrypt(C, si, so, X, P, inv_w, d, n);
        print_bin("decrypted data", d, n);
    }
    return 0;

ライトニング · #34

参考資料を確認しつつかずまさんのNo.23のプログラムと比較したにですが
かずまさんのNo.23のプログラムがほとんどあっているような気がしました。

コード:

   t = rand() % 10 | 1;
        so[i] = t << i;                        // 秘密鍵 so の生成

この部分が今一理解できていないのですがsoは全て奇数シフトしてるのでしょうか？
かずまさんも書いていた通りsoの偶数番目だけ奇数シフトし
偶数番目は乱数×*2^iすればいいのですがこれでなっているのでしょうか？

rand() & ((1<<k) - 1) | (1 << (k-1))
rand() & ((1<<k) - 1) | (1 << (k-1)) | 1

またこれはどういった処理が行われてるのでしょうか？
NTLだと　&が使えないので他のに代用しないといけないのですがどうすればいいのでしょうか？

ライトニング · #35

http://www.fastpic.jp/viewer.php?file=0230557220.jpg
soとsiはなんとかうまく作れました
けどsoとsiを合成するとおかしな感じになります
上記の画像のような真ん中のbitの0が広がっていく感じに三角形のような形にならないとダメなのですがうまくいってない状態です。また復号もお菓子なくなってしました。
何が原因かわからない状態です...

コード:

#include <NTL/ZZ.h>
#include <stdlib.h>  // srand, rand
#include <time.h>    // time
 
using namespace std;
using namespace NTL;
 
#define N 10
#define DISP_N 10
#define BINARY_BIT_SIZE 32 // テストに表示するビット数
 
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)   // a の逆元 (mod b)
{
    ZZ x1, y1, z1, x2, y2, z2, q, t;
    x1 = 1, y1 = 0, z1 = a, x2 = 0, y2 = 1, z2 = b;
    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 NTL_DtoB(ZZ decimal_number, char binary_number[]) {
  int i;
  for (i = BINARY_BIT_SIZE - 1; i >= 0; i--) {
    binary_number[i] = (decimal_number >> i) % 2;
    printf("%d", binary_number[i]);
  }
  printf("\n");
}

void print_array(const char *name, const ZZ *a, int n)
{
    cout << "  " << name << " = [ " << a[0];
    if (n > DISP_N) n = DISP_N;
    for (int i = 1; i < n; i++) cout << " " << a[i];
    cout << " ]\n";
}
 
void print_bin(const char *name, const int *a, int n)
{
    cout << "  " << name << " = [ " << a[0];
    for (int i = 1; i < n; i++) cout << a[i];
    cout << " ]\n";
}
 
int input_message(int *m)
{
    int i;
    string buf;
    cout << ">> ";
    if (!getline(cin, buf)) return 0;
    for (i = 0; i < N && (buf[i] | 1) == '1'; i++)
        m[i] = buf[i] - '0';
    return i;
}
 
void generate_keys(ZZ *si, ZZ *so, ZZ *pub, ZZ *pX, ZZ *pP, ZZ *pw)
{
  char binary_number[BINARY_BIT_SIZE] = {0}; /* テスト */   
  ZZ sosi[N], X, P, w, t;
    int i = N;
    X = 0;
    while (--i >= 0)
        if (i & 1)
            X += si[i] = X + 1 + rand() % 10;  // 秘密鍵 si の生成
        else 
	  X += si[i] = 1 + rand() % 10;      // ダミーの si の生成
    X += 1 + rand() % 10;                      // 秘密鍵 X の生成
    for (i = 0; i < N; i++) {
      t = rand() % 10 | 1;
      so[i] = t << (i+1)/2;       // 秘密鍵 so の生成
    
       NTL_DtoB(si[i], binary_number);
    }

    printf("\n");

    for (i = 1; i < N; i++) {
      NTL_DtoB(so[i], binary_number);
    }

    printf("\n");

    for (P = i = 0; i < N; i++)
        P += sosi[i] = so[i] * X + si[i];
    P += 1 + rand() % 10;                      // 秘密鍵 P の生成
    for (w = P / 2; gcd(w, P) != 1; w++) ;     // 秘密鍵 w の生成
    for (i = 0; i < N; i++)
        pub[i] = w * sosi[i] % P;              // 公開鍵 pub の生成
    *pX = X, *pP = P, *pw = w;

    for (i = 1; i < N; i++) {  
      NTL_DtoB(sosi[i], binary_number);
    }
}
 
ZZ encrypt(const int *m, ZZ *pub, int n)
{
    ZZ M;
    M = 0;
    for (int i = 0; i < n; i++)
        if (m[i]) M += pub[i];
    return M;
}
 
int decrypt(ZZ C, const ZZ *si, const ZZ *so,
        ZZ X, ZZ P, ZZ inv_w, int *m, int n)
{
    ZZ M = C * inv_w % P;
    ZZ Q = M / X, R = M % X;
    for (int i = 0; i < n; i++)
        if (i & 1)
            if (R >= si[i])
                m[i] = 1, R -= si[i], Q -= so[i];
            else
                m[i] = 0;
        else
            if ((Q >> i) % 2 == 1)       //2 if (Q % (1 << i+1) == 1 << i)
                m[i] = 1, R -= si[i], Q -= so[i];
            else
                m[i] = 0;
    return R != 0 || Q != 0;  // 0:成功, 0以外:失敗
}
 
int main(void)
{
    ZZ si[N], so[N];   // 秘密鍵
    ZZ X, P, w, inv_w; // 秘密鍵
    ZZ pub[N];  // 公開鍵
    int m[N];   // 入力メッセージ
    int n;      // 入力ビット長
    ZZ C;       // 暗号文
    int d[N];   // 復号データ
 
    srand(time(0));
    generate_keys(si, so, pub, &X, &P, &w);
    inv_w = inverse(w, P);
    print_array("si", si, N);
    print_array("so", so, N);
    cout << "  X = " << X << "\n";
    cout << "  P = " << P << "\n";
    cout << "  w = " << w << "\n";
    cout << "  inv_w = " << inv_w << "\n";
    print_array("public key", pub, N);
        
    while ((n = input_message(m)) != 0) {
        cout << "  length = " << n << "\n";
        print_bin("message input ", m, n);
        C = encrypt(m, pub, n);
        cout << "  cypher text = " << C << "\n";
        decrypt(C, si, so, X, P, inv_w, d, n);
        print_bin("decrypted data", d, n);
    }
    return 0;
}

かずま · #36

コード:

#include <NTL/ZZ.h>
#include <stdlib.h>  // srand, rand
#include <time.h>    // time
 
using namespace std;
using namespace NTL;
 
#define N 14
#define DISP_N 14
 
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)   // a の逆元 (mod b)
{
    ZZ 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 ZZ *a, int n)
{
    cout << "  " << name << " = [ " << a[0];
    if (n > DISP_N) n = DISP_N;
    for (int i = 1; i < n; i++) cout << " " << a[i];
    cout << " ]\n";
}
 
void print_bin(const char *name, const int *a, int n)
{
    cout << "  " << name << " = [ " << a[0];
    for (int i = 1; i < n; i++) cout << a[i];
    cout << " ]\n";
}
 
void print_bin(const char *name, ZZ& v)
{
    cout << "  " << name << " = [ ";
    for (int i = 32; --i >= 0; )
        cout << (v >> i) % 2;
    cout << " ]\n";
}
 
int input_message(int *m)
{
    string buf;
    cout << ">> ";
    if (!getline(cin, buf) || buf.size() > N) return 0;
    int i;
    for (i = 0; i < buf.size() && (buf[i] | 1) == '1'; i++)
        m[i] = buf[i] - '0';
    return i;
}
 
void generate_keys(ZZ *si, ZZ *so, ZZ *pub, ZZ *pX, ZZ *pP, ZZ *pw)
{
    ZZ sosi[N], X(0), P, w, one(1);
    int i = N;
    while (--i >= 0) {
        if (i & 1)  // i が奇数
            X += si[i] = X + 1 + rand() % 10;   // 秘密鍵 si の生成
        else        // i が偶数
            X += si[i] = si[i+1] + 1 + rand() % 10;  // ダミーの si
        //print_bin("si", si[i]);
    }
    X += 1 + rand() % 10;               // 秘密鍵 X の生成
    cout << "  X = " << X << endl;
    X = one << (N + 1);                 // 秘密鍵 X の生成(これを使う)
    for (i = 0; i < N; i++) {
        int k = N - i;
        ZZ t = one << (k - 1);
        t = rand() & (t - 1) | t;       // t は kビットの乱数
        if ((i & 1) == 0) t |= 1;       // i が偶数なら t を奇数にする
        so[i] = t << i;                 // 秘密鍵 so の生成
        print_bin("so", so[i]);
    }
    for (P = i = 0; i < N; i++) {
        P += sosi[i] = so[i] * X + si[i];
        print_bin("sosi", sosi[i]);
    }
    P += 1 + rand() % 10;                       // 秘密鍵 P の生成
    for (w = P / 2; gcd(w, P) != 1; w++) ;      // 秘密鍵 w の生成
    for (i = 0; i < N; i++)
        pub[i] = w * sosi[i] % P;               // 公開鍵 pub の生成
    *pX = X, *pP = P, *pw = w;
}
 
ZZ encrypt(const int *m, ZZ *pub, int n)
{
    ZZ M(0);
    for (int i = 0; i < n; i++)
        if (m[i]) M += pub[i];
    return M;
}
 
int decrypt(ZZ C, const ZZ *si, const ZZ *so,
        ZZ X, ZZ P, ZZ inv_w, int *m, int n)
{
    ZZ M = C * inv_w % P;
    ZZ Q = M / X, R = M % X;
    for (int i = 0; i < n; i++)
        if (i & 1)
            if (R >= si[i])
                m[i] = 1, R -= si[i], Q -= so[i];
            else
                m[i] = 0;
        else
            if ((Q >> i) % 2 == 1)   // Q ≡  1<<i (mod 1<<(i+1))
                m[i] = 1, R -= si[i], Q -= so[i];
            else
                m[i] = 0;
    return R != 0 || Q != 0;  // 0:成功, 0以外:失敗
}
 
int main(void)
{
    ZZ si[N], so[N];   // 秘密鍵   super-increasing, shifted-odd
    ZZ X, P, w, inv_w; // 秘密鍵   M = so*X + si, pub = M*w % P
    ZZ pub[N];  // 公開鍵          public key
    int m[N];   // 入力メッセージ  message input
    int n;      // 入力ビット長    number of bits
    ZZ C;       // 暗号文          cypher text
    int d[N];   // 復号データ      decrypted data
 
    srand(time(0));
    generate_keys(si, so, pub, &X, &P, &w);
    inv_w = inverse(w, P);
    print_array("si", si, N);
    print_array("so", so, N);
    cout << "  X = " << X << "\n";
    cout << "  P = " << P << "\n";
    cout << "  w = " << w << "\n";
    cout << "  inv_w = " << inv_w << "\n";
    print_array("public key", pub, N);
        
    while ((n = input_message(m)) != 0) {
        cout << "  length = " << n << "\n";
        print_bin("message input ", m, n);
        C = encrypt(m, pub, n);
        cout << "  cypher text = " << C << "\n";
        decrypt(C, si, so, X, P, inv_w, d, n);
        print_bin("decrypted data", d, n);
    }
    return 0;
}

間違いがあると思います。
よく理解して、詳しい解説をお願いします。

ライトニング · #37

No.36を課題で見せたところ
とりあえず100bit以上でも動くようにしないといけないのですが小さいビット数だとうまく動くのですが
大きいビット数にすると実行したらSOとSIがうまく足し合わさらない状態です
またここがあまり理解できてないのてすが最初に画像に書いてあるe1 e2を与えないといけないみたいです。

またNo36のプログラムのnはどうなってるのでしょうか？
縦のビット数以上に横のビット数がいるのいわれたのですがそれは作れているのでしょうか？

ライトニング · #38

とりあえずe1e2はいいみたいなので
後はsoが32ビット以上にしてしたまうとうまくつくれていないというか多分kがint型なので大きい値にならないのがダメみたいです。
そこでkをZZにしたいのですがうまく出来ていない状態です。

かずま · #39

ライトニングさんが書きました:No.36を課題で見せたところ

誰に見せたのですか？

ライトニングさんが書きました:縦のビット数以上に横のビット数がいるのいわれたのですがそれは作れているのでしょうか？

何のことかわかりません。

ライトニングさんが書きました: とりあえず100bit以上でも動くようにしないといけないのですが小さいビット数だとうまく動くのですが
大きいビット数にすると実行したらSOとSIがうまく足し合わさらない状態です

そんなことはないはずです。32ビットしか表示しないからそう見えるだけなのではありませんか？

ライトニングさんが書きました:またここがあまり理解できてないのてすが最初に画像に書いてあるe1 e2を与えないといけないみたいです。

あとから、あとからどんどん条件を追加されても困ります。

ライトニングさんが書きました:またNo36のプログラムのnはどうなってるのでしょうか？

#define N 14 のことですよね。
N は偶数であれば何でもいいはずです。

#define N 50 にして、表示のやり方をちょっと変更し、
main() ではなく、generate_keys() の中で行うようにしてみました。
N を 20 や 100 にして試したらどうなりますか？

コード:

#include <NTL/ZZ.h>
#include <stdlib.h>  // srand, rand
#include <time.h>    // time
 
using namespace std;
using namespace NTL;
 
#define N 50
 
ZZ gcd(ZZ a, ZZ b)   // 最大公約数
{
    ZZ r;
    while (b != 0) r = a % b, a = b, b = r;
    return a;
}
 
ZZ inverse(const ZZ& a, const ZZ& b)   // a の逆元 (mod b)
{
    ZZ 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_bin(const char *name, const int *a, int n)
{
    cout << "  " << name << " = " << a[0];
    for (int i = 1; i < n; i++) cout << a[i];
    cout << endl;
}
 
void print_bin(const char *name, const ZZ& v)
{
    cout << "  " << name << " = ";
    for (int i = (N+1)*2; --i >= 0; ) cout << (v >> i) % 2;
    cout << " : " << v << endl;
}
 
int input_message(int *m)
{
    string buf;
    cout << ">> ";
    if (!getline(cin, buf) || buf.size() > N) return 0;
    int i;
    for (i = 0; i < buf.size() && (buf[i] | 1) == '1'; i++)
        m[i] = buf[i] - '0';
    return i;
}
 
void generate_keys(ZZ *si, ZZ *so, ZZ *pub, ZZ& X, ZZ& P, ZZ& inv_w)
{
    ZZ sosi[N], one(1), w;
    int i = N;
    X = 0;
    while (--i >= 0) {
        if (i & 1)  // i が奇数
            X += si[i] = X + 1 + rand() % 10;   // 秘密鍵 si の生成
        else        // i が偶数
            X += si[i] = si[i+1] + 1 + rand() % 10;  // ダミーの si
    }
    for (i = 0; i < N; i++)
        print_bin("  si", si[i]);
    X += 1 + rand() % 10;               // 秘密鍵 X の生成(使用しない)
    cout << "     X = " << X << endl;
    for (i = 0; i < N; i++) {
        int k = N - i;
        ZZ t = one << (k - 1);
        t = rand() & (t - 1) | t;       // t は kビットの乱数
        if ((i & 1) == 0) t |= 1;       // i が偶数なら t を奇数にする
        so[i] = t << i;                 // 秘密鍵 so の生成
        print_bin("  so", so[i]);
    }
    X = one << (N + 1);                 // 秘密鍵 X の生成(使用する)
    cout << "     X = " << X << endl;
    for (P = i = 0; i < N; i++) {
        P += sosi[i] = so[i] * X + si[i];   // sosi の生成
        print_bin("sosi", sosi[i]);
    }
    P += 1 + rand() % 10;                   // 秘密鍵 P の生成
    cout << "     P = " << P << endl;
    for (w = P / 2; gcd(w, P) != 1; w++) ;  // 秘密鍵 w の生成
    cout << "     w = " << w << endl;
    inv_w = inverse(w, P);                  // inv_w
    cout << " inv_w = " << inv_w << endl;
    for (i = 0; i < N; i++) {
        pub[i] = w * sosi[i] % P;       // 公開鍵 pub の生成
        print_bin(" pub", pub[i]);
    }
}
 
ZZ encrypt(const int *m, ZZ *pub, int n)
{
    ZZ M(0);
    for (int i = 0; i < n; i++)
        if (m[i]) M += pub[i];
    return M;
}
 
int decrypt(ZZ C, const ZZ *si, const ZZ *so,
        ZZ X, ZZ P, ZZ inv_w, int *m, int n)
{
    ZZ M = C * inv_w % P;
    ZZ Q = M / X, R = M % X;
    for (int i = 0; i < n; i++)
        if (i & 1)
            if (R >= si[i])
                m[i] = 1, R -= si[i], Q -= so[i];
            else
                m[i] = 0;
        else
            if ((Q >> i) % 2 == 1)   // Q ≡  1<<i (mod 1<<(i+1))
                m[i] = 1, R -= si[i], Q -= so[i];
            else
                m[i] = 0;
    return R != 0 || Q != 0;  // 0:成功, 0以外:失敗
}
 
int main(void)
{
    ZZ si[N];   // 秘密鍵   super-increasing
    ZZ so[N];   // 秘密鍵   shifted-odd
    ZZ X;       // 秘密鍵   sosi = so * X + si,
    ZZ P;       // 秘密鍵   pub = sosi * w % P
    ZZ inv_w;   // 秘密鍵   inv_w = inverse(w, P)
    ZZ pub[N];  // 公開鍵   public key

    int m[N];   // 入力メッセージ  message input
    int n;      // 入力ビット長    number of bits
    ZZ  C;      // 暗号文          cypher text
    int d[N];   // 復号データ      decrypted data
 
    srand(time(0));
    generate_keys(si, so, pub, X, P, inv_w);

    while ((n = input_message(m)) != 0) {
        cout << "  length = " << n << endl;
        print_bin("message input ", m, n);
        C = encrypt(m, pub, n);
        cout << "  cypher text = " << C << endl;
        decrypt(C, si, so, X, P, inv_w, d, n);
        print_bin("decrypted data", d, n);
    }
    return 0;
}

実行結果

コード:

    si = 000000000000000000000000000000000000000000000000000000000000011111000000110111101011011000001101111100 : 2131237897084
    si = 000000000000000000000000000000000000000000000000000000000000011111000000110111101011011000001101111001 : 2131237897081
    si = 000000000000000000000000000000000000000000000000000000000000001010010101100111111001001000000100101101 : 710412632365
    si = 000000000000000000000000000000000000000000000000000000000000001010010101100111111001001000000100100110 : 710412632358
    si = 000000000000000000000000000000000000000000000000000000000000000011011100100010101000011000000001101010 : 236804210794
    si = 000000000000000000000000000000000000000000000000000000000000000011011100100010101000011000000001100001 : 236804210785
    si = 000000000000000000000000000000000000000000000000000000000000000001001001100000111000001000000000100000 : 78934736928
    si = 000000000000000000000000000000000000000000000000000000000000000001001001100000111000001000000000011111 : 78934736927
    si = 000000000000000000000000000000000000000000000000000000000000000000011000100000010010101101010101100010 : 26311578978
    si = 000000000000000000000000000000000000000000000000000000000000000000011000100000010010101101010101011110 : 26311578974
    si = 000000000000000000000000000000000000000000000000000000000000000000001000001010110000111001110001111010 : 8770526330
    si = 000000000000000000000000000000000000000000000000000000000000000000001000001010110000111001110001110101 : 8770526325
    si = 000000000000000000000000000000000000000000000000000000000000000000000010101110010000010011010000100111 : 2923508775
    si = 000000000000000000000000000000000000000000000000000000000000000000000010101110010000010011010000100110 : 2923508774
    si = 000000000000000000000000000000000000000000000000000000000000000000000000111010000101011011110000001100 : 974502924
    si = 000000000000000000000000000000000000000000000000000000000000000000000000111010000101011011110000001010 : 974502922
    si = 000000000000000000000000000000000000000000000000000000000000000000000000010011010111001001010000000110 : 324834310
    si = 000000000000000000000000000000000000000000000000000000000000000000000000010011010111001001010000000101 : 324834309
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000110011101000011000101011011 : 108278107
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000110011101000011000101010010 : 108278098
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000010001001101011101100011111 : 36092703
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000010001001101011101100011010 : 36092698
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000000101101111001001110111000 : 12030904
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000000101101111001001110110001 : 12030897
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000000001111010011000101000000 : 4010304
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000000001111010011000100111010 : 4010298
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000000000101000110010110111111 : 1336767
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000000000101000110010110111110 : 1336766
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000000000001101100110010011001 : 445593
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000000000001101100110010010011 : 445587
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000000000000100100010000110011 : 148531
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000000000000100100010000101101 : 148525
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000000000000001100000101101000 : 49512
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000000000000001100000101100110 : 49510
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000001111100 : 16508
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000001110010 : 16498
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001010101111111 : 5503
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001010101111100 : 5500
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011100101101 : 1837
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011100100101 : 1829
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001001100100 : 612
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001001100011 : 611
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011010001 : 209
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011001010 : 202
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000101 : 69
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000 : 64
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010111 : 23
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010110 : 22
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001001 : 9
    si = 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000101 : 5
     X = 6393713691246
    so = 000000000000000000000000000000000000000000000000000010000000000000000000011011011100101010010101011101 : 562950413919581
    so = 000000000000000000000000000000000000000000000000000010000000000000000001001100011101010001010000000110 : 562951236162566
    so = 000000000000000000000000000000000000000000000000000010000000000000000111011001000001111010110011001100 : 562957889547468
    so = 000000000000000000000000000000000000000000000000000010000000000000000011011100010101110101000101100000 : 562953650131296
    so = 000000000000000000000000000000000000000000000000000010000000000000000110101111000110011110001101110000 : 562957186098032
    so = 000000000000000000000000000000000000000000000000000010000000000000111001001001010001001101111101000000 : 563011312213824
    so = 000000000000000000000000000000000000000000000000000010000000000001100101100110001100011110111101000000 : 563059042152256
    so = 000000000000000000000000000000000000000000000000000010000000000011001110100101110001010100001110000000 : 563171777921920
    so = 000000000000000000000000000000000000000000000000000010000000000100111111001100000001011011011100000000 : 563292678764288
    so = 000000000000000000000000000000000000000000000000000010000000001111110101011100010010010101000000000000 : 564038128455680
    so = 000000000000000000000000000000000000000000000000000010000000010111001100110100110110010110010000000000 : 564544272950272
    so = 000000000000000000000000000000000000000000000000000010000000111110010000011011000111110000100000000000 : 567228195866624
    so = 000000000000000000000000000000000000000000000000000010000001101110010010100111011110111011000000000000 : 570529085632512
    so = 000000000000000000000000000000000000000000000000000010000000110101001000110110101010010100000000000000 : 566601592684544
    so = 000000000000000000000000000000000000000000000000000010000001001000001100011100110001011100000000000000 : 567911123369984
    so = 000000000000000000000000000000000000000000000000000010001100000000100110110111110001101000000000000000 : 615768249499648
    so = 000000000000000000000000000000000000000000000000000010010100010010100000110001001111110000000000000000 : 652183020175360
    so = 000000000000000000000000000000000000000000000000000010110000001110111100101101111001100000000000000000 : 775083453186048
    so = 000000000000000000000000000000000000000000000000000010011101011110010100010000001011000000000000000000 : 692576632700928
    so = 000000000000000000000000000000000000000000000000000010101111100101001110101000100100000000000000000000 : 772216472993792
    so = 000000000000000000000000000000000000000000000000000010011100001110100110111100101100000000000000000000 : 687099148763136
    so = 000000000000000000000000000000000000000000000000000010100000111011000100100101010000000000000000000000 : 707746810822656
    so = 000000000000000000000000000000000000000000000000000010010000111000010101111110110000000000000000000000 : 637190589644800
    so = 000000000000000000000000000000000000000000000000000010011110101000010010001111000000000000000000000000 : 697659706834944
    so = 000000000000000000000000000000000000000000000000000010010100110011010000100101000000000000000000000000 : 654433377583104
    so = 000000000000000000000000000000000000000000000000000011111000000100011010000000000000000000000000000000 : 1091018329948160
    so = 000000000000000000000000000000000000000000000000000010101001000111110000001100000000000000000000000000 : 743802637647872
    so = 000000000000000000000000000000000000000000000000000010110100010101100000000000000000000000000000000000 : 793125840748544
    so = 000000000000000000000000000000000000000000000000000010110100110100010101110000000000000000000000000000 : 795245138673664
    so = 000000000000000000000000000000000000000000000000000011100010000110110110100000000000000000000000000000 : 994429347299328
    so = 000000000000000000000000000000000000000000000000000010001101100110011101000000000000000000000000000000 : 622767036694528
    so = 000000000000000000000000000000000000000000000000000011111011001101100110000000000000000000000000000000 : 1104843829673984
    so = 000000000000000000000000000000000000000000000000000010110011010111000100000000000000000000000000000000 : 788835168419840
    so = 000000000000000000000000000000000000000000000000000011100010011010000000000000000000000000000000000000 : 995745217904640
    so = 000000000000000000000000000000000000000000000000000011000011110111110000000000000000000000000000000000 : 861450180493312
    so = 000000000000000000000000000000000000000000000000000011010111010011100000000000000000000000000000000000 : 946920029683712
    so = 000000000000000000000000000000000000000000000000000010101111001011000000000000000000000000000000000000 : 770414053687296
    so = 000000000000000000000000000000000000000000000000000011011100111000000000000000000000000000000000000000 : 971418523140096
    so = 000000000000000000000000000000000000000000000000000011100010111100000000000000000000000000000000000000 : 998081680113664
    so = 000000000000000000000000000000000000000000000000000010110000010000000000000000000000000000000000000000 : 775155697582080
    so = 000000000000000000000000000000000000000000000000000010010001010000000000000000000000000000000000000000 : 638816255737856
    so = 000000000000000000000000000000000000000000000000000011000011000000000000000000000000000000000000000000 : 857619069665280
    so = 000000000000000000000000000000000000000000000000000011100011000000000000000000000000000000000000000000 : 998356558020608
    so = 000000000000000000000000000000000000000000000000000011111100000000000000000000000000000000000000000000 : 1108307720798208
    so = 000000000000000000000000000000000000000000000000000011000100000000000000000000000000000000000000000000 : 862017116176384
    so = 000000000000000000000000000000000000000000000000000011010000000000000000000000000000000000000000000000 : 914793674309632
    so = 000000000000000000000000000000000000000000000000000011010000000000000000000000000000000000000000000000 : 914793674309632
    so = 000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000 : 562949953421312
    so = 000000000000000000000000000000000000000000000000000011000000000000000000000000000000000000000000000000 : 844424930131968
    so = 000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000 : 562949953421312
     X = 2251799813685248
  sosi = 010000000000000000000011011011100101010010101011101000000000011111000000110111101011011000001101111100 : 1267651637178145740207155938172
  sosi = 010000000000000000001001100011101010001010000000110000000000011111000000110111101011011000001101111001 : 1267653488704746167209321923449
  sosi = 010000000000000000111011001000001111010110011001100000000000001010010101100111111001001000000100101101 : 1267668470795628865630519984429
  sosi = 010000000000000000011011100010101110101000101100000000000000001010010101100111111001001000000100100110 : 1267658924479082621803230953766
  sosi = 010000000000000000110101111000110011110001101110000000000000000011011100100010101000011000000001101010 : 1267666886768319943364124442730
  sosi = 010000000000000111001001001010001001101111101000000000000000000011011100100010101000011000000001100001 : 1267788767945775875123614679137
  sosi = 010000000000001100101100110001100011110111101000000000000000000001001001100000111000001000000000100000 : 1267896246212244260923811856416
  sosi = 010000000000011001110100101110001010100001110000000000000000000001001001100000111000001000000000011111 : 1268150104597369319157334573087
  sosi = 010000000000100111111001100000001011011011100000000000000000000000011000100000010010101101010101100010 : 1268422349091687971042326402402
  sosi = 010000000001111110101011100010010010101000000000000000000000000000011000100000010010101101010101011110 : 1270100952567876202262149387614
  sosi = 010000000010111001100110100110110010110010000000000000000000000000001000001010110000111001110001111010 : 1271240688646496281858534513786
  sosi = 010000000111110010000011011000111110000100000000000000000000000000001000001010110000111001110001110101 : 1277284345769483282911294889077
  sosi = 010000001101110010010100111011110111011000000000000000000000000000000010101110010000010011010000100111 : 1284717288729305423194687091751
  sosi = 010000000110101001000110110101010010100000000000000000000000000000000010101110010000010011010000100110 : 1275873360840820955377093915686
  sosi = 010000001001000001100011100110001011100000000000000000000000000000000000111010000101011011110000001100 : 1278822161794309862481001298956
  sosi = 010001100000000100110110111110001101000000000000000000000000000000000000111010000101011011110000001010 : 1386586829496598671399933295626
  sosi = 010010100010010100000110001001111110000000000000000000000000000000000000010011010111001001010000000110 : 1468585603319557985417129923590
  sosi = 010110000001110111100101101111001100000000000000000000000000000000000000010011010111001001010000000101 : 1745332775474861526738181854213
  sosi = 010011101011110010100010000001011000000000000000000000000000000000000000000110011101000011000101011011 : 1559543932478706107731617788251
  sosi = 010101111100101001110101000100100000000000000000000000000000000000000000000110011101000011000101010010 : 1738876910012100169447054258514
  sosi = 010011100001110100110111100101100000000000000000000000000000000000000000000010001001101011101100011111 : 1547209735168122143585245510431
  sosi = 010100000111011000100100101010000000000000000000000000000000000000000000000010001001101011101100011010 : 1593704136746785243585967471386
  sosi = 010010000111000010101111110110000000000000000000000000000000000000000000000000101101111001001110111000 : 1434825651044153953595331941304
  sosi = 010011110101000010010001111000000000000000000000000000000000000000000000000000101101111001001110110001 : 1570989997866631639854715737009
  sosi = 010010100110011010000100101000000000000000000000000000000000000000000000000000001111010011000101000000 : 1473652957711041142281622860096
  sosi = 011111000000100011010000000000000000000000000000000000000000000000000000000000001111010011000100111010 : 2456754872104457116254400753978
  sosi = 010101001000111110000001100000000000000000000000000000000000000000000000000000000101000110010110111111 : 1674894640874074199290866329023
  sosi = 010110100010101100000000000000000000000000000000000000000000000000000000000000000101000110010110111110 : 1785960620426527055343531615678
  sosi = 010110100110100010101110000000000000000000000000000000000000000000000000000000000001101100110010011001 : 1790732855099455804010683354265
  sosi = 011100010000110110110100000000000000000000000000000000000000000000000000000000000001101100110010010011 : 2239255818971769566803834358931
  sosi = 010001101100110011101000000000000000000000000000000000000000000000000000000000000000100100010000110011 : 1402346697198052154884116071475
  sosi = 011111011001101100110000000000000000000000000000000000000000000000000000000000000000100100010000101101 : 2487887129811173046761430336557
  sosi = 010110011010111000100000000000000000000000000000000000000000000000000000000000000000001100000101101000 : 1776298885276166938979278569832
  sosi = 011100010011010000000000000000000000000000000000000000000000000000000000000000000000001100000101100110 : 2242218896155645022911038800230
  sosi = 011000011110111110000000000000000000000000000000000000000000000000000000000000000000000100000001111100 : 1939813355933963222633337077884
  sosi = 011010111010011100000000000000000000000000000000000000000000000000000000000000000000000100000001110010 : 2132274346416612187246560297074
  sosi = 010101111001011000000000000000000000000000000000000000000000000000000000000000000000000001010101111111 : 1734818222553549782736760214911
  sosi = 011011100111000000000000000000000000000000000000000000000000000000000000000000000000000001010101111100 : 2187440049417266945746752509308
  sosi = 011100010111100000000000000000000000000000000000000000000000000000000000000000000000000000011100101101 : 2247480141322607889079360030509
  sosi = 010110000010000000000000000000000000000000000000000000000000000000000000000000000000000000011100100101 : 1745495455392386187607765157669
  sosi = 010010001010000000000000000000000000000000000000000000000000000000000000000000000000000000001001100100 : 1438486325649611879432782348900
  sosi = 011000011000000000000000000000000000000000000000000000000000000000000000000000000000000000001001100011 : 1931186461285193228842633790051
  sosi = 011100011000000000000000000000000000000000000000000000000000000000000000000000000000000000000011010001 : 2248099111342250579216809590993
  sosi = 011111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000011001010 : 2495687119199326634196634435786
  sosi = 011000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000101 : 1941089981599476271041826783301
  sosi = 011010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000 : 2059932225370872777432142708800
  sosi = 011010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010111 : 2059932225370872777432142708759
  sosi = 010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010110 : 1267650600228229401496703205398
  sosi = 011000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001001 : 1901475900342344102245054808073
  sosi = 010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000101 : 1267650600228229401496703205381
     P = 83042766741009965529306151553651
     w = 41521383370504982764653075776825
 inv_w = 83042766741009965529306151553649
   pub = 010000001001011010011000111011011001111110101010000100000001001101100010001011001100011100100010110101 : 82408940922420892659202573584565
   pub = 000100000100101101001000100010110001001110111111100100000000011111000000110111101011011000001101111101 : 40887556626152609681048414815101
   pub = 000100000100101100101111110000011110101000110011001100000000101001010110011111100100100000010010100011 : 40887549135107168331837815784611
   pub = 010000001001011010001100110111110101010011101001111000000001010111110111110011000101100100100111100000 : 82408937278770424218404536076768
   pub = 010000001001011001111111101100110010101111001000111000000001011011010100010101101101111100101000111110 : 82408933297625805557624089332286
   pub = 000100000100101001101000101111100001011100001011111100000000101100110011000010001100111000010100001001 : 40887488986532094827091268437257
   pub = 010000001001010100000100010000011010101100001011111000000001011100011101110110100110000100101001100011 : 82408818617903843398844245625443
   pub = 000100000100100000010010111101100001000011000111111100000000101101111100100011000101000000010100101010 : 40887308318206298105074408490282
   pub = 010000001001000110011101111001000110111010001111111000000001011100110110010110111000110001111111000010 : 82408555566464121543784988352450
   pub = 010000001000011011000100111000000011010011111111111000000001011100110110010110111000110001111111000100 : 82407716264726027428175076859844
   pub = 010000000111111101100111010101110011001110111111111000000001011100111110100001101001101011110000110110 : 82407146396686717388376884296758
   pub = 000100000000110100001011101000000111010001111111111100000000101110011101001110001000100111011011111111 : 40882741197620241123197428332287
   pub = 000011111101110100000010110110101010100111111111111100000000101110011111111100011000111010101100100110 : 40879024726140330053055732230950
   pub = 010000000110000101110111001110100011010111111111111000000001011101000001001111111001111111000001100000 : 82404830060589555051617604595808
   pub = 010000000100111001101000110110000110110111111111111000000001011101000010001001111111011010110001101101 : 82403355660112810598065650904173
   pub = 001111011001010111111111001010000110000111111111111000000001011101000010001001111111011010110001101110 : 82349473326261666193606184905838
   pub = 001110111000010000010111100100001101100111111111111000000001011101000010011101010110100100000001110000 : 82308473939350186536597586591856
   pub = 000001000011110001011010011101000000010011111111111100000000101110100001001001110101011111101100110111 : 40648716982767552001283984849719
   pub = 000010001110110011111100010011111010010011111111111100000000101110100001010000010010100010110010001100 : 40741611404265629710787266882700
   pub = 001101001011000101100000000110111100100111111111111000000001011101000010100011110011100111000111001010 : 82173328286003915444582624424394
   pub = 000010010011110010110001100001110110010011111111111100000000101110100001010010011100001110011110101010 : 40747778502920921692860453021610
   pub = 001110000101101110001000010100001100100111111111111000000001011101000010100101111101010010110011100110 : 82245914672636572907513167817958
   pub = 001111000101111001000010101110001100100111111111111000000001011101000010100110101011001100000010010111 : 82325353915487888552508485582999
   pub = 000010001010001100000100011000100110010011111111111100000000101110100001010011001010000111101101100001 : 40735888371571666944725717908321
   pub = 001110110110001101011000010101001100100111111111111000000001011101000010100110111010011111000111010011 : 82305940262154444958165340123603
   pub = 001000101001001000110010101001001100100111111111111000000001011101000010100110111010011111000111010110 : 81814389304957736971178951176662
   pub = 000001100000001110001100100100100110010011111111111100000000101110100001010011011110100001001001011010 : 40683936050067945665007642612314
   pub = 001100111000000100011010101001001100100111111111111000000001011101000010100110111111100101011110010100 : 82149786430796702001634385745812
   pub = 000000110001011011110110010100100110010011111111111100000000101110100001010011100000001101111011101101 : 40626016942955254862647734099693
   pub = 111101111100010001110011010100100110010011111111111100000000101110100001010011100000001101111011110000 : 40401755461019097981251158597360
   pub = 000011001110010011011001010100100110010011111111111100000000101110100001010011100000110010001100100000 : 40820210021905956687211017741088
   pub = 111100010111110110110101010100100110010011111111111100000000101110100001010011100000110010001100100011 : 40277439805599396241272360608547
   pub = 001100111011111110001010101001001100100111111111111000000001011101000010100111000010000010100110111111 : 82154617298371882059816512268735
   pub = 001001111111110010011010101001001100100111111111111000000001011101000010100111000010000010100111000000 : 81921657292932143017850632153536
   pub = 001011111001111011011010101001001100100111111111111000000001011101000010100111000010000110101000110101 : 82072860063042983917989483014709
   pub = 001010101100001100011010101001001100100111111111111000000001011101000010100111000010000110101000111010 : 81976629567801659435682871405114
   pub = 000001001000000001001101010100100110010011111111111100000000101110100001010011100001000011101001111010 : 40653974259228207873284695669370
   pub = 001010010101111010011010101001001100100111111111111000000001011101000010100111000010000111111110110101 : 81949046716301332056432775298997
   pub = 111101111000111101001101010100100110010011111111111100000000101110100001010011100001000100000110100011 : 40397643299843678820113395761571
   pub = 000001000011101101001101010100100110010011111111111100000000101110100001010011100001000100000110100111 : 40648635642808789670849193197991
   pub = 001111000100011010011010101001001100100111111111111000000001011101000010100111000010001000100101000001 : 82323523578185159589589760379201
   pub = 111111111000101101001101010100100110010011111111111100000000101110100001010011100001000100010000001000 : 40555790139862386150231758881800
   pub = 111101111000101101001101010100100110010011111111111100000000101110100001010011100001000100010011010001 : 40397333814833857475044670981329
   pub = 001000011001011010011010101001001100100111111111111000000001011101000010100111000010001000101000001110 : 81794923181410302212207834335758
   pub = 111111110100101101001101010100100110010011111111111100000000101110100001010011100001000100010100010111 : 40550838379705244629132162385175
   pub = 001011001001011010011010101001001100100111111111111000000001011101000010100111000010001000101001010011 : 82012800628324529140590080199251
   pub = 111111000100101101001101010100100110010011111111111100000000101110100001010011100001000100010100101110 : 40491417257819546375937004422446
   pub = 010000001001011010011010101001001100100111111111111000000001011101000010100111000010001000101001101000 : 82408941440895850828557799950952
   pub = 000000000100101101001101010100100110010011111111111100000000101110100001010011100001000100010100110101 : 40570645420333810713530548372789
   pub = 000100000100101101001101010100100110010011111111111100000000101110100001010011100001000100010100110111 : 40887558070390868063904724174135
>> 1011
  length = 4
  message input  = 1011
  cypher text = 205705427336298485209444925445944
  decrypted data = 1011
>> 1101
  length = 4
  message input  = 1101
  cypher text = 205705434827343926558655524476434
  decrypted data = 1101
>>

#define N 100 でも問題ないようですが、何が問題ですか？

ライトニング · #40

課題をだした先輩に見てもらいました

コード:

#include <NTL/ZZ.h>
#include <stdlib.h>  // srand, rand
#include <time.h>    // time
 
using namespace std;
using namespace NTL;
 
#define N 100
#define DISP_N 100
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)   // a の逆元 (mod b)
{
    ZZ 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 ZZ *a, int n)
{
    cout << "  " << name << " = [ " << a[0];
    if (n > DISP_N) n = DISP_N;
    for (long long i = 1; i < n; i++) cout << " " << a[i];
    cout << " ]\n";
}
 
void print_bin(const char *name, const int *a, int n)
{
    cout << "  " << name << " = [ " << a[0];
    for (long long i = 1; i < n; i++) cout << a[i];
    cout << " ]\n";
}
 
void print_bin(const char *name, ZZ& v)
{
    cout << "  " << name << " = [ ";
    for (long long i = 200; --i >= 0; )
        cout << (v >> i) % 2;
    cout << " ]\n";
}
 
int input_message(int *m)
{
    string buf;
    cout << ">> ";
    if (!getline(cin, buf) || buf.size() > N) return 0;
    long long i;
    for (i = 0; i < buf.size() && (buf[i] | 1) == '1'; i++)
        m[i] = buf[i] - '0';
    return i;
}
 
void generate_keys(ZZ *si, ZZ *so, ZZ *pub, ZZ *pX, ZZ *pP, ZZ *pw)
{
    ZZ sosi[N], X(0), P, w, one(1);
    long long i = N;
    while (--i >= 0) {
        if (i & 1)  // i が奇数
            X += si[i] = X + 1 + rand() % 10;   // 秘密鍵 si の生成
        else        // i が偶数
            X += si[i] = si[i+1] + 1 + rand() % 10;  // ダミーの si
        //print_bin("si", si[i]);
    }
    X += 1 + rand() % 10;               // 秘密鍵 X の生成
    cout << "  X = " << X << endl;
    X = one << (N + 1);                 // 秘密鍵 X の生成(これを使う)
    for (i = 0; i < N; i++) {
        long long  k = N - i;
        ZZ t = one << (k - 1);
        t = rand() & (t - 1) | t;       // t は kビットの乱数
        if ((i & 1) == 0) t |= 1;       // i が偶数なら t を奇数にする
        so[i] = t << i;                 // 秘密鍵 so の生成
        print_bin("so", so[i]);
    }
    for (P = i = 0; i < N; i++) {
        P += sosi[i] = so[i] * X + si[i];
        print_bin("sosi", sosi[i]);
    }
    P += 1 + rand() % 10;                       // 秘密鍵 P の生成
    for (w = P / 2; gcd(w, P) != 1; w++) ;      // 秘密鍵 w の生成
    for (i = 0; i < N; i++)
        pub[i] = w * sosi[i] % P;               // 公開鍵 pub の生成
    *pX = X, *pP = P, *pw = w;
}
 
ZZ encrypt(const int *m, ZZ *pub, int n)
{
    ZZ M(0);
    for (int i = 0; i < n; i++)
        if (m[i]) M += pub[i];
    return M;
}
 
int decrypt(ZZ C, const ZZ *si, const ZZ *so,
        ZZ X, ZZ P, ZZ inv_w, int *m, int n)
{
    ZZ M = C * inv_w % P;
    ZZ Q = M / X, R = M % X;
    for (int i = 0; i < n; i++)
        if (i & 1)
            if (R >= si[i])
                m[i] = 1, R -= si[i], Q -= so[i];
            else
                m[i] = 0;
        else
            if ((Q >> i) % 2 == 1)   // Q ≡  1<<i (mod 1<<(i+1))
                m[i] = 1, R -= si[i], Q -= so[i];
            else
                m[i] = 0;
    return R != 0 || Q != 0;  // 0:成功, 0以外:失敗
}
 
int main(void)
{
    ZZ si[N], so[N];   // 秘密鍵   super-increasing, shifted-odd
    ZZ X, P, w, inv_w; // 秘密鍵   M = so*X + si, pub = M*w % P
    ZZ pub[N];  // 公開鍵          public key
    int m[N];   // 入力メッセージ  message input
    int n;      // 入力ビット長    number of bits
    ZZ C;       // 暗号文          cypher text
    int d[N];   // 復号データ      decrypted data
 
    srand(time(0));
    generate_keys(si, so, pub, &X, &P, &w);
    inv_w = inverse(w, P);
    print_array("si", si, N);
    print_array("so", so, N);
    cout << "  X = " << X << "\n";
    cout << "  P = " << P << "\n";
    cout << "  w = " << w << "\n";
    cout << "  inv_w = " << inv_w << "\n";
    print_array("public key", pub, N);
        
    while ((n = input_message(m)) != 0) {
        cout << "  length = " << n << "\n";
        print_bin("message input ", m, n);
        C = encrypt(m, pub, n);
        cout << "  cypher text = " << C << "\n";
        decrypt(C, si, so, X, P, inv_w, d, n);
        print_bin("decrypted data", d, n);
    }
    return 0;
}

e1 e2はもうどうでもいいらしいので
これをコンパイルするとsoの上位ビット？の左部分の0がどんどん大きなって言ってしまって４０bit目以降はほとんど左のbitが０になっているのがダメたいです
それだけ直せば完成らしいのでアドバイスお願いします

ライトニング · #41

先輩に指摘されたのはsoの上ビットにうまく乱数を足せあわせれてないと指摘されました。
本当かずまさんに頼りっぱなしですがアドバイスよろしくお願いします。

かずま · #42

ライトニングさんが書きました: これをコンパイルするとsoの上位ビット？の左部分の0がどんどん大きなって言ってしまって４０bit目以降はほとんど左のbitが０になっているのがダメたいです
それだけ直せば完成らしいのでアドバイスお願いします

rand() が返す値は 31ビットです。これを Nビットにしないと
いけないということでしょうか。それなら、

コード:

    int k = N - i;              // k は int で十分
    ZZ t = one << (k - 1);      // t は        kビットの最小値 (1000...00)
                                // t-1 は、(k-1)ビットの最大値  (111...11)
    ZZ r = one;                 // r を 1から始める
    while (r < t) r *= rand();  // r は kビットより大きい乱数
    t = r & (t - 1) | t;        // t は ちょうど kビットの乱数
    if ((i & 1) == 0) t |= 1;   // i が偶数のとき、t を奇数にする
    so[i] = t << i;             // 奇数シフト数列の生成

k も i も N も 100 とか 200 なので int (32ビット)で十分。
long long (64ビット) にする必要は全くありません。
10ビットが 1000、20ビットが 100万、30ビットが 10億、40ビットが 1兆だから
100ビットは、40+40+20 で、1兆の 1兆倍の 100万倍。
だから 100ビットの整数には ZZ型が必要。
int は 32ビットで 1ビットは符号だから、31ビットの精度で、20億。
100 や 200 はこれで十分。

かずま · #43

かずまさんが書きました:
コード:
    while (r < t) r *= rand();  // r は kビットより大きい乱数

rand() が 0 を返すと困るので、

コード:

    while (r < t) r *= rand() + 1u;  // r は kビットより大きい乱数

1 が 1u と unsigned になっているのは、rand() が RAND_MAX を返した
場合、int ではオーバーフローが起こって、負の値になるからです。

ライトニング · #44

ありがとうございます。おかげで思っている通りに動きました。

何個かプログラムで聞きたいことがあるのですが

1.ダミーのsiは次のsiの値より小さい値という判定をして作っていってるのでしょうか？

2.X(0) one(1)などのカッコはどういう意味がるのでしょうか？Xは２のNbit乗を表してるのでしょうか？

3.if ((i & 1) == 0) t |= 1; この二重カッコや|の意味はどういう意味でしょうか？

4.print_binとprint_arrayの違いはなんでしょうか？

5.soの復号の((Q >> i) % 2 == 1)　この処理Qをibitシフトしてそれを２で割ったあまりが１ならQからsoを引いているのでしょうか？

6.このプログラムを　main?で鍵生成　暗号化　復号を三つに分けるってできるのでしょうか？

7.縦のbitはNですが横のbitもNなのでしょうか？

色々質問が重なって初歩的な質問もあると思いますが申し訳ないのですがせっかくかずまさんが書いてくださったので色々と理解したいのでもしよければご回答お願いします。

かずま · #45

> 1.ダミーのsiは次のsiの値より小さい値という判定をして作っていってるのでしょうか？

次の si は、超増加数列の項ですから、それ以前のすべての項の和より大きくなる
ように作っています。したがって、ダミーの si の値は、次の si の値より小さくなります。

> 2.X(0) one(1)などのカッコはどういう意味がるのでしょうか？Xは２のNbit乗を表してるのでしょうか？

宣言時に変数の初期化をするには、int a = 3; のように書きます。
これは代入ではありません。宣言時の初期化です。

ZZ型の変数は、ZZ a, b; と宣言して、
a = 3; b = a; という代入で値を設定できます。

このうち、b = a; は同じ ZZ型の変数の代入なので問題ありませんが、
a = 3; のほうは、左辺が ZZ型、右辺が int型です。
なぜこれができるかというと、おそらくそういう代入演算子が定義されている
のだと思います。

さて、C++ には、int a = 3; の他に int a(3); という初期化があります。
ZZ型は、ZZ b = a; というように、同じ ZZ型の値による初期化は
= でできますが、ZZ a = 3; のような int による初期化ができないようです。
ZZ a(3) の形の初期化はできます。

そこで、ZZ X, one; X = 0; one = 1; と書く代わりに、
ZZ X(0), one(1); と書きました。

画像で提供された情報では、X は、si の総和より大きければよいとありましたが、
sosi のビットパターンが三角形にならないといけないと言われたので、
2の(N+1)乗にしました。N乗にしなかったのは、si の総和のほうが大きくなる場合
がありそうだったからです。

3.if ((i & 1) == 0) t |= 1; この二重カッコや|の意味はどういう意味でしょうか？

外側の括弧は if文の構文の括弧です。
(i & 1) == 0 の括弧は、演算子の優先順位の問題です。
括弧を省略して、i & 1 == 0 と書くと、i & (1 == 0) の意味になってしまいます。
| はビット単位の OR 演算子です。
t | 1 で t の値の最下位のビットが 1 になった値を演算結果とします。
t |= 1 で、t の最下位ビットが 1 になります。
C か C++ の入門書で AND、OR、Exclusive OR と NOT などのビット演算を
学習してください。

> 4.print_binとprint_arrayの違いはなんでしょうか？

print_array(const char *name, const ZZ *a, intn ) は
ZZ型の配列の要素をスペースで区切って 10進数で、n 個表示するものです。
pub = [ 5356433 330549 4356709 ... ]

print_bin(const char *name, const int *a, intn ) は
0 と 1 だけが入った int型の配列の要素をスペースで区切らずに
n個表示するものです。m = [ 101111010...10 ]

print_bin(const char *name, const ZZ& v) は、
ZZ型の変数 v の値を 2進数で表示するものです。
si = [ 101111010...10 ]

> 5.soの復号の((Q >> i) % 2 == 1)　この処理Qをibitシフトしてそれを２で割ったあまりが１ならQからsoを引いているのでしょうか？

そのあとの Q -= so; で引いています。

> 6.このプログラムを　main?で鍵生成　暗号化　復号を三つに分けるってできるのでしょうか？

generate_keys()、encrypt()、decrypt() の 3つに分けて、main() からそれらを
呼び出しています。
関数に分けずに、main() の中に全部の処理を書けるかという質問ですか？

> 7.縦のbitはNですが横のbitもNなのでしょうか？

縦とか横とか、何のことかわかりません。

ライトニング · #46

関数に分けずに、main() の中に全部の処理を書けるかという質問ですか？
すみません何て言えばいいのか分からないのですがmakefile?みたいなのを使って三つをそれぞれ一つ一つのプログラムにすることは可能なのかみたいなのを聞きたかったです。何言ってるか分からない場合は無視してください。

後最後に質問なのですが
soの数列は二回に一回奇数シフトするようになってるのでしょうか？
何回かコンパイルしてsoの数列を確認したのですが毎回奇数シフトしてるところもあれば二回に一回奇数シフトしてるところもあるのですが
これはtがkbitの乱数だからでしょうか？

かずま · #47

ライトニングさんが書きました:関数に分けずに、main() の中に全部の処理を書けるかという質問ですか？
すみません何て言えばいいのか分からないのですがmakefile?みたいなのを使って三つをそれぞれ一つ一つのプログラムにすることは可能なのかみたいなのを聞きたかったです。何言ってるか分からない場合は無視してください。

引用と、自分の書いた部分とが区別できるように書いてください。
「分割コンパイル」でググってみてください。

ライトニングさんが書きました: soの数列は二回に一回奇数シフトするようになってるのでしょうか？
何回かコンパイルしてsoの数列を確認したのですが毎回奇数シフトしてるところもあれば二回に一回奇数シフトしてるところもあるのですが
これはtがkbitの乱数だからでしょうか？

「何回か実行して」ですよね。
ソースを変更しない限りコンパイルは 1回で済みます。
No.42のコードのコメントで理解できませんか？
so の iが偶数の時は、奇数乱数のシフトですが、
so の iが奇数の時は、乱数のシフトですから、
これが偶数か奇数かは不定です。
No.29のライトニングさんの要求を私が誤解しているのでしょうか？
so に求められる条件を正確に書いてください。

ライトニング · #48

http://www.fastpic.jp/images.php?file=1687480104.jpg

簡単に言うと画像のようなsoを作りたい感じです。siが超増加しない所を奇数シフトしたいような感じです。

かずま · #49

ライトニングさんが書きました:http://www.fastpic.jp/images.php?file=1687480104.jpg

簡単に言うと画像のようなsoを作りたい感じです。siが超増加しない所を奇数シフトしたいような感じです。

N = 10 のとき

コード:

i   kビットの　　ｘ 2[sup]i/2[/sup]
0  10ビットの奇数 x 2[sup]0[/sup]
1   9ビットの乱数 x 2[sup]1[/sup]
2   9ビットの乱数 x 2[sup]1[/sup]
3   8ビットの乱数 x 2[sup]2[/sup]
4   8ビットの乱数 x 2[sup]2[/sup]
5   7ビットの乱数 x 2[sup]3[/sup]
6   7ビットの乱数 x 2[sup]3[/sup]
7   6ビットの乱数 x 2[sup]4[/sup]
8   6ビットの乱数 x 2[sup]4[/sup]
9   5ビットの乱数 x 2[sup]5[/sup]

シフト数が i ではなく、i/2 ということですね。
generate_keys をそのようにしてみました。
decrypt も修正が必要でした。

コード:

#include <NTL/ZZ.h>
#include <stdlib.h>  // srand, rand
#include <time.h>    // time
 
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(const ZZ& a, const ZZ& b)   // a の逆元 (mod b)
{
    ZZ 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_bin(const char *name, const int *a, int n)
{
    cout << "  " << name << " = " << a[0];
    for (int i = 1; i < n; i++) cout << a[i];
    cout << endl;
}
 
void print_bin(const char *name, const ZZ& v)
{
    cout << "  " << name << " = ";
    for (int i = (N+1)*2; --i >= 0; ) cout << (v >> i) % 2;
    cout << " : " << v << endl;
}
 
int input_message(int *m)
{
    string buf;
    cout << ">> ";
    if (!getline(cin, buf) || buf.size() > N) return 0;
    int i;
    for (i = 0; i < buf.size() && (buf[i] | 1) == '1'; i++)
        m[i] = buf[i] - '0';
    return i;
}
 
void generate_keys(ZZ *si, ZZ *so, ZZ *pub, ZZ& X, ZZ& P, ZZ& inv_w)
{
    ZZ sosi[N], one(1), w;
    int i = N;
    X = 0;
    while (--i >= 0) {
        if (i & 1)  // i が奇数
            X += si[i] = X + 1 + rand() % 10;   // 秘密鍵 si の生成
        else        // i が偶数
            X += si[i] = si[i+1] + 1 + rand() % 10;  // ダミーの si
    }
    for (i = 0; i < N; i++)
        print_bin("  si", si[i]);
    X += 1 + rand() % 10;               // 秘密鍵 X の生成(使用しない)
    cout << "     X = " << X << endl;
    for (i = 0; i < N; i++) {
        int k = N - i/2;
        ZZ t = one << (k - 1);
        ZZ r = one;
        while (r < t) r *= rand() + 1u;
        t = r & (t - 1) | t;            // t は kビットの乱数
        if ((i & 1) == 0) t |= 1;       // i が偶数なら t を奇数にする
        so[i] = t << i/2;               // 秘密鍵 so の生成
        print_bin("  so", so[i]);
    }
    X = one << (N + 1);                 // 秘密鍵 X の生成(使用する)
    cout << "     X = " << X << endl;
    for (P = i = 0; i < N; i++) {
        P += sosi[i] = so[i] * X + si[i];   // sosi の生成
        print_bin("sosi", sosi[i]);
    }
    P += 1 + rand() % 10;                   // 秘密鍵 P の生成
    cout << "     P = " << P << endl;
    for (w = P / 2; gcd(w, P) != 1; w++) ;  // 秘密鍵 w の生成
    cout << "     w = " << w << endl;
    inv_w = inverse(w, P);                  // inv_w
    cout << " inv_w = " << inv_w << endl;
    for (i = 0; i < N; i++) {
        pub[i] = w * sosi[i] % P;       // 公開鍵 pub の生成
        print_bin(" pub", pub[i]);
    }
}
 
ZZ encrypt(const int *m, ZZ *pub, int n)
{
    ZZ M(0);
    for (int i = 0; i < n; i++)
        if (m[i]) M += pub[i];
    return M;
}
 
int decrypt(ZZ C, const ZZ *si, const ZZ *so,
        ZZ X, ZZ P, ZZ inv_w, int *m, int n)
{
    ZZ M = C * inv_w % P;
    ZZ Q = M / X, R = M % X;
    for (int i = 0; i < n; i++)
        if (i & 1)
            if (R >= si[i])
                m[i] = 1, R -= si[i], Q -= so[i];
            else
                m[i] = 0;
        else
            if ((Q >> i/2) % 2 == 1)   // Q ≡  1<<i/2 (mod 1<<(i/2+1))
                m[i] = 1, R -= si[i], Q -= so[i];
            else
                m[i] = 0;
    return R != 0 || Q != 0;  // 0:成功, 0以外:失敗
}
 
int main(void)
{
    ZZ si[N];   // 秘密鍵   super-increasing
    ZZ so[N];   // 秘密鍵   shifted-odd
    ZZ X;       // 秘密鍵   sosi = so * X + si,
    ZZ P;       // 秘密鍵   pub = sosi * w % P
    ZZ inv_w;   // 秘密鍵   inv_w = inverse(w, P)
    ZZ pub[N];  // 公開鍵   public key
 
    int m[N];   // 入力メッセージ  message input
    int n;      // 入力ビット長    number of bits
    ZZ  C;      // 暗号文          cypher text
    int d[N];   // 復号データ      decrypted data
 
    srand(time(0));
    generate_keys(si, so, pub, X, P, inv_w);
 
    while ((n = input_message(m)) != 0) {
        cout << "  length = " << n << endl;
        print_bin("message input ", m, n);
        C = encrypt(m, pub, n);
        cout << "  cypher text = " << C << endl;
        decrypt(C, si, so, X, P, inv_w, d, n);
        print_bin("decrypted data", d, n);
    }
    return 0;
}

これでどうでしょうか？

かずま · #50

すみません。間違えました。
シフト数は、(i+1)/2 ですね。
次のように訂正します。

コード:

        int k = N - (i+1)/2;   // ********
        ZZ t = one << (k - 1);
        ZZ r = one;
        while (r < t) r *= rand() + 1u;
        t = r & (t - 1) | t;            // t は kビットの乱数
        if ((i & 1) == 0) t |= 1;       // i が偶数なら t を奇数にする
        so[i] = t << (i+1)/2;  // ********
        print_bin("  so", so[i]);

コード:

            if ((Q >> (i+1)/2) % 2 == 1)   // ********
                m[i] = 1, R -= si[i], Q -= so[i];

かずま · #51

かずまさんが書きました:

ライトニングさんが書きました:

コード:

i   kビットの　　ｘ 2[sup]i/2[/sup]
0  10ビットの奇数 x 2[sup]0[/sup]
1   9ビットの乱数 x 2[sup]1[/sup]
2   9ビットの乱数 x 2[sup]1[/sup]
3   8ビットの乱数 x 2[sup]2[/sup]
4   8ビットの乱数 x 2[sup]2[/sup]
5   7ビットの乱数 x 2[sup]3[/sup]
6   7ビットの乱数 x 2[sup]3[/sup]
7   6ビットの乱数 x 2[sup]4[/sup]
8   6ビットの乱数 x 2[sup]4[/sup]
9   5ビットの乱数 x 2[sup]5[/sup]

こちらも訂正しておきます。

コード:

i   kビットの.. x 2[sup](i＋1)/2[/sup]  kビットの.. << (i+1)/2
0  10ビットの奇数 x 2[sup]0[/sup]    10ビットの奇数 << 0
1   9ビットの乱数 x 2[sup]1[/sup]     9ビットの乱数 << 1
2   9ビットの奇数 x 2[sup]1[/sup]     9ビットの奇数 << 1
3   8ビットの乱数 x 2[sup]2[/sup]     8ビットの乱数 << 2
4   8ビットの奇数 x 2[sup]2[/sup]     8ビットの奇数 << 2
5   7ビットの乱数 x 2[sup]3[/sup]     7ビットの乱数 << 3
6   7ビットの奇数 x 2[sup]3[/sup]     7ビットの奇数 << 3
7   6ビットの乱数 x 2[sup]4[/sup]     6ビットの乱数 << 4
8   6ビットの奇数 x 2[sup]4[/sup]     6ビットの奇数 << 4
9   5ビットの乱数 x 2[sup]5[/sup]     5ビットの乱数 << 5

		8月 2025
日	月	火	水	木	金	土
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31