学生の頃から通算で三回くらい、学んで忘れてを繰り返している。「教科書読めばまた理解できる」という安心感だけは毎度残っているんだが、教科書読むより早く思い出したい。自分用の最短ルートメモを書いてみよう。できるかな。

Groupの理解が少し必要。

Definitions

A $group$ is a set $\mathbb{G}$ along with a binary operation $\bullet$ that satisfies the following.

closure: $\forall x,y \in \mathbb{G}$, $x \bullet y \in \mathbb{G}$

existence of identity: $\exists e \in \mathbb{G}$ such that $\forall x \in \mathbb{G}$, $e \bullet x = x = x \bullet e$

existence of inverses: $\forall x \in \mathbb{G}$, $\exists y \in \mathbb{G}$ such that $x \bullet y = e = y \bullet x$

associativity: $\forall x,y,z \in \mathbb{G}$, $(x \bullet y) \bullet z = x \bullet (y \bullet z)$

Additionally, a $group (\mathbb{G}, \bullet ) $ is $abelian$ if the following is satisfied.

commutativity: $\forall x,y \in \mathbb{G}$, $x \bullet y = y \bullet x$

The $order$ $|\mathbb{G}|$ is the number of elements in $\mathbb{G}$ when $\mathbb{G}$ has a finite number of elements.

Finally, for the convenience of later discussions,

$\mathbb{Z}_N^* := \{x \in \{1,…, N-1 \} | gcd(x,N) = 1 \} $

$\phi(N) := |\mathbb{Z}_N^*|$

Claims

Claim 1 ==> Claim 2
Claim 3 ==> Claim 4 ==> Claim 5

という構図。結局はClaim 2とClaim 5が欲しい。

Claim 1

Let $\mathbb{G}$ be a finite abelian group with order $m$. Then for all $g \in \mathbb{G}$, $g^m = 1$

Proof: Let $g_1,..,g_m$ be the distinct elements of $\mathbb{G}$. Then, so are $gg_1,..,gg_m$ because, for $i \neq j$,

$$gg_i = gg_j \implies g^{-1}gg_i = g^{-1}gg_j \implies g_i = g_j$$

Since $\mathbb{G}$ is abelian, it follows that

$$g_1g_2…g_m = (gg_1)(gg_2)…(gg_m) = g^mg_1g_2…g_m$$

Therefore, $g^m = 1$. $$\tag*{$\blacksquare$}$$

Claim 2

Let $\mathbb{G}$ be a finite abelian group with order $m > 1$. Then for any $g \in \mathbb{G}$ and for any integer $x$, $g^x = g^{x \bmod m}$.

Proof: We can say the following for some integer $q$, using $g^m = 1$ from Claim 1 above. $$g^x = g^{qm + (x \bmod m)} = g^{qm}g^{x \bmod m} = (g^m)^qg^{x \bmod m} = 1^qg^{x \bmod m} = g^{x \bmod m}$$

$$\tag*{$\blacksquare$}$$

Claim 3

Let $a,b \in \mathbb{N}$. Then,

$\exists X,Y \in \mathbb{Z}$ such that $Xa + Yb = gcd(a,b)$.

Furthermore, $gcd(a,b)$ is the smallest positive integer that can be expressed in this way.

Proof: Consider the set $I := \{xa + yb | x,y \in \mathbb{Z}\}$. Note $a,b \in I$, and thus $I$ certainly contains some positive integers. Let $d$ be the smallest positive integer in $I$ and write $d = Xa + Yb$ for some $X,Y \in \mathbb{Z}$. It suffices to show that $d = gcd(a,b)$.

Let $c$ be an arbitrary element in $I$. Then we can write $c = x’a + y’b$ for some $x’,y’\in \mathbb{Z}$. Also, since $d \leq c$, we can write $c = qd + r$ for some integers $q,r$ with $0 \leq r < d$. It follows that

$$r = c - qd = x’a + y’b - q(Xa + Yb) = (x’ - qX)a + (y’ - qY)b \in I$$

If $r \neq 0$, given $r < d$, it contradicts $d$ being the smallest positive integer in $I$. Therefore, $r = 0$. It follows that $c = qd$, and that $d|c$ for any $c \in I$. Since $a,b \in I$, $d$ is a common divisor of $a$ and $b$.

It remains to show $d$ is the greatest common divisor. Assume there exists an integer $d’ > d$ that $d’|a$ and $d’|b$.

$$d’|a \land d’|b \implies d’|Xa + Xb \implies d’|d$$

However, this is impossible if $d’ > d$. Hence $d = gcd(a,b)$

$$\tag*{$\blacksquare$}$$

Claim 4

Let $b,N \in \mathbb{Z}$ with $b \geq 1$ and $N > 1$. Then $b$ is invertible modulo $N$ if and only if $gcd(b,N) = 1$.

