久しぶりにCTFに出た。暗号だけやってたけどこの問題だけ解けず。

def bytes_to_long(data):
    return int(data.encode("hex"),16)

def rsa(msg,e,n):
    return pow(bytes_to_long(msg),e,n)

flag = open('flag.txt','r').read()
tmp = randint(2**1023, 2**1024)
e = 65537
p = next_prime(0xDEAD*tmp+randint(2, 2**500))
q = next_prime(0xBEEF*tmp+randint(2, 2**500))
N =  p*q
print('msg1 = '+str(rsa("You can't factor the modulus",e,N)))
print('msg2 = '+str(rsa("If you don't know the modulus!",e,N)))
print('flag = '+str(rsa(flag,e,N)))

RSA。ソースを読むと、平文\(m_1, m_2\)、公開鍵\(e\)、暗号文\(c_1,c_2,c_{\mathrm{flag}}\)が与えられてる。

公開鍵\(n\)がわからなくて、\(p,q\)のだいたいの比がわかる。

もし、\(n\) を計算できれば、\(p,q\)の比から\(p,q\)のbitの上位半分がわかるので、 Coppersmith法が使えて、\(p,q\)が求まる。

さらに、秘密鍵\(d\)が求まるので、flagを復号できる(Coppersmith’s Attack)。という流れ。

まず\(n\)の求める。

$$ c_1 = m_1^e \bmod n $$

$$ c_2 = m_2^e \bmod n $$

だから

$$ m_1^e – c_1 = k_1 n$$

$$ m_2^e – c_2 = k_2 n $$

ここで、\(k_1n,k_2n\)の最大公約数を取る。

$$ \gcd(k_1,k_2)n=\gcd(m_1^e-c_1,m_2^e-c_2) $$

\(\gcd(k_1,k_2)\)は十分小さいと予想できて、適当に全探索すれば\(n\)が求まる。あとでわかるけど\(1\)だったのでその必要はなかった。

CTF中は、多倍長整数と最大公約数の計算に C++ の Boost を使っていて、1時間経っても終わらなくて、もっと良い方法があるのかと思ってやめてしまった。GMP使ったら10秒かからなかった。GMP凄い。

Coopersmith法は、SageMathで実装されている。SageMathの実装だと、パラメータが、
$$ X=\mathrm{ceil}(1/2N^{\beta^2/\delta-\epsilon}) \\ \beta=1.0 \\ \epsilon = \beta/8 $$
で、\( b\ge N^\beta \)となるような\( N\)の任意の約数\( b\)について、\( |x|<X\)かつ\( f(x)=0 \bmod b\)となるような\( x\)を全て求めるアルゴリズム。ただし\( |x|\ge X\)となるような\( x\)を求めることもある。

$$ a_1 = \mathrm{0xDEAD} \\ a_2 = \mathrm{0xBEEF} $$

とすると、

$$ \frac{p}{q}\sim \frac{a_1}{a_2} $$

であり、\(p\)の下界\(\bar{p}\)が求まる。

$$ p>\sqrt{\frac{na_1 \cdot 2^{1023}}{a_2 \cdot 2^{1023} – 2^{500}}} = \bar{p} $$

これを用いて、

$$ f(x)=x+\bar{p} \\
|x|<2^{500} \\
\beta=0.5 $$

として、Coppersmith法を用いると、$$ f(x) = 0 \bmod p $$ となるような \(x\) が求まる。よって、$$ p = x+\bar{p} $$

\(p\)が求まったので、\(q\)が求まり、さらに\(d\)が求まるので flag を復号できる。

p4{S3cur1ty_th0ru9h_0b5cur1ty_4t_i7s_fin3s7}


ソース

参考

Problem – C1 – Codeforces

問題概要

2つの量子状態\( |0\rangle,\ |+\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\)のどちらかがそれぞれ確率50%で与えられる。
どちらが与えられたか確率80%以上で(測定することで)判定せよ。

解法

コンテスト中は、Bloch球を描いてy軸周りに\(\frac{\pi}{4}\)回転すれば確率最大だろうと予想して解きました。条件の確率80%という数字をどう導出するのか気になったのでまとめます。

まず、内積\(\langle 0 | + \rangle\)は、

