実装して何かがおかしいと気づいた今日一日

この記事から一部コードをコピペしました。

ついに完成？

実装をお見せします。

数式通りにかけているかどうか自信がないですが、多分あっていると思います。
確認は各自におまかせします。
挙動は極めて不安定です。
同じ値が出るからと言って周期が簡単に決まるというわけではなさそうです。
本当に周期があるかどうかは確かめる方法がわかりません。
非線形というものはこういうものなのでしょうか？
そこは皆さんが今までの記事を参考に、実際に動かしてみることをおすすめします。
とにかく単純な写像ではなさそうだということだけははっきりいえます。
つまり同じ値が不規則な間隔で出現するということです。
しかしながら周期は存在するはずなので、周期検出方法に問題がありそうです。

プログラムをちょっと書き換えたら、周期らしきものを見つけました。
１２８と５８の周期が交互に出てきます。
つまり、このプログラムで言えば確認しましたが、１２８＋５８＝１８６が周期というわけです。
全部の値は出てないことになります。
周期が２５６になるかもう少しやってみます。

#define ROTL8(x, shift) ((uint8_t)((x) << (shift)) | ((x) >> (8 - (shift))))
unsigned char be(unsigned char b)
{
	return b ^ ROTL8(b, 1) ^ ROTL8(b, 2) ^ ROTL8(b, 3) ^ ROTL8(b, 4) ^ 0x63;
}

unsigned char it(unsigned char s)
{
	return ROTL8(s, 1) ^ ROTL8(s, 3) ^ ROTL8(s, 6) ^ 5;
}

unsigned char loo(unsigned char c)
{
	return be(be(c));
}

unsigned char let(unsigned char c)
{
	return it(it(c));
}

int Shift(int e)
 {
     int shifted = (e << 1) ^ (((e & 0x80) != 0) ? 0x1B : 0x00);
     return shifted;
 }

static unsigned char Dot(int a, int b)
{

    int mask = 0x1;
    int product = 0;

    while (mask != 0)
    {
        if ((b & mask) != 0)
        {
            product ^= a;
        }

        a = Shift(a);
        mask <<= 1;
    }

    return (unsigned char)product;
}

unsigned char ml(unsigned char c,int u){
    for(int i=0;i<u;i++)
        c=loo(Dot(c,c));
return c;
}

unsigned int period = 0, count = 0;
unsigned char lll(unsigned char l)
{
	unsigned char lfs = l;

	int flg = 1, m, c2 = 0;

	 while(1)
	{
		m=lfsr(lfs);
		lfs=ml(m,period+1);
		lfs^=Dot(lfs,(loo(m)^be(m)));
		++period;
		printf("%d %d\n", lfs, period);
		if (lfs == 9){
			count++;
			if(count==1)
			mm=period;
		}
		if (count == i-1 && lfs == 9)
		{	
			mm = period-mm;
			printf("m=%d\n", mm);
			i++;
			mm=period;
			if(i>100)
			 exit(1);
		}
	}

	return (unsigned char)(lfs);
}

8-bit LFSR

lfsr.c

#include <stdio.h>
#include <stdlib.h>

#define STREAM (256 * 8)

/* short program to understand linear feed shift register
 * and its use in stream ciphers.
 */

unsigned char
lfsr(unsigned char c) {

        unsigned char in_s, cs, cp, p, nbit, s[STREAM];
        int i, j, k=0;


        in_s = c;     /* this can be any 8 bit value */
        p = 0x71;        /* max length polynomial x^8+x^4+x^3+x^2+1 = 0b01110001 */

        cs = in_s;      /* copy initial state */

        //printf("\nByte values for lfsr with initial value of 0xb4, and bit mask 0x71.\n");
        //printf("Should correspond to primitive polynomial x^8+x^4+x^3+x^2+1.\n");

        while (k < STREAM) {
                for (j = 0;j < 8;j++,k++) {
                        cp = nbit = cs & p;

                        for (i = 1;i < 8; i++) { /* xor all bits together */
                                nbit ^= (cp >> i);
                        }
                        s[k] = cs & 0x01;
                        cs = (cs >> 1) | (nbit << 7); /*  rotate in new bit */
                }
                return cs;
                printf(" %02x ",cs);
                if (cs == in_s) {
                         printf("\nreached duplicate at %d.\n", k);
                }
        
        }
        
/* print the stream and put it back together */
        /*
        printf("\n** stream cipher **\n");
        unsigned char out = 0;
        k = 7;
        for (i = 0;i < STREAM;i++) {
                //printf("%d:",s[i]);
                out |= s[i]<<k;
                k--;
                if ((i+1) % 8 == 0) {
                        printf(" %02x ",out);
                        k = 7;out = 0;
                }
        }
        */
}

