sig-ctf-2016S-4.1

僕の知ってる数論

この章で出てくる文字は、断らない限り全部整数。

合同式

$a \equiv b \ (mod \ n) \Leftrightarrow \exists k \in \mathbb Z, a-b=kn$

$a,b,c \in \mathbb Z, m \in \mathbb N$

1. $a \equiv b \Rightarrow a+c \equiv b+c$
2. $a \equiv b \wedge c \equiv d \Rightarrow ac \equiv bd$
3. $a \equiv b \Rightarrow a^m \equiv b^m$

最大公約数

aとbの最大公約数を$\gcd(a,b)$とか単に$(a,b)$とか書く。

ユークリッドの互除法を用いると、$\gcd(a,b)$は$O(\log ab)$で求まる。

さらに、拡張されたユークリッドの互除法によって、(x,y)に対して$ax+by=\gcd(x,y)$なる(a,b)を求められる。

逆元

$(x,n)=1$のとき、$ax \equiv 1 \ (mod \ n)$なるaを容易に求められる。この$a$を、$x^{-1}$とかく。

求めるには、上の拡張されたユークリッドの互除法において、$x=x, y=n, a=a$とすればよい。

カーマイケルの定理/オイラーの定理/フェルマーの小定理

カーマイケルの定理: カーマイケル関数λに対して、
$(a,n)=1 \Rightarrow a^{\lambda (n)} \equiv 1 \ (mod \ n)$

上の定理を弱くして、次の定理が示される。

オイラーの定理: オイラーのトーシェント関数φに対して、
$(a,n)=1 \Rightarrow a^{\phi (n)} \equiv 1 \ (mod \ n)$

更に弱くして、次の定理が示される。

フェルマーの小定理: $p \in \mathbb P$に対して、
$(a,p)=1 \Rightarrow a^{p-1} \equiv 1 \ (mod \ p)$

中国剰余定理

中国剰余定理: $(m,n)=1$のとき、
$x \equiv a \ (mod \ m)$かつ$x \equiv b \ (mod \ n)$なる$x$が$mn$を法として一意的に存在する。

特に、$(m,n)=1$のとき、
$x \equiv y \ (mod \ m) \wedge x \equiv y \ (mod \ n) \Leftrightarrow x \equiv y \ (mod \ mn)$

一意的とは、そのようなxのmnを法とした剰余はすべて等しいということ。

暗号でしょっちゅうでてくる気がする定理

$k \in \mathbb N$で、$a^m \equiv 1 \ (mod\ n)$のとき、$a^{km} \equiv 1 \ (mod \ n)$

それはそう。

平方剰余

$(a,b)=1$のとき、$x^2 \equiv a \ (mod \ b)$なるxが存在するときaはbを法として平方剰余であるという。

ルジャンドル記号: aが奇素数pを法として平方剰余なとき、$\left( \frac {a} {p} \right)=1$、平方非剰余なとき$\left( \frac {a} {p} \right)=-1$とかく。

定理: $\left( \frac{ab}{p} \right) = \left( \frac {a}{p} \right) \left( \frac {b}{p} \right)$

オイラーの規準: pは奇素数。
$\left( \frac{a}{p} \right)≡a^{\frac{p−1}2} \ mod\ p$
http://mathtrain.jp/criterion

平方剰余の相互法則: p,qは奇素数。
$\left( \frac {p}{q} \right)\left( \frac {q}{p} \right)=(-1)^{\frac{p-1}{2} \frac{q-1}{2}}$

拡張みたいなので、ヤコビ記号とかいうのもある。
さらに拡張で、クロネッカー記号とかいうのもある。

生成元

集合$G$に対して位数とは、$|G|$のこと。群$(G,+)$で、$g \in G$の位数とは、$g^n = 1$となる最小の自然数nのこと。
ある二項演算があってそのもとで$G = {g^n | n \in \mathbb N }$のとき、$g$を$G$の生成元といい、$G=$と書く。

$Z_p$には生成元が少なくとも1つ存在する。

Rabin

準備

1. $p,q \in \mathbb P (p \neq q)$を用意
2. $n=pq$を計算
3. $0 \le B \lt n$を用意

後々を考えると、B=0ならp,qはどんな素数でも良いけれど、Bが0でないならp,qは奇素数でなければならなそう。

暗号化

$c=x(x+B) \ mod \ n$

復号

1. $x_p = \pm \sqrt {c + \frac {B^2}{4}} - \frac {B}{2} \ mod \ p$,$x_q = \pm \sqrt {c + \frac {B^2}{4}} - \frac {B}{2} \ mod \ q$ を計算
2. $x \equiv x_p \ (mod \ p) \wedge x \equiv x_q \ (mod \ q)$を中国剰余定理で計算
3. 求まる４つのxのうちいずれかが解

平方根の計算には、たとえばCipolla's algorithmを使う。

p,qに4k+3型の素数を使うと、平方根の計算に公式が使えて簡単になる。

RSA

準備

1. $p,q \in \mathbb P (p \neq q)$を準備
2. $n=pq, \phi(n)=(p-1)(q-1)$を計算
3. p,qは破棄
4. $e \in \mathbb N \wedge (e, \phi(n))=1 \wedge e \lt \phi(n)$なる$e$を準備
5. $\phi(n)$を法として$d=e^{-1}$を計算

暗号化

$c = p^e \ mod \ n$

復号

$p = c^d \ mod \ n$

証明

$c^d \equiv p^{ed} \equiv p^{k \phi(n)+1} = p^{k \phi(n)} p \equiv 1p \equiv p$

tools

• 数論的計算機 PARI/GP ,CTF向け使い方
• 怖い数学を使った素因数分解器 Msieve

prove it!

• ユークリッドの互除法
• フェルマーの小定理、オイラーの定理（どちらから証明しても良い）
• 平方剰余ならばルジャンドル記号が1になる
• ルジャンドル記号が1ならば平方剰余
• $Z_p$の生成元の存在

Written with StackEdit.