$$ \langle 0 | + \rangle = \begin{pmatrix}1 & 0\end{pmatrix}\frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 1\end{pmatrix} = \frac{1}{\sqrt{2}}\ $$

であり、これより、

$$ \cos\theta = \frac{1}{\sqrt{2}} \\ \theta = \frac{\pi}{4} $$

であるので、\( |0\rangle \)と\( |+\rangle \)は直交していません。一般に、区別したい状態が直交していないと完全に区別することはできません。

区別できる確率を最大にするには、Bloch球上でy軸周りに\( \frac{\pi}{4} \) 回転し、Pauli Z 基底での測定した結果が \( |0\rangle \)ならばもともと\( |0\rangle \)、\( |1\rangle\)ならばもともと\( |+\rangle\)だったと答えるようにすればよいことは想像がつきます。

なぜかというと下図のように\( |0\rangle,|+\rangle\)がそれぞれ緑色、オレンジ色のベクトルへと変化し、それぞれ\( |0\rangle,|1\rangle\)へのなりやすさが等しくなるからです。

Bloch球上でy軸周りに回転するゲート$$ R_y(\theta)=\begin{pmatrix}\cos\frac{\theta}{2} & -\sin\frac{\theta}{2} \\ \sin\frac{\theta}{2} & \cos\frac{\theta}{2}\end{pmatrix}$$

を用いて、\( \theta\)回転させたときに、正解する確率\( P(\theta)\)がどのように変化していくか見ていきます。

条件付き確率\( P(B|A)\)を次のように定義します。

  • 最初の量子状態が\( |A\rangle\)で、その後ユニタリゲート\( U\)を作用させた後、測定した結果が\( |B\rangle\)である確率

例えば\( P(1|+)\)は、量子状態がもともと\( |+\rangle\)で、その後なんらかのユニタリゲート\( U\)を作用させた後に、測定した結果が\( |1\rangle\)である確率です。

今回作用させるユニタリゲート\( U\)は\( R_y(\theta)\)で、\( P(\theta)\)は条件付き確率を用いて、

$$ P(0)P(0|0)+P(+)P(1|+) $$

と表せます。問題の条件より、\( P(0)=P(+)=\frac{1}{2}\)なので、
$$ P(\theta)=\frac{1}{2}(P(0|0)+P(1|+)) $$

です。\(R_y(\theta)\)は、入力が\( |0\rangle\)のとき、

$$ R_y(\theta)(|0\rangle)=\cos\frac{\theta}{2}|0\rangle+\sin\frac{\theta}{2}|1\rangle $$

であり、入力が\( |+\rangle\)のとき、

$$ R_y(\theta)(|+\rangle)=\frac{1}{\sqrt{2}}(\cos\frac{\theta}{2}-\sin\frac{\theta}{2})|0\rangle+\frac{1}{\sqrt{2}}(\sin\frac{\theta}{2}+\cos\frac{\theta}{2})|1\rangle $$

であるので、

$$ P(0|0)=\cos^2\frac{\theta}{2} \\ P(1|+)=|\frac{1}{\sqrt{2}}(\sin\frac{\theta}{2}+\cos\frac{\theta}{2})|^2=\frac{1}{2}+\sin\frac{\theta}{2}\cos\frac{\theta}{2} $$

となります。以上のことから、

$$ P(\theta) = \frac{1}{2}(\cos^2\frac{\theta}{2}+\frac{1}{2}+\sin\frac{\theta}{2}\cos\frac{\theta}{2}) $$

となり、\( P(\theta)\)の臨界点を求めることで\( \theta=\frac{\pi}{4}\)のとき最大値\( \frac{1}{4}(2+\sqrt{2})=0.85355\cdots\)が求まります。

参考に、Wolfram Alpha で\(P(\theta)\)の最大化を解いてみると、Maximize{(1/2)(1/2+cos^2x+cosxsinx), 0<=x<=π/2},{x} – Wolfram|Alpha のようになります。

つまり、理想的には約85%の確率で\( |0\rangle\)と\( |+\rangle\)が区別できるので、誤差を考慮してこの問題では80%以上という条件にしたのだろうとわかります。

ソースコード

Ry(PI()/4.0, q);
if(M(q)==One){
  return 1;
}
return 0;

参考