ライトニング さんが書きました:wやbの単体の意味は分かるのですが中で何が行われてるのかがよく分からないのがほとんどの状態です....
(long long)*rのlong longを以前に説明してもらいましたが
これにrをかけてるのは何故でしょうか?またなぜlong longなのでしょうか?
*r は、main の r を参照するため、と説明したはずです。掛け算ではありません。
(long long) は #define N 20 のときに掛け算がオーバーフローしないようにするものです。
今は、#define N 10 ですから、不要です。削除してかまいません。
ライトニング さんが書きました:
print_arrayがいまいちどういうものかピンとこないのですが( " w",w)とか (" sum = %d\n", sum)のwやsumの手前の空白部分などが
よくわからないのですがこれは何を表示させてるのでしょうか?("%d",w)とかはだめなのでしょうか?
現在の表示は次の通り。
コード:
w = [ 5 13 28 48 96 196 390 779 1557 3117 ]
sum = 6229
Private key
w = [ 5 13 28 48 96 196 390 779 1557 3117 ]
q = 6233
r = 3116
Public key
b = [ 3114 3110 6219 6209 6185 6135 6038 2727 2338 1558 ]
Enter 10 binary digits
123456789.
w や sum の前の空白がないと、表示は次のようになります。ただそれだけのことです。
コード:
w = [ 5 13 28 48 96 196 390 779 1557 3117 ]
sum = 6229
Private key
w = [ 5 13 28 48 96 196 390 779 1557 3117 ]
q = 6233
r = 3116
Public key
b = [ 3114 3110 6219 6209 6185 6135 6038 2727 2338 1558 ]
Enter 10 binary digits
123456789.
ライトニング さんが書きました:
int*q int*rなどの*はintにqをかけるという意味でしょうか?それとも只*qというのを宣言してるだけでしょうか?
* はポインタです。
int *q は、q がポインタで、そのポインタは int を指しますよ。という意味です。
q は int ではありません。*q が int で、関数 generate_key() の呼出し元である main() の q を参照します。
鍵の生成を genearate_key() という別関数にしたため、混乱しているようですね。
では、関数にせず、main() に戻します。次のプログラムなら理解できますか?
コード:
#include <stdio.h> // fgets, printf
#include <stdlib.h> // rand, srand
#include <time.h> // time
#define N 10
int gcd(int a, int b) // 最大公約数
{
int r;
while (b)
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[N]) // 配列の表示
{
int i;
printf("%s = [", name);
for (i = 0; i < N; i++) printf(" %d", a[i]);
printf(" ]\n");
}
int input_data(int a[N]) // データの入力
{
int i;
char buf[256];
printf("\nEnter %d binary digits\n", N);
printf("%.*s\n", N, "123456789.123456789.123456789.12");
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 == N; // i が N だったら 1 を、そうでなかったら 0 を返す
}
int encrypt(const int a[N], const int b[N]) // 暗号化
{
int i, c = 0;
for (i = 0; i < N; i++)
if (a[i] == 1) c += b[i];
return c;
}
int decrypt(int c, const int w[N], int q, int r, int s[N]) // 復号
{
int i, sum = c * inverse(r, q) % q;
for (i = N; --i >= 0; ) {
if (sum >= w[i])
sum -= w[i], s[i] = 1;
else
s[i] = 0;
}
return sum; // 復号できれば 0、そうでなければ正の値を返す
}
int main(void)
{
int w[N], q, r; // 秘密鍵
int b[N]; // 公開鍵
int a[N]; // 暗号化する前のデータ
int c; // 暗号化されたデータ
int s[N]; // 復号されたデータ
int i, sum = 0;
srand(time(0));
for (i = 0; i < N; i++) // 超増加列(秘密鍵)の生成
sum += w[i] = sum + 1 + rand() % 10;
print_array(" w", w);
printf(" sum = %d\n", sum);
q = sum + 1 + rand() % 10; // 秘密鍵 q の生成
for (r = q /2; gcd(r, q) != 1; ++r) ; // 秘密鍵 r の生成
for (i = 0; i < N; i++) // 公開鍵の生成
b[i] = r * w[i] % q;
printf("Private key\n");
print_array(" w", w);
printf(" q = %d\n r = %d\n", q, r);
printf("Public key\n");
print_array(" b", b);
while (input_data(a)) { // データの入力
print_array(" a", a); // 入力データの表示
c = encrypt(a, b); // 暗号化
printf(" c = %d\n", c); // 暗号化されたデータの表示
decrypt(c, w, q, r, s); // 復号
print_array(" s", s); // 復号されたデータの表示
}
return 0;
}
さらに質問です。Wikipedia の
「Merkle-Hellmanナップサック暗号」は見ていますか?