暗号理論の問題

条件 $(1)$ を式にする。

$$E(E(x))\equiv a(ax+b)+b=a^{2}x+(a+1)b(\mathrm{mod}26)$$
である。これがすべての $x$ について $x$ と合同になる条件を考える。$x=0$ を代入すると $(a+1)b\equiv 0(\mathrm{mod}26)$、さらに $x=1$ を代入して差をとると $a^2\equiv 1(\mathrm{mod}26)$ が必要である。逆にこの 2 つが成り立てば、すべての $x$ で $E(E(x))\equiv x$ となる。よって条件 $(1)$ は
$$a^2\equiv 1(\mathrm{mod}26),(a+1)b\equiv 0(\mathrm{mod}26)$$
と同値である。

$a^2\equiv 1(\mathrm{mod}26)$ を解く。

$26=2\cdot 13$ なので、中国剰余定理より $a^2\equiv 1(\mathrm{mod}2)$ かつ $a^2\equiv 1(\mathrm{mod}13)$ と同値である。
- $a^2\equiv 1(\mathrm{mod}2)$ は $a$ が奇数であること。
- $13$ は素数なので $a^2-1=(a-1)(a+1)\equiv 0(\mathrm{mod}13)$ より $a\equiv 1$ または $a\equiv 12(\mathrm{mod}13)$。

$0\le a\le 25$ で $a\equiv 1(\mathrm{mod}13)$ となるのは $1,14$、$a\equiv 12(\mathrm{mod}13)$ となるのは $12,25$。このうち奇数は $a=1,25$ である（どちらも $\gcd (a,26)=1$ を満たす）。

$b$ の条件（条件 $(1)$ の残り）。

• $a=1$ のとき: $2b\equiv 0(\mathrm{mod}26)$、すなわち $b\equiv 0(\mathrm{mod}13)$ なので $b=0,13$。
• $a=25$ のとき: $(a+1)b=26b\equiv 0(\mathrm{mod}26)$ は常に成り立つので、$b=0,1,\dots ,25$ のすべて。

条件 $(2)$ を調べる。

$E(x)=x$ となる $x$ が存在することは、合同式
$$(a-1)x+b\equiv 0(\mathrm{mod}26)$$
が解をもつことと同値である。

• $a=1$ のとき: 合同式は $b\equiv 0(\mathrm{mod}26)$ となる。$b=0$ ならすべての $x$ が解（恒等写像）、$b=13$ なら解なし。よって条件 $(2)$ を満たすのは $b=13$ の $1$ 個。
• $a=25$ のとき: 合同式は $24x\equiv -b(\mathrm{mod}26)$ となる。$\gcd (24,26)=2$ なので、これが解をもつのは $2\mid b$ のときに限る（$2\mid b$ なら $12x\equiv -\frac{b}{2}(\mathrm{mod}13)$ となり、$\gcd (12,13)=1$ より解がある）。よって条件 $(2)$ を満たすのは $b$ が奇数のとき、すなわち $b=1,3,\dots ,25$ の $13$ 個。

まとめ。

よい鍵は $(1,13)$ の $1$ 個と、$(25,b)$（$b$ は $0\le b\le 25$ の奇数）の $13$ 個で、合計
$$1+13=14$$
個である。

（確認: たとえば $(a,b)=(25,1)$ では $E(x)\equiv -x+1$ で、$E(E(x))\equiv -(-x+1)+1=x$。また $E(x)=x$ は $2x\equiv 1(\mathrm{mod}26)$ となり、左辺は偶数、右辺は奇数なので解がない。）

条件 (1): $E(E(x))=a(ax+b)+b=a^{2}x+(a+1)b(\mathrm{mod}26)$。これがすべての $x$ で $x$ に等しい条件は、$x=0$ と $x=1$ を代入して比べることにより $a^2\equiv 1$ かつ $(a+1)b\equiv 0(\mathrm{mod}26)$。\n\n$a^2\equiv 1(\mathrm{mod}26)$ は mod 2 で $a$ が奇数、mod 13 で $a\equiv \pm 1$。$0\le a\le 25$ ではそれぞれ $a\equiv 1(\mathrm{mod}13)$ かつ奇数が $a=1$、$a\equiv 12(\mathrm{mod}13)$ かつ奇数が $a=25$。よって $a\in \{1,25\}$（どちらも $\gcd (a,26)=1$）。\n\n- $a=1$: $(a+1)b=2b\equiv 0(\mathrm{mod}26)$ より $b\in \{0,13\}$。条件 (2): $E(x)=x+b\ne x$ がすべての $x$ で成り立つには $b\ne 0$。よって $b=13$ の 1 通り。\n- $a=25\equiv -1$: $(a+1)b=26b\equiv 0$ は常に成り立つので $b$ は $0\le b\le 25$ の任意。条件 (2): $E(x)=-x+b\equiv x$ すなわち $2x\equiv b(\mathrm{mod}26)$ が解 $x$ をもたないことが必要。これは $b$ が奇数のときに限る（$b$ が偶数なら $x=b/2$ が解）。$b$ が奇数なのは 13 通り。\n\n合計 $1+13=14$。\n\n検算: $(1,13)$: $E(x)=x+13$, $E(E(x))=x+26\equiv x$、不動点なし ✓。$(25,1)$: $E(x)=1-x$, $E^2(x)=x$、$2x\equiv 1(\mathrm{mod}26)$ は解なし ✓。