Proof: Suppose $b$ is invertible module $N$, and let $c$ denote its inverse. Then $bc = 1 \bmod N$. It follows that $bc = 1 + xN$ for some $x \in \mathbb{Z}$, or $bc - xN = 1$. From Claim 3, $gcd(b,N)$ is the smallest positive integer that can be expressed in this form and $1$ is the smallest positive integer. Therefore, $gcd(b,N) = 1$.

Conversely, suppose $gcd(b,N) = 1$. By Claim 3, there exists $X,Y \in \mathbb{Z}$ such that $Xb + YN = gcd(b,N)$. From there, we have the following.

$$Xb + YN = gcd(b,N) \implies Xb + YN = 1 \implies Xb = 1 \bmod N$$

Therefore, $X$ is a multiplicative inverse of $b$. $b$ is invertible.

$$\tag*{$\blacksquare$}$$

Claim 5

$\mathbb{Z}_N^*$ is an abelian group under multiplication modulo $N$

Proof:

existence of identity: $1$ is the identity in integer multiplication and it’s in $\mathbb{Z}_N^*$
associativity: Integer multiplication is associative.
commutativity: Integer multiplication is commutative.
existence of inverses: Let $x \in \mathbb{Z}_N^*$. By definition of $\mathbb{Z}_N^*$, $gcd(x,N) = 1$. Therefore, by Claim 4, $x$ is invertible modulo $N$. From the commutativity, $x$ is inverse of $x^{-1}$ as well. Therefore, by Claim 4, $gcd(x^{-1},N) = 1$. It follows that $x^{-1} \in \mathbb{Z}_N^*$.
closure: Let $a,b \in \mathbb{Z}_N^*$. By invertibility, $a^{-1},b^{-1} \in \mathbb{Z}_N^*$ exist. It follows that $ab \bmod N$ has inverse $b^{-1}a^{-1} \bmod N$. By Claim 4, this means $gcd((ab \bmod N), N) = 1$. Therefore, by definition of $\mathbb{Z}_N^*$, $ab \in \mathbb{Z}_N^*$.

$$\tag*{$\blacksquare$}$$

RSA Problem

準備が整った。以下の問題は十分に難しいだろうということがRSA暗号のベースとなっている。

Given $c \in \mathbb{Z}_N^*$, compute $m \in \mathbb{Z}_N^* $, where

$$m^e = c \bmod N$$

and

$N$ is a product of two primes

$e,d \in \mathbb{N} $, $gcd(e, \phi(N)) = 1$, and $ed = 1 \bmod \phi(N)$

Key pair

公開鍵は$(N,e)$. plaintext $m$ を上の式でciphertext $c$ に変えて、秘密鍵保持者に送る。

秘密鍵は$(N,d)$. Claim 2とClaim 5から、 $$\forall g \in \mathbb{Z}_N^*, g^{x} = g^{x \bmod \phi(N)} \bmod N$$

と言える。秘密鍵保持者は以下の式でplaintext $m$ を得る。

$$c^d = m^{ed} = m^{ed \bmod \phi(N)} = m^1 = m \bmod N$$

$d$

$gcd(e, \phi(N)) = 1$という条件があるので、Claim 4より、$d$は存在する。

$N$

$N$はpublicだが、$N$を構成する二つの素数は秘密。それらがバレると、$\phi(N)$がバレ、$d$がバレる。

$\phi(N)$

Let $N = pq$ for some primes $p$ and $q$.

$$\mathbb{Z}_N^* = \{1,..,N-1\}\setminus\{p,..,(q-1)p,q,..,(p-1)q\}$$

Thus,

$$\phi(N) = |\mathbb{Z}_N^*| = (N-1)-(q-1)-(p-1) = pq-q-p+1 = (p-1)(q-1) $$

Extended Euclidean algorithm

Runs in polynomial time.

Input: $a,b \in \mathbb{Z}$ with $a \geq b > 0$
Output: $(g, X, Y)$ such that $g = gcd(a,b)$ and $Xa + Yb = g$

うちらの場合、$(e,\phi(N))$を元に、$Xe + Y\phi(N) = gcd(e,\phi(N)) = 1$となる$(X,Y)$が求められてしまう。この$X$こそまさに$d$.

というわけで、RSA problemはfactoring以上に難しくはなり得ない。

Reference

Introduction to Modern Cryptography - 相変わらず読みやすい。

Minimal group theory to understand RSA problem

May 22, 2018

Definitions

Claims

Claim 1

Claim 2

Claim 3

Claim 4

Claim 5

RSA Problem

Key pair

\(d\)

\(N\)

\(\phi(N)\)

Extended Euclidean algorithm

Reference