格納

フォーラムルール
フォーラムルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら

返信する

Advanced BBCode Box 3 :: ヘルプ ページ Advanced BBCode Box 3 (aka ABBC3)  
選択テキストを切り取る (カット) 選択テキストをコピー コピーしたテキストを貼り付け (ペースト) 選択したテキストから全ての BBCode タグを削除します。 箇条書きリスト 連番付き箇条書きリスト リスト項目 水平線 太字 斜体 下線 取り消し線 上付き文字 下付き文字 フェードイン / アウト テキスト グラデーション 正当テキスト 左揃え 中央ぞろえ 右揃え 整形済みテキスト
タブインデント挿入 コード 引用 本題と外れた内容を囲むオフトピックテキストを挿入します。 Web アドレス Eメール 画像を挿入します。 サムネイル画像を挿入します。 Youtube 動画 を挿入します。 ニコニコ動画を挿入します。

BBCode: ON
[img]: ON
[flash]: OFF
[url]: ON
スマイリー: OFF
トピックのレビュー
このトピックは既に解決しています
   

展開ビュー トピックのレビュー: 格納

Re: 格納

投稿記事 by かずま » 2015年12月14日(月) 22:58

この続きは、Merkle-Hellmanナップサック暗号 で行います。
ここには、もう返信しないでください。

Re: 格納

投稿記事 by Dixq (管理人) » 2015年12月14日(月) 20:48

一つのトピックが長くなりすぎです。

1トピック1質問としてください。
また、トピックタイトルは質問内容が分かるように名前を付け、内容が変わったら新しくトピックを立ててください。
現在過去ログとして全く意味をなさないものになっています。

Re: 格納

投稿記事 by かずま » 2015年12月14日(月) 19:32

まず、引用は、quoteタグを使うとか、行頭に > を付けるとかして、
引用と自分の文章との区別がつくように書いてください。

No.103 で、かずま さんが書きました:そこで、私は、r を q/2 と q の間と考え、q/2 にしました。
r は q と互いに素でなければなりませんから、gdc(r, q) == 1 になるまで、
r を 1ずつ増やしていって、適切な値を求めています。

gdc は gcd の間違いでした。申し訳ありません。

> この文はそういう意味じゃないのでしょうか?

「この文」というのは、No.103 の文ですね。
「そういう意味」というのは、No.115 のライトニングさんの解釈でしょうか?

NO.115 で、ライトニング さんが書きました:qの値を決めたらそれを2で割りその値を+1ずつしていき最初のqの値と素になればその値がrとなるという解釈

この解釈では、+1 してから、互いに素のチェックをしているようにも取れます。
それは間違い。互いに素であるかどうかのチェックが先です。

NO.117 ライトニング さんが書きました:qを求め2/qを計算しそこからgdc(r, q) == 1 になるようなqを+1増やしていき
gdc(r, q) == 1 になった時その値がrになるってことではないのでしょうか?

「2/q」は「q/2」の間違い。
「qを+1増やしていき」は、「r を 1ずつ増やしていき」の間違い。

NO.117 ライトニング さんが書きました:それとも2/qをした時点でその値がrになりそのrがgdc(r, q) == 1になるまで+1していくという事でしょうか?

「2/q」は「q/2」の間違いですが、「+1していく」が r のことなら、その通りです。
q/2 を計算した時点でそれを仮の r にしないと、gcd(r, q) != 1 のチェックができません。
最初から、gcd(r, q) == 1 なら、その r が決定した値です。
gcd(r, q) が 1 でなければ、r を 1 増やし、また gcd(r, q) のチェックに行きます。
そして、gcd(r, q) == 1 なら、求める r が決定します。

Re: 格納

投稿記事 by ライトニング » 2015年12月14日(月) 16:25

そこで、私は、r を q/2 と q の間と考え、q/2 にしました。
r は q と互いに素でなければなりませんから、gdc(r, q) == 1 になるまで、
r を 1ずつ増やしていって、適切な値を求めています。

この文はそういう意味じゃないのでしょうか?qを求め2/qを計算しそこからgdc(r, q) == 1 になるようなqを+1増やしていき
gdc(r, q) == 1 になった時その値がrになるってことではないのでしょうか?
それとも2/qをした時点でその値がrになりそのrがgdc(r, q) == 1になるまで+1していくという事でしょうか?

Re: 格納