周期がバラバラ・・・なぜ？

次のように書き換えたら本当に周期が不規則になりました。
１バイトしか無いのに周期が４００とかありえませんよね。
こんな事があるはずがないので何かが間違っているはずですが、なぜなのかわかりません。

もしバグでないのなら、私の計算結果が狙い通りになっているということかもしれません。
関数mlはループのたびに書き換えられて（$(A^2g^2)^n$の部分です）それ以前の計算結果にたされます。
このためループのたびに値が書き換えられることで本来なら256しか周期を持ち得ない関数がいろんな周期を持つように見えるという効果を出すのだろうか？
つまりlfsrとs-boxを混ぜると予測の難しい数列を得ることができるかもしれない。
普通のlfsrであれば、1つの値が返す周期の種類は1つだけですが、この方法ではループのたびに関数が書き換わるので同じ関数に見えても何種類もの周期を持つ、もはや周期というべきものがない関数になるのです。
それは私が書いた前の計算で得られた結果と同じなのだろうか。
でもそうであれば、lfsrいらないよねという話になりますが、実際はそんなつもりではないです。lfsrは必要ですが、s-boxと混ぜることでどのような相互作用を生み出すのか理解できていないのです。
きっかけは、ランダム多項式の代入値をs-boxに入れるとどうなるかという疑問から始まりました。式の形が同じようにみえるから混ぜられるのではないかという思い込みで始めたことが、2重半直積になるという結果になり（本当に？）、それをプログラミングするとどんな結果が期待できるのか何も考えないでプログラムをしていたことになります。
どんな多項式をランダムに取るのか固定して取るのか、ずっと使うのか使い捨てにするのか、それさえも考えずに。それを今決めよう。
そこで重要なのがこの公式になるはず。

----ここから
ここで$S=g^2A^2,T=g(a)+a,U=(Ab'+c)$
とおくと、
$L=(S,A^2T+U)$：こういう形で混ざるんですね。
$L^2=(S,A^2T+U)(S,A^2T+U)=(S^2,S(A^2T+U)+A^2T+U)$
$L^3=(S,A^2T+U)(S^2,S(A^2T+U)+A^2T+U)
=(S^3,S^2(A^2T+U)+S(A^2T+U)+A^2T+U)$
$V=A^2T+U$とすると、
$L^n=(S^n,S^{(n-1)}+S^{(n-2)}V+S^{(n-3)}V+,...,SV+V)$
------ここですよね。

SもTもUもスカラーなのに大文字にするからわかりにくい。
$g$だけが多項式。$A$は行列。で$g$を帰還多項式だって思い込んだのが過ちだった。
$g$に選ぶ多項式は何でも良かったのだ！
ここでｎ回目の繰り返しが行われたあとどんな関数が得られるのかわかっているので、出てくるはずの値をシード値を決めて計算してやればどうなるか分かる。
$A^2$に周期があるかどうかも同じように計算すれば分かる。
まず$L^1$の場合を計算しよう。で、Lは何かというと、半直積の元なわけですよｗ
ああわかりにくい。
私はまだ自分の出した計算結果を理解していなくて、s-boxが群でないにも関わらず群であるとみなして、混ぜようとしているのが間違っているのかもしれないです。要するに行列使ってるからアフィン群という思い込み。それはもうすでに、S-boxの行列の代わりにビットシフト関数を持っているのでなにか入れて試せばすぐ分かる。（そしてAは周期が４しか無いことが分かる）
いずれにしてもどう動くのが正しいのか、正解を知らずにプログラムをしていたことになり、結論を出すにはもう少し先になりそうです。

unsigned int period = 0, count = 0;
unsigned char lll(unsigned char l)
{
	unsigned char lfs = l;

	int flg = 1, m=11, c2 = 0;
	int i=3;
	int mm =0;
	while (1)
	{
		lfs = lfsr(lfs);
		lfs = ml(lfs, period + 1);
		lfs ^= Dot(lfs, (loo(m) ^ be(m)));
		++period;
		printf("%d %d\n", lfs, period);
		if (lfs == 11){
			count++;
			if(count==1)
			mm=period;
		}
		if (count == i-1 && lfs == 11)
		{	
			mm = period-mm;
			printf("m=%d\n", mm);
			i++;
			mm=period;
			if(i>10)
			 exit(1);
		}
		
	}