---
tags: crypto
---

# CRT-RSAとfault attack

## notation

以下、特に断りが無ければ各記号を次のように扱う

* $p, q$ : 素数、公開鍵の生成に使う
* $N$ : 2素数 $p, q$ の積、いつもの公開鍵の法の方
* $e$ : いつもの公開鍵の指数の方
* $m$ : 平文
* $c$ : 暗号文、上記の記号を用いると次のようになる -> $c = m^e \mod N$
* $d$ : いつもの秘密鍵、$m = c^d \mod N$ が成り立つ

## 中国剰余定理とRSA

通常のRSAでは $d$ を秘密鍵として復号しているが計算量がそこそこ大きいというデメリットがある。そこで中国剰余定理を使って復号時のコストを下げる事が出来る。

仮に次の2式が成り立つ $x$ を求められたとする。

$$
x \equiv c^d \mod p \\
x \equiv c^d \mod q
$$

これは中国剰余定理を用いると $pq = N$ を法として1つに答えが定まる。そしてそれは平文 $m$ に一致するはずである。
よって $p,q$ を法として $c^d$ と合同な値をそれぞれ用意する事が出来れば復号に問題は生じない。これを $c'^{d'}$ という新しい暗号文と秘密鍵で表現して計算量を下げるのがCRT-RSAの目的である。

念の為、上の連立合同方程式は $x \equiv m \mod N$ が解となる事の証明を与えておく。

$c^d \equiv m \mod N$ より $c^d = k_N N + m$ とおくことが出来る。これは $N = pq$ より $p, q$ を法とする合同式に書き換えることが出来、次のようになる。

$$
c^d \equiv m \mod p \\
c^d \equiv m \mod q
$$

したがって対象の合同方程式は

$$
x \equiv m \mod p \\
x \equiv m \mod q
$$

になる。

合同式を外すと $x = k_p p + m = k_q q + m$ となる。 $p, q$ は互いに素(というかどちらも素数)なので $k_p = kq, k_q = kp$ と整数 $k$ を用いて表すことが出来る。
これで $x = kqp + m = kN + m$ となったので $x \equiv m \mod N$ であることが示された。

## CRT-RSA

では $p, q$ を法とした新しい合同方程式で指数がより小さいものを考える(今はまだ $d$ である)。その前に元の方程式の $c$ はそれぞれ次のように書き換えられる。

$$
x \equiv c_p^d \mod p \\
x \equiv c_q^d \mod q
$$

ここで $c_p :\equiv c \mod p, c_q :\equiv c \mod q$ である。

続いて $d_p :\equiv d \mod (p-1), d_q :\equiv d \mod (q-1)$ を用意する。これを秘密鍵のように扱って $c_p, c_q$ の指数として計算するとフェルマーの定理を用いて次のようになる。

$$
c_p^d = c_p^{k_{dp}(p-1) + d_p} \equiv c_p^{d_p} \mod p \\
c_q^d = c_q^{k_{dq}(q-1) + d_q} \equiv c_q^{d_q} \mod q
$$

故に解きたい合同方程式は次のように縮小できる

$$
x \equiv c_p^{d_p} \mod p \\
x \equiv c_q^{d_q} \mod q \\
$$

ということで鍵生成の際に $d_p, d_q$ も一緒に生成し、秘密鍵として保持しておくことで復号時の計算量を下げることが出来る(実際どの程度下がるかはよく知らないしあんまり興味もないです、気が向いたら追記します)

以上より暗号文の復号手順は次のようになる。

1. 暗号文 $c$ に対して $p, q$ を法とした剰余である $c_p, c_q$ を計算する
2. 秘密鍵 $d_p, d_q$ を用いて $c_p^{d_p} \mod p, c_q^{d_q} \mod q$ を計算する
3. $x \equiv c_p^{d_p} \mod p, x \equiv c_q^{d_q} \mod q$ を満たすような $x \mod N$ を計算する