投稿記事 by かずま » 2015年12月14日(月) 16:08

ライトニング さんが書きました:
コード[C++]: 全て選択
1
for (*r = *q /2; gcd(*r, *q) != 1; ++*r) ;

かずまさんが説明してくださったこのfor分なのですがsum以上のqの値を決めるのはどの部分でしょうか?

そのひとつ上の行で、q の値を決めています。

No.86 のプログラム, 53行目 (generat_keys() の中から main() の q と r を参照するので、*q、*r )
コード[C]: 全て選択
1
2
    *q = sum + 1 + rand() % 10;  // 秘密鍵 q の生成
    for (*r = *q /2; gcd(*r, *q) != 1; ++*r) ;  // 秘密鍵 r の生成

No.110 のプログラム, 81行目 (ここは main() の中なので q と r はそのまま)
コード[C]: 全て選択
1
2
    q = sum + 1 + rand() % 10;  // 秘密鍵 q の生成
    for (r = q /2; gcd(r, q) != 1; ++r) ;  // 秘密鍵 r の生成

ライトニング さんが書きました:またqの値を決めたらそれを2で割りその値を+1ずつしていき最初のqの値と素になればその値がrとなるという解釈でいいでしょうか?

No.103 の説明は読んでいないのですか?

Re: 格納

投稿記事 by ライトニング » 2015年12月14日(月) 14:05

みけCATさんも分かり易い説明ありがとうございます。お二方の説明でだいたいは理解してきました。

あと1つ疑問なのですが
コード[C++]: 全て選択
1
for (*r = *q /2; gcd(*r, *q) != 1; ++*r) ;

かずまさんが説明してくださったこのfor分なのですがsum以上のqの値を決めるのはどの部分でしょうか?
またqの値を決めたらそれを2で割りその値を+1ずつしていき最初のqの値と素になればその値がrとなるという解釈でいいでしょうか?

Re: 格納

投稿記事 by かずま » 2015年12月13日(日) 16:25

かずま さんが書きました:
ライトニング さんが書きました:a[i]は秘密鍵の配列要素ですよね?

