Q&A
「どこで(最初に)(何行目で)」
「何を入れて」
「どこで(２回目に)(何行目で)」
「何に変わっていたか？」
を明確にしてください。
ある秘密分散法のプログラムを作成していたところ，元の方で定義していた"p","q","N"(他にもあるかもしれません)の値をのちにもう一度使おうとしたら，おかしな値になってしまいました．理由がわかる方がいたらご教授いただきたいです．
なお，以前同じ内容で質問してベストアンサーを決めて解決済みになってしまったため，もう一度質問し直しました．また，以前ご指摘のあった，領域の問題は解決したと思います．
40,41行目でp,q,Nを宣言して，151行目以降の検証フェーズにて，値がおかしくなっています．
コードの下に実行結果を載せました．
検証フェーズの直前で，p,q,Nの値を確認したところ正しい値が出力されました．
C
1//逐次秘密分散法の実装 2#include <stdbool.h> 3#include<stdio.h> 4#include<math.h> 5 6int main(void){ 7 //繰り返し変数 8 int i,j,k; 9 10 //初期化フェーズ 11 12 //ディーラー 13 //レベル，閾値，プレイヤー数の決定 14 int m=3; 15 int t[m],n[m]; 16 t[0]=2,n[0]=2; 17 t[1]=2,n[1]=3; 18 t[2]=3,n[2]=4; 19 printf("m=%d\n",m); 20 for(i=0;i<m;i++){ 21 printf("t[%d]=%d, n[%d]=%d\n",i,t[i],i,n[i]); 22 } 23 //素数P≡3mod4においてFPから各レベルのシークレットを選択する 24 int P=23; 25 int s[m]; 26 s[0]=3,s[1]=5,s[2]=5; 27 printf("P=%d\n",P); 28 for(i=0;i<m;i++){ 29 printf("s[%d]=%d, ",i,s[i]); 30 } 31 printf("\n"); 32 //2つの安全な素数p,qを選択し，Nを公開する．ただしN<P 33 34 35 36 37 38//ここでp,q,Nを定義した 39 40 int p=7,q=3; 41 int N=p*q; 42 printf("p=%d, q=%d, N=%d\n",p,q,N); 43 //gをp,qに対して互いに素になるように[N^1/2,N]より整数を選択する 44 int g=5; 45 printf("g=%d\n",g); 46 // プレイヤー 47 //シークレットシャドウsijを[2,N]からランダムに選択し，Rijを計算する(sijをs1とする) 48 int s1[P][P],R[P][P]; 49 50 for(i=0;i<m;i++){ 51 for(j=0;j<n[i];j++){ 52 s1[i][j]=j+1; 53 printf("s[%d][%d]=%d, ",i,j,s1[i][j]); 54 } 55 printf("\n"); 56 } 57 for(i=0;i<m;i++){ 58 for(j=0;j<n[i];j++){ 59 R[i][j]=pow1(g,s1[i][j],N); 60 printf("R[%d][%d]=%d, ",i,j,R[i][j]); 61 } 62 printf("\n"); 63 } 64 65 //Rijが全てのレベルで一意であるか確認，一意でない場合sijを再選択 66 int count[m]; 67 printf("レベル"); 68 for(i=0;i<m;i++)count[i]=0; 69 for(i=0;i<m;i++){ 70 for(j=0;j<n[i]-1;j++){ 71 for(k=j+1;k<n[i];k++){ 72 if(R[i][j]==R[i][k])count[i]++; 73 } 74 } 75 if(count[i]==0)printf("%d,",i+1); 76 } 77 printf("で一意である．\n"); 78 79 //配布フェーズ 80 //ディーラー 81 //p-1,q-1に対して互いに素である素数s0を選択する 82 int s0=5; 83 printf("s0=%d\n",s0); 84 //s0*f=1modΦ(N)となるfを探す 85 for(i=1;i<P;i++){ 86 87 } 88 int f=17; 89 printf("Φ(N)=%d, f=%d\n",phi(N),f); 90 //R0を計算 91 int R0=pow1(g,s0,N); 92 printf("R0=%d\n",R0); 93 94 95 int I[P][P]; 96 int S[m],K[m],ss[m]; 97 for(i=0;i<m;i++){ 98 for(j=0;j<n[i];j++){ 99 //Iijを計算する 100 I[i][j]=pow1(R[i][j],s0,N); 101 printf("I[%d][%d]=%d, ",i,j,I[i][j]); 102 } 103 printf("\n"); 104 if(i==0){ 105 S[i]=s[i]; 106 107 } 108 else{ 109 K[i]=fmod(s[i]*ss[i-1],P); 110 printf("K[%d]=%d\n",i,K[i]); 111 //Kiが平方剰余か判断する 112 if(jacobi(K[i],P)==1){ 113 printf("K[%d]は平方剰余である\n",i); 114 S[i]=sqrt(K[i]); 115 printf("S[%d]=%d\n",i,S[i]); 116 } 117 else { 118 printf("K[%d]は平方剰余でない\n",i); 119 //Ki*RiがFPを方とする平方剰余となるようにFPから乱数Riを選択する(iをPまでにしているが，あっているか不明) 120 int R1[P];//R1はRi 121 for(k=2;k<P;k++){ 122 if(jacobi(K[i]*k,P)==1){ 123 R1[i]=k; 124 break; 125 } 126 } 127 printf("R[%d]=%d\n",i,R1[i]); 128 int r[m][P]; 129 for(j=0;j<n[i];j++){ 130 r[i][j]=fmod(h(I[i][j],R1[i],t[i],P),P); 131 printf("r[%d][%d]=%d, ",i,j,r[i][j]); 132 } 133 printf("\n"); 134 S[i]=sqrt(fmod(K[i]*R1[i],P)); 135 } 136 } 137 138 //t1-1次関数hi(x)を作成 139 //yijを計算する 140 int y[m][P]; 141 for(j=0;j<n[i];j++){ 142 y[i][j]=fmod(h(I[i][j],S[i],t[i],P),P); 143 printf("y[%d][%d]=%d, ",i,j,y[i][j]); 144 } 145 printf("\n"); 146 ss[i]=pow1(g,S[i],P);//ss=s' 147 if(i==m-1) printf("S[%d]=%d\n",i,S[i]); 148 else printf("S[%d]=%d, s'[%d]=%d\n",i,S[i],i,ss[i]); 149 } 150 151 //検証フェーズ 152 //プレイヤー 153 double I1[m][P];//I1=I' 154 int countv=0;//誤ったシェアのカウント 155 for(i=0;i<m;i++){ 156 for(j=0;j<n[i];j++){ 157 //I'ijを計算する 158 159//N,p,qの値がおかしい 160 161 printf("R0=%d, s[%d][%d]=%d, N=%d, p=%d, q=%d\n",R0,s1[i][j],N,p,q); 162 I1[i][j]=pow1(R0,s1[i][j],N); 163 printf("I'[%d][%d]=%d,f=%d,N=%d\n",i,j,I1[i][j],f,N); 164 //Rij==I'ij^f mod Nを検証する 165 int h=pow1(I1[i][j],f,N); 166 printf("I'[%d][%d]^f mod N=%d\n",i,j,h); 167 printf(" R[%d][%d]=%d\n",i,j,R[i][j]); 168 if(R[i][j]!=h){ 169 printf("レベル%dの%d番目のプレイヤーは，誤ったシェアを提出しました\n",i,j); 170 countv++;//誤ったシェアがあればプラス1 171 } 172 } 173 } 174 if(countv==0)printf("全て正しいシェアでした\n"); 175 /* 176 //復元フェーズ 177 //プレイヤー 178 double S1[m],r[m]; //求めるSi 179 double y1[m][P]; 180 for(i=1;i<=m;i++){ 181 S1[i]=0; 182 for(j=1;j<=t[i];j++){ 183 //ラグランジュ補間を使用して，Siを求める 184 y1[i][j]=fmod(h(I[i][j],S[i],t[i],P),P); 185 printf("y[%d][%d]=%lf, ",i,j,y1[i][j]); 186 r[i]=y1[i][j]; 187 for(k=1;k<=t[i];k++){ 188 if(j!=k){ 189 r[i]*=(0-I1[i][k])/(I1[i][j]-I1[i][k]); 190 191 } 192 } 193 194 S1[i]+=r[i]; 195 printf("S[%d]=%lf ",i,S1[i]); 196 S1[i]=fmod(S1[i],P); 197 198 } 199 S1[i]=round(S1[i]); 200 printf("S[%d]=%lf\n",i,S1[i]); 201 } 202 203*/ 204 return 0; 205} 206 207 208 209 210 211 212//累乗計算 213int pow1(a,b,N){ 214 int p=1,i; 215 for(i=0;i<b;i++)p=fmod(p*a,N); 216 return p; 217} 218 219//最大公約数を求める関数 220int gcd(a,b) 221{ 222 int temp; 223 while ( b > 0 ) { 224 temp = a % b, a = b; b = temp; 225 } 226 return a; 227} 228 229 230//ファイ関数 231int phi(n){ 232 int i, res=1; 233 for(i=2;i<n;i++){ 234 if(gcd(i,n)==1)res++; 235 } 236 return res; 237} 238 239//ti-1次関数を作成する関数(数値) 240int h(x,S,t,P){ 241 int ans=S; 242 int j,k; 243 int a[P],p[P]; 244 a[1]=1,a[2]=2,a[3]=3; 245 for(j=1;j<t;j++){ 246 p[j]=a[j]*pow(x,j); 247 ans +=p[j]; 248 } 249 return ans; 250} 251 252//平方剰余か判断 253int jacobi(a,p){ 254 255 int x = 1; 256 int tmp; 257 if (p <= 0) return 0; 258 if (p > 2 && (p & 1) == 0) return 0; 259 a %= p; 260 if (a < 0) a += p; 261 262 while (a > 1) { 263 if (a & 1) { 264 if ((a & 3) == 3 && (p & 3) == 3) x = -x; 265 tmp = p; 266 p = a; 267 a = tmp; 268 a = a % p; 269 } else { 270 a >>= 1; 271 if ((p & 7) == 3 || (p & 7) == 5) x = -x; 272 } 273 } 274 if (a == 0) return 1; 275 return x; 276}
initialize.c:59:15: warning: implicit declaration of function 'pow1' is invalid in C99 [-Wimplicit-function-declaration] R[i][j]=pow1(g,s1[i][j],N); ^ initialize.c:89:29: warning: implicit declaration of function 'phi' is invalid in C99 [-Wimplicit-function-declaration] printf("Φ(N)=%d, f=%d\n",phi(N),f); ^ initialize.c:91:10: warning: implicit declaration of function 'pow1' is invalid in C99 [-Wimplicit-function-declaration] int R0=pow1(g,s0,N); ^ initialize.c:112:10: warning: implicit declaration of function 'jacobi' is invalid in C99 [-Wimplicit-function-declaration] if(jacobi(K[i],P)==1){ ^ initialize.c:130:24: warning: implicit declaration of function 'h' is invalid in C99 [-Wimplicit-function-declaration] r[i][j]=fmod(h(I[i][j],R1[i],t[i],P),P); ^ initialize.c:142:20: warning: implicit declaration of function 'h' is invalid in C99 [-Wimplicit-function-declaration] y[i][j]=fmod(h(I[i][j],S[i],t[i],P),P); ^ initialize.c:161:45: warning: more '%' conversions than data arguments [-Wformat] printf("R0=%d, s[%d][%d]=%d, N=%d, p=%d, q=%d\n",R0,s1[i][j],N,p,q); ~^ initialize.c:163:46: warning: format specifies type 'int' but the argument has type 'double' [-Wformat] printf("I'[%d][%d]=%d,f=%d,N=%d\n",i,j,I1[i][j],f,N); ~~ ^~~~~~~~ %f 8 warnings generated. m=3 t[0]=2, n[0]=2 t[1]=2, n[1]=3 t[2]=3, n[2]=4 P=23 s[0]=3, s[1]=5, s[2]=5, p=7, q=3, N=21 g=5 s[0][0]=1, s[0][1]=2, s[1][0]=1, s[1][1]=2, s[1][2]=3, s[2][0]=1, s[2][1]=2, s[2][2]=3, s[2][3]=4, R[0][0]=5, R[0][1]=4, R[1][0]=5, R[1][1]=4, R[1][2]=20, R[2][0]=5, R[2][1]=4, R[2][2]=20, R[2][3]=16, レベル1,2,3,で一意である． s0=5 Φ(N)=12, f=17 R0=17 I[0][0]=17, I[0][1]=16, y[0][0]=20, y[0][1]=19, S[0]=3, s'[0]=10 I[1][0]=17, I[1][1]=16, I[1][2]=20, K[1]=4 K[1]は平方剰余である S[1]=2 y[1][0]=19, y[1][1]=18, y[1][2]=22, S[1]=2, s'[1]=2 I[2][0]=17, I[2][1]=16, I[2][2]=20, I[2][3]=4, K[2]=10 K[2]は平方剰余でない R[2]=5 r[2][0]=2, r[2][1]=4, r[2][2]=20, r[2][3]=18, y[2][0]=22, y[2][1]=1, y[2][2]=17, y[2][3]=15, S[2]=2 R0=17, s[1][21]=7, N=3, p=23, q=0 I'[0][0]=17,f=21,N=0 I'[0][0]^f mod N=-2147483648 R[0][0]=5 レベル0の0番目のプレイヤーは，誤ったシェアを提出しました R0=17, s[2][21]=7, N=3, p=0, q=0 I'[0][1]=17,f=21,N=0 I'[0][1]^f mod N=-2147483648 R[0][1]=4 レベル0の1番目のプレイヤーは，誤ったシェアを提出しました R0=17, s[1][21]=7, N=3, p=0, q=0 I'[1][0]=17,f=21,N=0 I'[1][0]^f mod N=-2147483648 R[1][0]=5 レベル1の0番目のプレイヤーは，誤ったシェアを提出しました R0=17, s[2][21]=7, N=3, p=0, q=0 I'[1][1]=17,f=21,N=0 I'[1][1]^f mod N=-2147483648 R[1][1]=4 レベル1の1番目のプレイヤーは，誤ったシェアを提出しました R0=17, s[3][21]=7, N=3, p=0, q=0 I'[1][2]=17,f=21,N=0 I'[1][2]^f mod N=-2147483648 R[1][2]=20 レベル1の2番目のプレイヤーは，誤ったシェアを提出しました R0=17, s[1][21]=7, N=3, p=0, q=0 I'[2][0]=17,f=21,N=0 I'[2][0]^f mod N=-2147483648 R[2][0]=5 レベル2の0番目のプレイヤーは，誤ったシェアを提出しました R0=17, s[2][21]=7, N=3, p=0, q=0 I'[2][1]=17,f=21,N=0 I'[2][1]^f mod N=-2147483648 R[2][1]=4 レベル2の1番目のプレイヤーは，誤ったシェアを提出しました R0=17, s[3][21]=7, N=3, p=0, q=0 I'[2][2]=17,f=21,N=0 I'[2][2]^f mod N=-2147483648 R[2][2]=20 レベル2の2番目のプレイヤーは，誤ったシェアを提出しました R0=17, s[4][21]=7, N=3, p=0, q=0 I'[2][3]=17,f=21,N=0 I'[2][3]^f mod N=-2147483648 R[2][3]=16 レベル2の3番目のプレイヤーは，誤ったシェアを提出しました
回答4件
0
ベストアンサー
＞//N,p,qの値がおかしい
＞ printf("R0=%d, s[%d][%d]=%d, N=%d, p=%d, q=%d\n",R0,s1[i][j],N,p,q);
printf引数の指定が間違っています。
printfと引数の関連が以下になっています。
R0=%d：R0
s[%d]:s1[i][j]
[%d]:N
=%d:p
N=%d:q
p=%d:不定値 ※printfの仕様上、引数足りなくてもなんとなく動くはず
q=%d:不定値
多分下記が正しいはず？
C++
1printf("R0=%d, s1[%d][%d]=%d, N=%d, p=%d, q=%d\n",R0, i, j, s1[i][j],N,p,q);
投稿2021/01/29 08:04
総合スコア404
これもコンパイラの警告で教えてくれますけどね。コンパイルエラー見るのは大事ってことです。
おっしゃる通りだと思います。
現場でもそうですが、自身が作ったコードでwarningが増えても
毛ほども気にしない輩が多くて、モヤモヤしますよね。。。
0
そもそもコンパイルが通りませんので、コンパイルが通るようにしてください。gcc -std=c11 -Wall -Wextra -pedanticないしclang -std=c11 -Wall -Wextra -pedanticでエラー・警告が出ないように。型もろくに書かないとか質問以前の問題。
投稿2021/01/29 06:14
編集2021/01/29 06:25総合スコア5850
すみません．プログラミング初心者で，理解ができていないのですが，型というのは何を書けば良いのでしょうか？
私は，macでvisual studio codeでコンパイルはできています．
本当に警告はでていませんか？
たとえば
int phi(n){
//
}
というのは引数nの型が書かれていません。C言語がISOで標準化されるより前の時代、こういう記法もありましたが、現代では警告が出ているはずです。その他にもprintfのフォーマット指定や、関数の宣言順序など多数のエラーが手元では出てますね。
で、手元で修正してコンパイルしてみましたがstack破壊とか未定義動作とか踏まずにちゃんと動いているのでは・・・？なにが問題なの？なんならpもqも使われていない。
https://wandbox.org/permlink/q4S7o8pdBQ0UPvGB
0
＞ここでN,p,qの値がおかしくなっている．
＞ int h=pow1(I1[i][j],f,N);
＞ printf("I'[%d][%d]^f mod N=%d\n",i,j,h);
まず、N=%dで表示しているのがhになっているのがおかしい。
それともf mod N = h として表示したい？
＞ここでN,p,qの値がおかしくなっている．
p,qの使用箇所が見当たらないです。。。
投稿2021/01/29 06:19
総合スコア404
0
C言語のコードを書くなら、デバッグできる環境を整えましょう。
Eclipseや、WindowsならVisualStudioなど。
コードの任意の場所で実行を止め、変数のナカミを見ることができます。そこから１行づつ実行して、コードの流れを見れるようになります
そうすれば、アテズッポでコードを書かなくて済むようになります。
＃再掲
投稿2021/01/29 06:17
総合スコア87800
あなたの回答
tips
プレビュー