と、ここで一応完結はしているのだが下記に示すGarner法という連立合同方程式の解法において $p^{-1} \mod q$ を計算する必要があるため秘密鍵にこの値が追加されることもある(よくcoefficientと呼ばれている)

## Garner法

この形の合同方程式を解く方法は色々あるが(私は[Wikipediaに載ってる方法](https://ja.wikipedia.org/wiki/%E4%B8%AD%E5%9B%BD%E3%81%AE%E5%89%B0%E4%BD%99%E5%AE%9A%E7%90%86#%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95)が好きです)、Garner法というのものを用いる。詳しくはググって欲しいが、各方程式を満たすように $x$ を更新していくものである。

CRT-RSAにこれを適用すると次のようになる。

0. 記法として $m_p :\equiv c_p^{d_p} \mod p, m_q :\equiv c_q^{d_q} \mod q$ を導入する
1. $x \equiv m_p \mod p$ なので $x = kp + m_p$ のように表すことが出来る。ここで $k$ はまだ不明である。
2. これをもう1つの方程式に代入すると $kp + m_p \equiv m_q \mod q$ である。
3. よって $k \equiv p^{-1}(m_q - m_p) \mod q$ が成立するため $k$ を求めることが出来る
4. つまり $x = kp + m_p$ も求まったことになる。

ここで先程少しだけ触れた $p^{-1} \mod q$ が登場する。この値は平文によらず、鍵のみに依存するので鍵生成時に事前に計算しておくことが可能である。秘密鍵はこれも含めて保存される(OpenSSL等は確かそう)。

## 署名

CRT-RSAは通常のRSA同様署名へと転用することが出来る。手順は次の通り。

0. 鍵生成は済んでいるものとする( $cf :\equiv p^{-1} \mod q$ と定義する)
1. $s_p :\equiv m^{d_p} \mod p, s_q :\equiv m^{d_q} \mod q$ を計算する
2. $s \equiv s_p \mod p, s \equiv s_q \mod q$ となるような $s$ を計算する
3. 具体的には $k \equiv cf(s_q - s_p) \mod q$ を計算し、 $s = kp + s_p$ を署名とする

なおこれは $cf :\equiv p^{-1} \mod q$ として計算しているが、 $cf :\equiv q^{-1} \mod p$ として計算しても $p, q$ が入れ替わるだけで最終的な署名は同じになる。

この署名が本当に検証出来るのかを証明する。つまり $s^e \equiv m \mod N$ である事を証明する。
これは直接値を計算しなくても $s \equiv m^d \mod N$ であることを証明すれば良い。
まず $d_p, d_q$ の定義から $m^d \equiv m^{d_p} \equiv s \mod p, m^d \equiv m^{d_q} \equiv s \mod q$ である。
よって $s = m^d + pk_p = m^d + qk_q$ と整数 $k_p, k_q$ を用いて表す事ができ、しかも $p, q$ は互いに素なので $k_p = kq, k_q = kp$ となる整数 $k$ が存在する。
これを代入すると $s = m^d + pqk = m^d + Nk$ となることから $s \equiv m^d \mod N$ である。

### Fault Attack

上記署名手順の1において計算ミスが発生し、正しい署名が得られないとする。実はこの場合でも誤って発行された署名とメッセージと公開鍵から正しい署名を復元することが出来る。具体的な手順は次の通り。

0. 上記署名は $p,q$ に対して対称な手順なので $s_q$ が正しく計算されなかったと仮定し、この時得られた署名を $s_f := k_fp + s_p$ とおく
1. $y :\equiv s_f^{e} \mod N$ を計算する
2. $gcd(y - m, N)$ を計算する、この結果は $N$ の素因数になるはずで1でなければその結果から各秘密鍵を導出出来る
3. ということは本来得られるはずだった署名も入手することが出来る

これがなぜ成立するかを証明する。まず補題として $x \equiv kp \mod pq$ である $x$ は $p$ を約数として持つ事を証明する。
これは簡単で $x = pqk_N + kp = (qk_N + k)p$ となることから $x$ は $p$ を約数として持つことが示された。

ここで $y :\equiv s_f^{e} = (k_fp + s_p)^e \mod N$ を計算すると二項定理から ${s_p}^e$ 以外の項は $p$ の $i (>0)$ 次の項となる。これを $y \equiv Kp + {s_p}^e \mod N$ と表す。

${s_p}^e$ に関しては ${s_p}^e \equiv m^{ed_p} \equiv m^{ed} \mod p$ という関係が成り立つ。よって ${s_p}^e = pk_s + m^{ed}$ が成り立つ。これを $y$ の合同式に代入すると $y \equiv Kp + pk_s + m^{ed} \equiv pK' + m \mod N$ となる( $p$ で括って整数 $K'$ を利用したのと $m^{ed} \equiv m \mod N$ を適用した)。
よって $y - m \equiv pK' \mod N$ である。

これで上の補題を利用すると $y-m$ は $p$ を約数として持つことがわかる。故に $N = pq$ との公約数を計算すると $p$ が出てくる。

## 実装

from math import gcd
from Crypto.Util.number import inverse, getPrime, getRandomNBitInteger


class KeyCRTRSA:
    def __init__(self, n=2048):
        self.bit_length = n
        self.e = 0x10001
        self.genSecretKey(self.bit_length)


    def genPrimes(self, n):
        p = getPrime(n)
        q = getPrime(n)

        return p, q


    def genSecretKey(self, n):
        self.p, self.q = self.genPrimes(self.bit_length)
        self.n = self.p * self.q
        self.d = inverse(self.e, (self.p - 1) * (self.q - 1))
        self.dp = self.d % (self.p - 1)
        self.dq = self.d % (self.q - 1)
        self.cf = inverse(self.p, self.q)


    def getPublicKey(self):
        return self.n, self.e


    # danger
    def getPrivateKey(self):
        return self.dp, self.dq, self.cf


    def encrypt(self, m):
        return pow(m, self.e, self.n)


    def decrypt(self, c):
        c_p, c_q = c % self.p, c % self.q
        m_p, m_q = pow(c_p, self.dp, self.p), pow(c_q, self.dq, self.q)
        k = self.cf * (m_q - m_p) % self.q

        return (k*self.p + m_p) % self.n


    def sign(self, m):
        return self.decrypt(m)


    def verify(self, s, m):
        return self.encrypt(s) == m


    # codes for fault attack
    def invalidSign(self, m):
        sp, sq = pow(m, self.dp, self.p), pow(m, self.dq, self.q)
        # inject fault
        sq = getRandomNBitInteger(self.bit_length)
        k = self.cf * (sq - sp) % self.q

        return (k * self.p + sp) % self.n


def genKey(n=2048):
    return KeyCRTRSA(n)


def fault_attack(invalid_s, m, n, e):
    p = gcd(pow(invalid_s, e, n) - m, n)
    if p == 1:
        raise ValueError("Both sp and sq are invalid")
    q = n // p
    d = inverse(e, (p-1)*(q-1))

    return pow(m, d, n), d


if __name__ == "__main__":
    # generate key
    crt_rsa = genKey()
    n, e = crt_rsa.getPublicKey()

    # encryption and decryption
    m = getRandomNBitInteger(3072)
    c = crt_rsa.encrypt(m)
    assert m == crt_rsa.decrypt(c)

    # sign and verification
    s = crt_rsa.sign(m)
    if crt_rsa.verify(s, m):
        print("[+] Verified")
    else:
        print("[+] NG")
        exit()

    # Fault Attack
    invalid_s = crt_rsa.invalidSign(m)
    assert not crt_rsa.verify(invalid_s, m)

    recovered_s, d = fault_attack(invalid_s, m, n, e)

    if crt_rsa.verify(recovered_s, m):
        print("[+] Attack is Successful!!")
    else:
        print("[+] ha?")