なんでそうなるの? main() は無視ですか?
コード[C]: 全て選択
1
2
3
4
5
6
7
int main(void)
{
    int w[N], q, r;  // 秘密鍵
    int b[N];        // 公開鍵
    int a[N];  // 暗号化する前のデータ
    int c;     // 暗号化されたデータ
    int s[N];  // 復号されたデータ

秘密鍵は b。
a は暗号する前のデータとはっきり書いてあります。
Wikipedia は無視ですか?
a は alpha、すなわち α。
b は beta、すなわち β。

すみません。
b は公開鍵でした。秘密鍵は w(と q と r)。
しかし、input_data(a) で呼び出された input_data() の中の a が、
暗号化する前のデータであることは確かです。
print_array() の中の a は、呼出しごとに変わります。

Re: 格納

投稿記事 by かずま » 2015年12月13日(日) 16:13

ライトニング さんが書きました:
コード[C++]: 全て選択
1
2
3
4
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;

この部分がまだいまいち理解できてないのですが (!fgets(buf, sizeof buf, stdin)) これが何か全く分からないです。

No.105 に詳しく書いたのに分からないのですか?
No.105 の fgets() や ! の説明のどこが分からないのですか?

ライトニング さんが書きました:またbufは配列をいれる箱?なのは分かりますが

buf は文字列を入れる配列。
buf には、fgets() によりキーボードから文字列が入ります。
配列の各要素 buf[i] には文字が入ります。

ライトニング さんが書きました:buf[i]==1ならa[i]=は1ってのは何故ですか?

buf[i] == '1' です。
キーボードからの入力は文字列ですね。
buf[i] には文字が入っています。
a[i] には数値を入れなければなりません。
buf[i] が文字の '1' なら a[i] には数値の 1 を入れます。

ライトニング さんが書きました:a[i]は秘密鍵の配列要素ですよね?

なんでそうなるの? main() は無視ですか?
コード[C]: 全て選択
1
2
3
4
5
6
7
int main(void)
{
    int w[N], q, r;  // 秘密鍵
    int b[N];        // 公開鍵
    int a[N];  // 暗号化する前のデータ
    int c;     // 暗号化されたデータ
    int s[N];  // 復号されたデータ

秘密鍵は b。
a は暗号する前のデータとはっきり書いてあります。
Wikipedia は無視ですか?
a は alpha、すなわち α。
b は beta、すなわち β。

ライトニング さんが書きました:28行目のfor (i = 0; i < N; i++) printf(" %d", a[i]);
ここでa[i]を表示させるようにしてますが。a[i]の計算はこれより後に計算してるのに何故先に表示するのを持ってきて実行できるのでしょうか?

これは print_array() の中ですね。
ここの a は暗号化する前のデータではありません。
print_array(" w", w) で呼び出されたときは w。
print_array(" b", b) で呼び出されたときは b。
だから、まだ計算していない a や s ではありません。
関数の引数は、呼出し元の引数を引き継ぎます。

Re: 格納

投稿記事 by ライトニング » 2015年12月13日(日) 13:22

コード[C++]: 全て選択
1
2
3
4
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;

この部分がまだいまいち理解できてないのですが (!fgets(buf, sizeof buf, stdin)) これが何か全く分からないです。
またbufは配列をいれる箱?なのは分かりますがbuf[i]==1ならa[i]=は1ってのは何故ですか?
a[i]は秘密鍵の配列要素ですよね?

28行目のfor (i = 0; i < N; i++) printf(" %d", a[i]);
ここでa[i]を表示させるようにしてますが。a[i]の計算はこれより後に計算してるのに何故先に表示するのを持ってきて実行できるのでしょうか?

MH暗号のWikiはみながら確認しています。

Re: 格納

投稿記事 by みけCAT » 2015年12月12日(土) 21:55

Offtopic :
かずま さんが書きました:* はポインタです。

確かにそうですね。
N1256 6.7.5 Declarators さんが書きました:declarator:
pointeropt direct-declarator

direct-declarator:
identifier
(略)

pointer:
* type-qualifier-listopt
* type-qualifier-listopt pointer
(http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)

Re: 格納

投稿記事 by かずま » 2015年12月12日(土) 21:08

ライトニング さんが書きました: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)とかはだめなのでしょうか?

現在の表示は次の通り。
コード[Text]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
  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 の前の空白がないと、表示は次のようになります。ただそれだけのことです。
コード[Text]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
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() に戻します。次のプログラムなら理解できますか?
コード[C]: 全て選択
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#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ナップサック暗号」は見ていますか?

Re: 格納

投稿記事 by みけCAT » 2015年12月12日(土) 20:58

ライトニング さんが書きました:(long long)*rのlong longを以前に説明してもらいましたが
これにrをかけてるのは何故でしょうか?

long longにrを掛けるなどという意味の分からない処理はありません。
これはポインタrが指す先のデータ(int型)を読み取り、その値をlong long型に変換しているだけですね。

ライトニング さんが書きました:またなぜlong longなのでしょうか?

int型の値同士を掛け算するとオーバーフローしてundefined behaviorになってしまうリスクがありますが、
もしもlong long型のサイズがint型の2倍であれば、int型の範囲の値をlong longにして掛け算をすることでオーバーフローを回避できるからでしょう。

ライトニング さんが書きました:( " w",w)とか (" sum = %d\n", sum)のwやsumの手前の空白部分などが
よくわからないのですがこれは何を表示させてるのでしょうか?

文字列リテラル中の空白部分は、標準出力の内容を表示するアプリケーションに空白を表示させているのでしょう。
ソースコード中の文字列リテラル以外の空白部分は、ソースコードを編集するテキストエディタに空白を表示されているのでしょう。

ライトニング さんが書きました:("%d",w)とかはだめなのでしょうか?

No: 64のコードの559行目のprint_array(" w", w);をprint_array("%d",w);にすることは、出力の意味がわかりにくくなるだけで問題はないでしょう。

ライトニング さんが書きました:int*q int*rなどの*はintにqをかけるという意味でしょうか?

いいえ。
ライトニング さんが書きました:それとも只*qというのを宣言してるだけでしょうか?

いいえ。int*型(int型のデータを指すポインタ)の引数qやrを宣言しています。
Offtopic :
C言語の文法的には「int*」と「q」ではなく「int」(declaration-specifiers)と「*q」(declarator)なんですけどね…

Re: 格納

投稿記事 by ライトニング » 2015年12月12日(土) 20:11

wやbの単体の意味は分かるのですが中で何が行われてるのかがよく分からないのがほとんどの状態です....
(long long)*rのlong longを以前に説明してもらいましたが
これにrをかけてるのは何故でしょうか?またなぜlong longなのでしょうか?

print_arrayがいまいちどういうものかピンとこないのですが( " w",w)とか (" sum = %d\n", sum)のwやsumの手前の空白部分などが
よくわからないのですがこれは何を表示させてるのでしょうか?("%d",w)とかはだめなのでしょうか?

int*q int*rなどの*はintにqをかけるという意味でしょうか?それとも只*qというのを宣言してるだけでしょうか? 

Re: 格納

投稿記事 by かずま » 2015年12月12日(土) 09:09

ライトニング さんが書きました:
コード[C++]: 全て選択
1
2
3
4
5
 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;

まずこれがどうしても何故これb を法とする整数の合同における a の逆元が求まるのかが全く分からないです。

「拡張ユークリッド 互除法 逆元」でググってください。

Re: 格納

投稿記事 by かずま » 2015年12月12日(土) 06:41

ライトニング さんが書きました:この部分のどこを変換したらbit数をかえれるのでしょうか?

#define N 10 のところだけです。
ただし、28 か 29までです。30はダメです。

Re: 格納

投稿記事 by かずま » 2015年12月12日(土) 06:05

ライトニング さんが書きました:この部分は何をやってるかが全くわからない状態です。 char buf[256]は256bit分箱があると考えればいいですか?

関数の頭書きと、最後の return 文を省略しないでください。
コード[C]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
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 を返す
}

