今回は正の整数が入った配列の隣接要素を足してその総和を計算します。
少し複雑になりますが、総和を計算する間に１ビット左シフト演算をします。
更に、この配列に繰り返し同じ置換をかけることで、どのように総和の値が変わるのかを説明するつもりですが、よく分からないかも知れません。
ここでは恒等置換を除き、小さな素数位数のサイクルをなるべく多く含んだ置換を$\pi$とする。
何故こうするかといえば、限られた次元の中で最大の巡回位数を置換群が持つようにしたいからである。
まず、配列aの隣り合った要素に対する演算を
$e(a[i],a[i+1])=a[i]+a[i+1]$
とする。
ここではこのように$i$は配列の要素数$N$より$1$つ小さな数まで増えるものとする。
置換をかけているので、最後と最初の項が何になるのかが判ればよい。
つまり配列の要素の大きさが、解読できるかどうかの基礎的な問題の一つになっている。
次に例を示します。
配列aを次のように決めます。
$a=(7,9,1,10,9)$
この例で言えば配列aのサイズ$N=5$です。
更に置換は
$\pi=(4,5,2,1,3)$
とします。
故に、$\pi$を配列にかけた結果の配列は、
$\pi a=(10,9,9,7,1)$
である。
ここで、$\pi^j$は$\pi$を$j$回かけたもの、$N$を配列の長さ、$i$を配列の添え字を意味する。
$j$は配列の要素数によって変化しますが、ここでは２０までと決めます。
そして配列の隣接する要素の和は
$A_{0 \leq j \leq 20}=\Sigma_{i=1}^{N-1}e(a[\pi^j(i)],a[\pi^j(i+1)])$
と書ける。
ある置換を同一の配列に繰り返しかけ、その度に配列の和を計算してみると、この例の場合は、$j=0$なので、
$A_0= \Sigma_{i=1}^{4} e(a[i],a[i+1])=(7+9)+(9+1)+(1+10)+(10+9)=56 $
そして、$j={0,1,2,3,4,...}$の場合、
$A_j=(A_0,A_1,A_2,A_3,A_4,...)=(56,61,56,53,64,...)$
であることが解る。（実はこの何の工夫もない計算だと、異なる置換の間で衝突が発生してしまうので、少し変えなければならない）
さてここで定義しておきたいのは$A_j$である。
その定義を以下のようにする。
定義
$A_j$の全体を簡単に$A$と書く。この時$A$のことを配列$a$の置換$\pi$による系列、以下では簡単に系列と呼ぶことにする。
従って、求めたい値$A_j$は以下のように計算できる。
$A=2\Sigma a-a[0]-a[N-1]$
のように$i=0,..,N-1$に渡って足していく計算になる。
そこでやりたいのは、置換$\pi$と系列$A_i$を公開し、配列の値そのものは公開しないときに$\pi$と$A_i$を使って認証プロトコルを作ろうという話である。
20220416 続き
さて今度はこれからやりたいことを説明する。
やりたいこと
ランダムな要素を持つ配列を１つ固定したとき、置換群とその系列を１対１に対応させたい。
配列の各値が全部同じであるような自明な場合を除いて、十分ランダムであれば（0,1,2,3,4,5,6,7,8,...であってもよい）配列と置換による系列は１対１に対応するであろうという問題である。
もしこれが成り立つなら、認証に使えそうだというのが今までの実験的な予測である。
ちょっと調べてみたところ、置換を作用させる２つの配列の関係は置換グラフと呼ばれるものに近いことが解った。
これによるとグラフが与えられたとき、そのグラフが置換グラフであることを判定したり、また置換グラフであればその置換を出力する簡単な計算法があると言うことが解っているらしい。
なのでこの認証にはグラフの構造はを秘密にしておかなければならない。
配列を置換グラフとしてみたとき、配列の要素が置換グラフの頂点に対応している。
認証法を述べる。
基礎となる問題
配列aがあり秘密のされている。この時、公開置換$\pi$と系列$A$が公開されているときに、置換と系列だけから配列の要素を復元するのは不可能である。
また、１つの系列について、２つ以上の異なる置換と配列の対を見つけるのは困難でなければならない。
さてこれをどのように使えばいいだろうか？
鍵セットアップ
送信者は公開鍵を計算するのに、まず長さNのランダムな配列aと、置換πを決める。
更に認証子として系列Aを計算し、$(A,\pi)$が送信者の公開鍵であり、配列aが秘密鍵である。
プロトコルの基本ロジック
１．送信者は配列aと異なる乱数列rを生成して検証者にrの系列$A_r$を送る。
２．検証者はランダムにビットを選び送信者に送る。検証者が送ったビットをeとする。
３．送信者のチャレンジ
e=0の時、送信者はランダム配列rを検証者に送る。
e=1の時、送信者は$r+a$を送る。
４．検証
e=0の時、
検証者はｒから系列を生成して、最初に送られてきた系列と一致することを確認する。
e=1の時
検証者は送られてきたランダム配列$a+r$から系列$A_{r+a}$を計算し、公開系列Aとの足し算$A+A_r$と比較して一致することを確認する。
そうでなければこの認証は破棄される。
ここで系列を生成するのに使う演算は排他的論理和$\oplus$でないことに注意。
何故普通の足し算なのかは、系列が消し合って途中で配列の内容に関する情報が消えてしまわないようにである。
ここで、どのように衝突のない系列を計算するのかを説明する。
もう一つまだよく分かっていない部分であるが、もう一つ重要なのは、何故送信者と検証者の系列は常に一致するのかについて説明品なければならない。
系列の計算方法を具体的に書くと、N=5の場合、
s+=8(a[0]+a[1])
s+=4(a[1]+a[2])
s+=2(a[2]+a[3])
s+=1(a[3]+a[4])
となる。
シフト演算は小さなサイズの変数ではすぐあふれてしまうが、６４ビット整数ならループの上限である６４を上回らないので６４bit分の乱数の情報は確保できるはずである。
もし配列の順番を入れ替えるだけだと系列のとる値は同じ値ばかりになり衝突がが出てくる場合がある。
それをなくすために配列の隣接要素を足すときに、総和が格納されている変数に左シフト処理をしている。
シフト処理以外は全て足し算だけで実行しているのだから２つの配列を足してから計算する系列とすでにある系列を足し算したものが一致するのは当たり前のような気もするが、何故そうなるのかうまく説明できない。
足し算の場合には、この演算結果も期待した系列の値になる。
なので一連の計算の意味を数学的に捉えなければならないのだか、まだよく分からない。
置換群の位数をある程度に保つのは繰り返しによって同じ値が出てこないためという意味もあるのだが、シフトさせないと系列の衝突が起きる原因は調べなければならない。
以下にCのコードを載せる。
int j;
//系列の要素数
for(j=0;j<10;j++){
//s1は総和を格納する変数
s1=0;
s2=0;
s3=0;
t1=0;
t2=0;
t3=0;
memset(c1,0,sizeof(c1));
memset(c2,0,sizeof(c2));
memset(c3,0,sizeof(c3));
//隣接する配列の要素の輪を計算する
for(i=0;i<N-1;i++){
c1[i]=(a[i])+a[(i+1)];
c2[i]=(b[i])+b[(i+1)];
c3[i]=(d[i])+d[(i+1)];
f1[i]=m1[i]+m1[i+1];
f2[i]=m2[i]+m2[i+1];
f3[i]=m3[i]+m3[i+1];
}
//謎のシフト処理
for(i=0;i<N-1;i++){
s1=(s1<<1);
s2=(s2<<1);
s3=(s3<<1);
t1=(t1<<1);
t2=(t2<<1);
t3=(t3<<1);
//総和の計算
s1+=c1[i]; //^c2[i];
s2+=c2[i];
s3+=c3[i];
t1+=f1[i]; //^c2[i];
t2+=f2[i];
t3+=f3[i];
}
printf("%llu,",s1%256);
printf("%llu,%llu %llu,%llu\n",c*(s1+s2)%256,c*s3%256,(t1+t2)%256,t3%256);
//置換によって配列の値を入れ替える
for(i=0;i<N;i++){
s[i]=a[u[i]];
t[i]=b[u[i]];
e[i]=d[u[i]];
g1[i]=m1[u[i]];
g2[i]=m2[u[i]];
g3[i]=m3[u[i]];
}
memcpy(a,s,sizeof(a));
memcpy(b,t,sizeof(b));
memcpy(d,e,sizeof(d));
memcpy(m1,g1,sizeof(m1));
memcpy(m2,g2,sizeof(m2));
memcpy(m3,g3,sizeof(m3));
}
次回に続く。