K3RN3LCTF Pascal RSA

問題概要

次のPythonファイルと出力が与えら得れる．

triangle =[[1]]
flag = open('flag.txt','rb').read()

from Crypto.Util.number import getPrime,bytes_to_long
from math import gcd
p = getPrime(20)
while len(triangle[-1]) <= p:
    r = [1]
    for i in range(len(triangle[-1]) - 1):
        r.append(triangle[-1][i] + triangle[-1][i+1])
    r.append(1)
    triangle.append(r)
code = ''
for x in triangle[-1]:
    code+=str(x%2)
d = int(code,2)
while True:
    P = getPrime(512)
    Q = getPrime(512)
    if gcd(d, (P-1)*(Q-1)) == 1:
        N = P*Q
        e = pow(d,-1,(P-1)*(Q-1))
        break
enc = pow(bytes_to_long(flag), e, N)
file = open('challenge.txt','w')
file.write(f'p = {p}\nenc = {enc}\nN = {N}')

p = 751921
enc = 9820620269072860401665805101881284961421302475382405373888746780467409082575009633494008131637326951607592072546997831382261451919226781535697132306297667495663005072695351430953630099751335020192098397722937812151774786232707555386479774460529133941848677746581256792960571286418291329780280128419358700449
N = 84317137476812805534382776304205215410373527909056058618583365618383741423290821410270929574317899945862949829480082811084554009265439540307568537940249227388935154641779863441301292378975855625325375299980291629608995049742243591901547177853086110999523167557589597375590016312480342995048934488540440868447

問題名がヒントになっていて，$p=751922$段(便宜上，$1$が一つだけの三角形を$0$段と呼ぶことにする)のパスカルの三角形を作り，最下段の偶奇によって$d$を作っている．この$d$を求める問題．問題ファイルにパスカルの三角形を求めるプログラムがついているが，$p=75192$段のパスカル三角形を作るには時間計算量$O(p^2)$がかかり，非常に時間がかかる．途中経過をすっ飛ばして，最下段の偶奇のみを求める何らかの方法を見つけなければならない．

パスカルの三角形というのは，次のようなものである． $$ \begin{array}{c} 1 \\ 1\ 1\\ 1\ 2\ 1\\ 1\ 3\ 3\ 1\\ 1\ 4\ 6\ 4\ 1\\ 1\ 5\ 10\ 10\ 5\ 1\\ \vdots \qquad \vdots \qquad \vdots \end{array} $$ これは，二項係数を並べたものと見ることができる．なぜこれが成り立つかは，三角形の上の頂点からその場所までの経路の数を考えるとわかりやすい(ここではあまり説明しない)． $$ \begin{array}{c} {}_0\textrm{C}_0 \\ {}_1\textrm{C}_0\ {}_1\textrm{C}_1\\ {}_2\textrm{C}_0\ {}_2\textrm{C}_1\ {}_2\textrm{C}_2\\ {}_3\textrm{C}_0\ {}_3\textrm{C}_1\ {}_3\textrm{C}_2\ {}_3\textrm{C}_3\\ {}_4\textrm{C}_0\ {}_4\textrm{C}_1\ {}_4\textrm{C}_2\ {}_4\textrm{C}_3\ {}_4\textrm{C}_4\\ \vdots \qquad \vdots \qquad \vdots \end{array} $$ $p$段のパスカルの三角形の最下段は，${}_p\textrm{C}_i(0\leq i\leq p)$が並んでいる．

ここで，ルーカスの定理を使う．

$$ {}_m\textrm{C}_n = \prod_{i=0}^{k} {}_{m_i}\textrm{C}_{n_i} \pmod p \\ $$ ただし，$m_k m_{k-1} m_{k-2} \cdots m_1 m_0$は $m$の$p$進数表示，$n_k n_{k-1} n_{k-2} \cdots n_1 n_0$は $n$の$p$進数表示である．特に，$\pmod 2$の世界は次の$4$パターンしか出てこない． $$ {}_1\textrm{C}_0 = 1 \\ {}_1\textrm{C}_1 = 1 \\ {}_0\textrm{C}_0 = 1 \\ {}_0\textrm{C}_1 = 0 $$ よって，ルーカスの定理を使うときに${}_0\textrm{C}_1$($m_i=0$かつ$n_i=1$となる$i$)が1つも出てこなかったら，計算結果は$1 \pmod 2$，すなわち奇数となる．これは，m&n == nが真であることと同値である．

これで，${}_p\textrm{C}_i(0\leq i\leq p)$の偶奇が各$i$について$O(1)$で計算できる．

p = 751921
enc = 9820620269072860401665805101881284961421302475382405373888746780467409082575009633494008131637326951607592072546997831382261451919226781535697132306297667495663005072695351430953630099751335020192098397722937812151774786232707555386479774460529133941848677746581256792960571286418291329780280128419358700449
N = 84317137476812805534382776304205215410373527909056058618583365618383741423290821410270929574317899945862949829480082811084554009265439540307568537940249227388935154641779863441301292378975855625325375299980291629608995049742243591901547177853086110999523167557589597375590016312480342995048934488540440868447


def is_nCk_odd( n,k):
    return n&k == k

code=''
for i in range(0,p+1):
    ch=is_nCk_odd(p,i)
    if ch:
        code+='1'
    else:
        code+='0'

d=int(code,2)

print(hex(pow(enc,d,N)))

めっちゃ数論

shiba's writeups

K3RN3LCTF Pascal RSA

問題概要

解法

コメント