char buf[256]; は、行入力のためのバッファです。#define N 10 ですから、
10個の '0' と '1'、改行コードの '\n'、文字列の終わりの '\0' を入れるため
に最低 12個の char の領域が必要です。
N はもう少し大きくできますし、ユーザが間違って余計な文字を入れてしまうかも
しれないので、かなり大きめに 256個にしました。

次の printf は、Enter 10 binary digits と表示します。
その次の printfは、"123456789.123456789.123456789.12"という文字列の_うち
先頭の N 個、すなわち 10個を表示します。

fgets は、行入力関数です。標準入力 stdin(今はキーボード)から 1行分の
文字列を buf に読み込みます。
ユーザが Linux で Ctrl-D、Windows で Ctrl-Z を入力すると、それは入力終了の
意味になるので、fgets は読込みに失敗し、NULL を返します。
fgets() の前の単項演算子 ! はそれを検出して、演算結果を 1 にします。
if (1) になるので、return 0; が実行され、input_data()関数は呼び出し元に
0 を返します。これは、データが読み込めなかったという合図です。
通常は、ユーザが 0011010111 Enter などと入力するので、fgets() は成功し、
NULL 以外の値を返すので、! による演算結果が 0 になり、if (0) ですから
return 文は実行されません。buf には入力文字列が入っています。

その buf の先頭から N個の文字を、for文で順番に見ていき、
'1' だったら数値の 1 を、
'0' だったら数値の 0 を a[i] に代入します。
'1' と '0' 以外の文字があったら、break; で forループを中断します。

最後の return文の意味はコメント通りです。
これで、main() の int a[N]; にデータの入力完了です。

さて、main() の while (input_data(a)) { ですが、正しく入力できた場合、
input_data() が 1 を返すので、while (1) { となり、{ から } までの文が実行され、
その後、input_data(a) の呼び出しに戻ってきます。
入力の終了や入力エラーの場合、input_data(a) は 0 を返すので、
while (0) { となり、{ から } までの文は実行されずにその次の return 0; に進みます。
main() 終了します。

Re: 格納

投稿記事 by かずま » 2015年12月11日(金) 22:21

ライトニング さんが書きました:
コード[C++]: 全て選択
1
2
3
4
5
6
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");

またvoid print_array a[i]とa[N]の違い nameは何を表してるのか二行目と四行目のprintfは何を表示させてるのかが分からないです。

No.86のプログラムを実行すると、次のような表示が出ます。
コード[Text]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
  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.

最初の行は、generate_array() の中の print_array(" w", w); という
関数呼び出しにより表示されています。
name が、" w" を表していることに何の疑問があるのでしょうか?
関数 print_array() の中の
一つ目の printf で、" w = [" を表示し、
二つ目の printf で、" 5 13 28 48 96 196 390 779 1557 3117" を表示し、
三つ目の printf で、"]\n" を表示しています。

a[i] と a[N] の違いですか?
a[i] は、配列 a の i番目の要素を参照しています。
a[N] は、引数の宣言で、a が配列であることを示しています。
実は、この引数の const int a[N] は、
const int a[] と書いてもよく、
const int *a と書いてもよいのです。
ここでの配列の実体は、main() の int w[N] で、それが generate_keys()
を経由して、print_array() から a[i] で参照できるようになっています。

Re: 格納

投稿記事 by かずま » 2015年12月11日(金) 21:40


for文ですが、これは右側にあるコメントのように秘密鍵 r の生成です。
Wikipedia には、「整数 r を gcd(r,q) = 1 となるようにランダムに選ぶ」とあります。
ランダムといっても 0 と 1 はダメです。
0 だと、公開鍵が全部 0 になってしまいます。
1 だと、公開鍵が秘密鍵と同じになってしまいます。
2, 3, 4, ... といった小さい数だと r * w[i] が q を超えず、
b[0], b[1], b[2], ... が超増加列なって、秘密鍵がばれやすくなりますから、
ある程度の大きさが必要です。
r が大きすぎると、r * w[N-1] などがオーバーフローする恐れがあります。
そこで、私は、r を q/2 と q の間と考え、q/2 にしました。
r は q と互いに素でなければなりませんから、gdc(r, q) == 1 になるまで、
r を 1ずつ増やしていって、適切な値を求めています。

Re: 格納

投稿記事 by かずま » 2015年12月11日(金) 12:54

ライトニング さんが書きました:
コード[C++]: 全て選択
1
2
3
print_array("  w", w);
for (*r = *q /2; gcd(*r, *q) != 1; ++*r) ;
 b[i] = (long long)*r * w[i] % *q;

この三つがwを何を表してるのか、 for文がどのようになってるのか b[i]には何の計算が行われてb[i]に何が入ったのかが分からないです。

Wikipedia とプログラムに書いてありますが、それでも w や b が何か分かりませんか?
b は beta、すなわち β です。
コード[C]: 全て選択
1
2
3
4
5
6
7
8
9
10
int main(void)
{
    int w[N], q, r;  // 秘密鍵
    int b[N];        // 公開鍵
    int a[N];  // 暗号化する前のデータ
    int c;     // 暗号化されたデータ
    int s[N];  // 復号されたデータ
 
    srand(time(0));
    generate_keys(b, w, &q, &r); // 鍵の生成

コード[C]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
void generate_keys(int b[N], int w[N], int *q, int *r)  // 鍵の生成
{
    int i, sum = 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] = (long long)*r * w[i] % *q;
}

q や r の実体は、main() の中にあり、
generate_keys() からそれらを参照するために *q や *r となっています。

つづく

Re: 格納

投稿記事 by ライトニング » 2015年12月10日(木) 13:34

コード[C++]: 全て選択
1
2
3
4
5
 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;

まずこれがどうしても何故これb を法とする整数の合同における a の逆元が求まるのかが全く分からないです。
コード[C++]: 全て選択
1
2
3
4
5
6
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");

またvoid print_array a[i]とa[N]の違い nameは何を表してるのか二行目と四行目のprintfは何を表示させてるのかが分からないです。
コード[C++]: 全て選択
1
2
3
4
5
6
7
8
9
 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;

この部分は何をやってるかが全くわからない状態です。 char buf[256]は256bit分箱があると考えればいいですか?

コード[C++]: 全て選択
1
2
3
print_array("  w", w);
for (*r = *q /2; gcd(*r, *q) != 1; ++*r) ;
 b[i] = (long long)*r * w[i] % *q;

この三つがwを何を表してるのか、 for文がどのようになってるのか b[i]には何の計算が行われてb[i]に何が入ったのかが分からないです。

後最後のほうの while (input_data(a))
input_data(a)になるまで続ける?と言うのがよく分からないです。
この部分のどこを変換したらbit数をかえれるのでしょうか?
ご回答よろしくお願いします。

またNTLをしったのはちゃんと暗号を使える?大きいbit数でもできるように新たなNTLでも動くようにと課題が与えられました。
これのNTLを使って実装の後にもまた別の最後の課題が与えられまずはこっちを理解しなければならない状態です。

Re: 格納

投稿記事 by かずま » 2015年12月10日(木) 06:21

ライトニング さんが書きました:No.86のプログラムを理解できていない状態なのでそちらを聞いてもいいでしょうか?

はい、聞かれたことはなんでも答えるつもりです。

ライトニング さんが書きました:どれも自分の説明不足で結果的にナップサック暗号のリンクを持ち出してしまってる形になっているのはすいません。

そうです。最初にリンクを示し、自分がどんな問題で困っているのかを説明するべきでした。

ライトニング さんが書きました:確かにまたNTLのトピックも同じように自分の説明不足でNTLが何のかなども分からない事だらけだと思います。

NTL は、どこで知ったのですか?
前の課題は、「C言語で MH暗号を作れ」だったと思いますが、
今度の課題は、「C++ で、NTL を使って MH暗号を作れ」になったんですか?

ライトニング さんが書きました:格納のリンクを貼るべきでした

「NTLの使い方」にそのトピックができたいきさつを説明し、リンクを貼ってください。

ライトニング さんが書きました:C++の入門を少し拝見しcoutがC++の関数ということも分かりました。

cout は、オブジェクトです。ostreamクラスのインスタンスです。
と言っても、わからないでしょう。cout は、変数だと思ってください。

cout << "abc" は、operator<<(cout, "abc") のことで、operator<< が関数です。
これは C の fputs("abc", stdout) に相当します。

Re: 格納

投稿記事 by みけCAT » 2015年12月09日(水) 21:34

ライトニング さんが書きました:C++の入門を少し拝見しcoutがC++の関数ということも分かりました。

どこでそんなことを知ったのですか?coutは関数ではありません。
c++ - cout and cin are not functions, so what are they? - Stack Overflow

Re: 格納

投稿記事 by ライトニング » 2015年12月09日(水) 14:32

EasyIDEC のバージョンは一緒でした。

No.86のプログラムを理解できていない状態なのでそちらを聞いてもいいでしょうか?

トピックのタイトルは完全に忘れていました。申し訳ないです。

どれも自分の説明不足で結果的にナップサック暗号のリンクを持ち出してしまってる形になっているのはすいません。

確かにまたNTLのトピックも同じように自分の説明不足でNTLが何のかなども分からない事だらけだと思います。
格納のリンクを貼るべきでした

C++の入門を少し拝見しcoutがC++の関数ということも分かりました。

Re: 格納

投稿記事 by かずま » 2015年12月09日(水) 06:15

ライトニング さんが書きました:自分ももう一度改めて実行してみたところかずまさんと同じようなエラーをはかれてしまいました
自分でも何故以前実行できたのか分からない状態です....

No.94 の「EasyIDEC のバージョンが違うのでしょうか?」という質問に
答えてもらっていません。

ライトニング さんが書きました:またNo.89のプログラムで質問したいことがあるのですがここで質問していいでしょうか?

No.94 の「No.64 の改良版の No.86 なら中身を理解できますか?」に
答えてもらっていません。
No.89 のプログラムは、No.86 を元に NTL を使うようにしたものなので、
そちらの理解が先です。

ライトニング さんが書きました:一応NTLトピックをたてたのですが...

No.89 で、「さらに、NTL に関する質問をするなら、
「NTL を使用する Merkle-Hellmanナップサック暗号」という件名の
新しいトピックを立ててください。」とお願いしたのに、そうなっていません。

何度同じ間違いをしたら気が済むのですか?

10/04~10/07 「mod計算?」
10/08~10/14 「数列の作成」
10/23~現在 「格納」
10/29~10/31 「mody逆元計算」

どれも、不明確な質問をし、回答者が疑問を持ってから、Wikipedia の
「Merkle-Hellmanナップサック暗号」へのリンクを持ち出しています。

12/06 「NTLの使い方」
ライトニング さんが書きました:これをNTLでうまく実装させたいのですがどの部分を直せばいいでしょうか?
うか?NTLのオリジナル?の関数なのでしょうか?

これを見た人はどう思いますか?
・このプログラムは何だろうか?
・NTL って何だろうか?
・なぜ直さないといけないんだろうか?
と疑問がいっぱいです。
ちゃんとこれまでの経緯を説明し、少なくとも「格納」へのリンクを張るべきです。

ライトニング さんが書きました:またCとC++の違いがよくわからないのですがcoutと言うのはC++関数なのでしょうか?NTLのオリジナル?の関数なのでしょうか?

C++ を全く学習していないことが分かります。
せめて 30分だけでも C++ の入門ページを見てください。

Re: 格納

投稿記事 by ライトニング » 2015年12月08日(火) 22:37

自分ももう一度改めて実行してみたところかずまさんと同じようなエラーをはかれてしまいました
自分でも何故以前実行できたのか分からない状態です....

またNo.89のプログラムで質問したいことがあるのですがここで質問していいでしょうか?一応NTLトピックをたてたのですが...

Re: 格納

投稿記事 by かずま » 2015年12月07日(月) 10:14

かずま さんが書きました:私のところで、EasyIDEC Ver 0.0.9.0 を起動し、No.90 のプログラムをコピペして、
「プログラム実行」を押すと、次のようにエラーになりました。

次のように訂正します。

私のところで、EasyIDEC Ver 0.0.9.0 を起動し、No.90 のプログラムをコピペして、
「関数の宣言」を削除して、「プログラム実行」を押すと、次のようにエラーになりました。

Re: 格納

投稿記事 by かずま » 2015年12月07日(月) 02:38

ライトニング さんが書きました:自宅ではEasyIDECと言うのを使用しておりそれで先頭の「関数の宣言」を消しては実行できました。

私のところで、EasyIDEC Ver 0.0.9.0 を起動し、No.90 のプログラムをコピペして、
「プログラム実行」を押すと、次のようにエラーになりました。
コード[Text]: 全て選択
1
2
3
ファイル「C:/EasyIDEC/project/default/main.c」の
「89行目」で記述エラーを発見しました。
「print_suretu」が再定義されています。以前と同じ名前を使っていないか、関数の記述順番は正しいかどうかを確認してください。

gcc では警告だけで実行はできたのに、EasyIDEC ではエラーで実行できません。
EasyIDEC のバージョンが違うのでしょうか?

ライトニング さんが書きました:No64の実行をしてみたのですがその後どのような値を入力するのか分からないのが謎でした。
けれど10bitを何かうつというのをようやく理解でき実行部分までは理解することができました。

No.64 の改良版の No.86 なら中身を理解できますか?
分からないところは質問してください。
No.89 は、これの NTL版です。

ライトニング さんが書きました:実行したのはこのプログラミングです

以前に質問した29行目のprintf("",sum)だとエラーをはかれてしまったのでprintf("%d\n",sum)を治したらこのようになってしまい
コード[Text]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
6
17
42
92
193
394
791
1589
3185
6379
数列の合計 = 6379
xの値は? 7000
yの値は? 699
秘密鍵 6,11,25,50,101,397,798,1596,3194
合計=6379 x = 7000 y=6999
公開鍵 6994,6989,6975,6950,6899 6799 6603 6202 5450 3806
暗号 17580 暗号:17580
復号:[9][5][2]

のように少し変になってしました。

何も変ではありません。
6 17 42 92 というのは sum の値です。
6 11 25 50 というのは、kakunou[i] の値です。

17 = 6 + 11
42 = 6 + 11 + 25
92 = 6 + 11 + 25 + 50
となるのは当然です。プログラムをそうなるように書いているのですから。

Re: 格納

投稿記事 by ライトニング » 2015年12月06日(日) 22:49

すいません何て言えばいいのか分からないのですが
Emacsで作ったプログラムをターミナルを使ってgccでコンパイルしましたと言えばいいのでしょうか?説明が下手で申し訳ないです。
すいません実行したプログラムです。

Re: 格納

投稿記事 by ライトニング » 2015年12月06日(日) 22:46

すいません誤字・脱字がありました。
かずまさんの言われた通り警告が出てしました。
EasyIDEXでは実行できたので勝手にEmacs作ったもの保存したものをgccでもコンパイルできると思い込んでいました。
そのため先頭の関数宣言は消さずにそのままにしておきました。
10bitの何かではなく10個の2進数字を入力をするというのが分かったので実行方法までは分かりました。

Re: 格納

投稿記事 by みけCAT » 2015年12月06日(日) 22:44

Offtopic :
ライトニング さんが書きました:学校ので使ってるのEmacsをターミナルでコンパイルするとかずまんの言われたとおり警告が出てしまいました。

Emacsをコンパイルした…?どうして…?

ライトニング さんが書きました:実行したのはこのプログラミングです

これはプログラミングではありません。プログラムです。

ページトップ