About

関連リンク

  • shiba's Library
    • 競プロ用のライブラリをまとめています．CTFでもたまに競プロの力を使うことがあるので参考になるかも．

知識

RSA

必要な知識

  • モジュロ演算
  • Fermatの小定理，オイラーの$\varphi$関数
  • 拡張ユークリッドの互除法

概要

素数$p$と$q$を用いて，$n=pq$とする． $e$を公開鍵として，$d$を秘密鍵とする． $e$と$d$は，以下の式を満たす必要がある． $$ed\equiv 1\pmod{\varphi(n)}$$ $e$と$\phi(n)$は互いに素である必要がある． ここで，$\varphi(n)$はオイラー関数である．この値は$n$が異なる素数$p$と$q$の積である場合，次のように求められる． $$\varphi(n)=(p-1)(q-1)$$ 公開鍵$(e,n)$と秘密鍵$(d,n)$を用いて，暗号化と復号化を行う． ここで，$m$は平文，$c$は暗号文である． 暗号化は，以下の式で行う． $$c\equiv m^e\pmod{n}$$ 復号化は，以下の式で行う． $$m\equiv c^d\pmod{n}$$

成り立つ理由

オイラーの$\varphi$関数は，$x$と互いに素な$n$について，次の性質がある． $$x^{\varphi(n)} \equiv 1 \pmod n$$ $ed\equiv 1 \pmod{\varphi(n)}$であるため，次のように復元できることがわかる． $$ c^d\equiv (m^e)^d\equiv m^{ed}\equiv m^{k\varphi(n)+1} \equiv m^{k\varphi(n)}m\equiv (m^{\varphi(n)})^k m \equiv 1^km\equiv m\pmod{n} $$

なお，$k$は$ed=k\varphi(n)+1$が成り立つ整数である．

一般化(Multi-prime RSA)

$n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$とする．オイラーの$\varphi$関数は，次のように計算できる． $$\varphi(n)=\prod_{i=1}^k(p_i-1)p_i^{e_i-1}$$

プログラム上での求め方

$p,q$

ミラー–ラビン素数判定法を使うことで巨大な素数が生成できる．

$e$

$e=65537$などの素数を用いることが多い．

$d$

$ed\equiv 1\pmod{\varphi(n)}$を満たすような$d$を求める． これは，拡張ユークリッドの互除法を用いて求めることができる．

$c,m$

$c\equiv m^e\pmod{n}$や$m\equiv c^d\pmod{n}$を計算する． このとき，$m^e$や$c^d$は巨大な数になるため，Naiveな計算では間に合わない． 繰り返し二乗法(バイナリ法，ダブリングなど)を用いることで，$O(\log e),O(\log d)$で計算できる．

実装例

from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes

def gen_key():
    p = getPrime(1024)
    q = getPrime(1024)
    n = p*q
    phi = (p-1)*(q-1)
    e = 65537
    d = inverse(e,phi)
    return (e,n),(d,n)

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

def decrypt(c,d,n):
    return pow(c,d,n)

if __name__ == "__main__":
    (e,n),(d,n) = gen_key()
    m = bytes_to_long(b"Hello World")
    c = encrypt(m,e,n)
    print(long_to_bytes(decrypt(c,d,n)))

Python

Pythonの罠

listのコピー

a = [1,2,3]
b = a
b[0] = 0
print(a)

[0,2,3]

なんと，bの代入元であるaも変わってしまった．

これを回避するために，aのcopyを作る必要がある．

a = [1,2,3]
b = a.copy()
b[0] = 0
print(a)

[1,2,3]

割り算の演算子

a = 5
b = 2
print(a/b)
print(a//b)

2.5
2

/は小数点以下を含む割り算を行う．//は小数点以下を切り捨てた割り算を行う． /を大きな整数で使おうとすると正しい結果が得られない．

次のプログラムでは，$9999\cdots9999$を$3$で割った値，すなわち$3333\cdots3333$を求めたい．

a = 999999999999999999999999999999999999999999999999999999999999999999999999999999999999
b = 3
print(a/b)
print('{:.1000g}'.format(a/b)) #eを使わない表示にする．
print(a//b)

3.333333333333333e+83
333333333333333316642274409837779174589735593005847147516488057690807469867494539264
333333333333333333333333333333333333333333333333333333333333333333333333333333333333

演算子/を使った場合，でたらめな値が得られたことがわかる． //を使うと，正しい値が得られる．

小数を扱う関数

sqrt関数，pow関数などは小数で計算をする．

a = 10
b = pow(a,100)
print('{:.10000g}'.format(b))

x = 10000000000000000000000000000000000
a = x*x
b = sqrt(a)
print('{:.10000g}'.format(b))

10000000000000000159028911097599180468360808563945281389781327557747838772170381060813469985856815104
9999999999999999455752309870428160

わけのわからない値が得られる． 基本的に標準ライブラリの関数は信用してはいけない．PyCryptodome，sagemath，NumPyなどのライブラリを使うか，自分で実装する必要がある．

再帰関数の深さ

def f(n):
    if n==0:
        return 0
    return f(n-1)+1
print(f(100000))

RecursionError: maximum recursion depth exceeded in comparison

再帰関数の深さ(recursion depth)の最大値は，デフォルトでは$1000$である． これを変更するには，sysモジュールを使う．

import sys
sys.setrecursionlimit(1000000)

Miller–Rabin primality test

素数判定アルゴリズム．

import random

def MillerRabinPrimalityTest(n, k=20):
    s = 0
    d = n-1
    if n == 2:
        return True
    if n == 1 or n % 2 == 0:
        return False
    # 奇数dと整数sでn-1=d*2^sを満たすようにする
    while d % 2 == 0:
        s += 1
        d //= 2
    # k回の試行を行う
    for _ in range(k):
        a = random.randint(1, n-1)
        x = pow(a, d, n)
        # x = 1 or -1
        if x != 1: 
            composite = True
            y = d
            for _ in range(s):
                x = pow(a, y, n)
                y *= 2
                if x == n-1:
                    composite = False
                    break
            if composite:
                return False
    return True

getPrime

ミラーラビン素数判定を用いて、指定されたビット数の素数を生成する。

depends

def getPrime(n):
    while True:
        p = random.randint(2<<(n-2), 2<<(n-1))
        if MillerRabinPrimalityTest(p):
            return p

2022

2022

CakeCTF2021 together as one

問題概要

問題リンクファイル

素数$p,q,r$があり，$e\equiv65537$，フラグを$m$とし，次の値が与えられる． $$ n \equiv pqr \\ c \equiv m^e \\ x \equiv (p+q)^r \mod n \\ y \equiv (p+qr)^r \mod n $$

解法

二項定理により，$x$の値について次の計算ができる． $n=pqr$であり，$0<x<r$のとき${}_r\textrm{C}_x$が$r$の倍数であることを使っている． $$ \begin{align} x &\equiv (p+q)^r \mod n \\ &\equiv {}_r\textrm{C}_0 p^rq^0 + {}_r\textrm{C}_1 p^{r-1}q^1 + {}_r \textrm{C}_2 p^{r-2}q^2 + \cdots + {}_r\textrm{C}_{r-1} p^1q^{r-1} + {}_r\textrm{C}_{r} p^0q^{r-1} \mod n \\ &\equiv p^r + q^r \mod n \end{align} $$ $y$も同様に，展開をして$n$の倍数になる項を削除する． $$ \begin{align} y &\equiv (p+qr)^r \mod n \\ &\equiv p^r + q^rr^r \mod n \end{align} $$ 法$q$の世界で考える．すると， $$ \begin{align} x &\equiv p^r \mod q\\ y &\equiv p^r \mod q \end{align} $$ よって，整数$k$を用いると次が成り立つ $$ \begin{align} x &\equiv y \mod q\\ x &\equiv y + kq \\ x - y &\equiv kq \end{align} $$

$x-y$は$q$の倍数であり，$n$も素因数$q$を持っているため，$q\equiv\textrm{GCD}(x-y,n)$である．

次に，$x$と$y$を法$r$で考える．フェルマーの小定理により，$p^r \mod r\equiv p$が成り立つ(他の変数も同様)．

$$ \begin{align} x \equiv p + q \mod r\\ y \equiv p \mod r \end{align} $$ $q$が邪魔だが既知であるため，$r$について合同な式ができる． $$ \begin{align} x - q \equiv y \mod r\\ \end{align} $$ よって，$r\equiv\textrm{GCD}(x-q-y,n/q)$である．

from Crypto.Util.number import long_to_bytes,inverse

def GCD(a,b):
    if a%b==0:
        return b
    return GCD(b,a%b)

def LCM(a,b):
    return a//GCD(a,b)*b


n = # 長いので省略
c = 
x = 
y = 
e = 0x10001

q = GCD((x-y)%n,n)
r = GCD((x-y-q)%n,n)//q
p = n//r//q

print(f'{p = :#}')
print(f'{q = :#}')
print(f'{r = :#}')
assert p*q*r == n

phi = (p-1)*(q-1)*(r-1)
d = pow(e,-1,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

CakeCTF{This_chall_is_inspired_by_this_music__Check_out!__https://www.youtube.com/watch?v=vLadkYLi8YE_cf49dcb6a31f}

コメント

$q$を見つけた後がわかりませんでした． こういう式変形して最大公約数とって$p,q$あぶり出すタイプの問題，法を$p$とか$q$して合同な数を見つけようとすると見えやすくなるのかもしれない．

CakeCTF2021 discrete_log

概要

問題リンク

フラグの文字列の$i$文字目の文字コードを$m_i$として $$ c_i \equiv g^{rm_i} \mod p $$ の各$c_i$が与えられる．なお，素数$p$と正の整数$g$は与えられている．正の整数$r$は与えられない．

解法

$g^r$の値がわかれば，$m_i$を全探索(多くて256通り)すればいい． フラグ形式より，$m_0$がord("C")であることがわかるので，$d\equiv m_0^{-1}\mod \phi(p)$として $(g^{rm_0})^d \equiv g^r \mod p$と計算することで$g^r$が求める．

from Crypto.Util.number import *

def GCD(a,b):
    if a%b==0:
        return b
    return GCD(b,a%b)

def LCM(a,b):
    return a//GCD(a,b)*b

def extGCD(a, b):
    if b:
        d, y, x = extGCD(b, a % b)
        y -= (a // b)*x
        return d, x, y
    return a, 1, 0

p = # 長いので省略
q = 
cs = 

d = inverse(ord("C"),p-1)
gr = pow(cs[0],d,p)
flag = ""
for c in cs:
    for i in range(1<<8):
        if c==pow(gr,i,p):
            flag += chr(i)
print(flag)

CakeCTF{ba37a0f409ef3ec23a6cffbc474a1cef}

コメント

1文字ずつ暗号化するのは危険

picoCTF2022 Sequences

概要

$$ \begin{align} a_0 &= 1 \\ a_1 &= 2 \\ a_2 &= 3 \\ a_3 &= 4 \\ a_i &= 21a_{i-1} + 301a_{i-2} - 9549_{i-3} + 55692 a_{i-4} \quad (i>4) \end{align} $$ で定義される数列で，$a_{20000000}$を$10^{10000}$で割った余りを求める．

解法

数列は，$4$項間の線形漸化式である．線形漸化式の$n$項目は高速に求められる(参考)． 次のように行列で表し，ダブリングによって累乗を高速に計算する． $$ \begin{pmatrix} 21 & 301 & -9549 & 55692 \\ 1 &0&0&0\\ 0&1&0&0\\ 0&0&1&0\\ \end{pmatrix} ^{n-3} \begin{pmatrix} a_3\\ a_2\\ a_1\\ a_0 \end{pmatrix} = \begin{pmatrix} a_n\\ a_{n-1}\\ a_{n-2}\\ a_{n-3} \end{pmatrix} $$

import math
import hashlib
import sys
from tqdm import tqdm
import functools

ITERS = int(2e7)
VERIF_KEY = "96cc5f3b460732b442814fd33cf8537c"
ENCRYPTED_FLAG = bytes.fromhex("42cbbce1487b443de1acf4834baed794f4bbd0dfe08b5f3b248ef7c32b")

def mat_mul(a, b) :
    I, J, K = len(a), len(b[0]), len(b)
    c = [[0] * J for _ in range(I)]
    for i in range(I) :
        for j in range(J) :
            for k in range(K) :
                c[i][j] += a[i][k] * b[k][j]
            c[i][j] %= 10**10000
    return c


def mat_pow(x, n):
    y = [[0] * len(x) for _ in range(len(x))]

    for i in range(len(x)):
        y[i][i] = 1

    while n > 0:
        if n & 1:
            y = mat_mul(x, y)
        x = mat_mul(x, x)
        n >>= 1

    return y


d0 = 0
ret = [[4], [3], [2],[1]]
mat = [[21,301,-9549,55692], [1, 0, 0, 0], [0, 1, 0, 0],[0,0,1,0]]
#ret = mat_mul(mat_pow(mat, ITERS), ret)
#ret = [[1],[1]]
#mat = [[1,1], [1,0]]
ret = mat_mul(mat_pow(mat, ITRES), ret)
print(ret)


# Decrypt the flag
def decrypt_flag(sol):
    sol = sol % (10**10000)
    sol = str(sol)
    sol_md5 = hashlib.md5(sol.encode()).hexdigest()

    if sol_md5 != VERIF_KEY:
        print("Incorrect solution")
        sys.exit(1)

    key = hashlib.sha256(sol.encode()).digest()
    flag = bytearray([char ^ key[i] for i, char in enumerate(ENCRYPTED_FLAG)]).decode()

    print(flag)

if __name__ == "__main__":
    sol = A
    decrypt_flag(sol)

コメント

競プロだと基本ですね

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)))

コメント

めっちゃ数論

CakeCTF2022 frozen cake

問題

問題ファイル 素数$p,q$と平文$m$，$n=pq$から次の$a,b,c$の値が与えられる．$n$の値も与えられる． $$ \begin{align} a &\equiv m^p \mod n \\ b &\equiv m^q \mod n \\ c &\equiv m^n \mod n \end{align} $$

解法

$p$と$q$は$\phi(n)$と互いに素ではないため，$a,b$から$m$を復元するのは難しそう． $c$を変形してみる．

$$ n = (p-1)(q-1) + p+q-1 = \phi(n) + p+q-1 \\ c \equiv m^n \equiv m^{\phi(n) +p+q-1} \equiv m^{p+q-1} \equiv m^p m^q m^{-1}\pmod n $$

ここで，$m^p,m^q\pmod n$の値はわかっているので， $$ c a^{-1} b^{-1} \equiv m^{-1} \pmod n $$ これで$m^{-1}\mod n$が求まり，これの逆数がフラグである．

from Crypto.Util.number import inverse , long_to_bytes

n = 101205131618457490641888226172378900782027938652382007193297646066245321085334424928920128567827889452079884571045344711457176257019858157287424646000972526730522884040459357134430948940886663606586037466289300864147185085616790054121654786459639161527509024925015109654917697542322418538800304501255357308131
a = 38686943509950033726712042913718602015746270494794620817845630744834821038141855935687477445507431250618882887343417719366326751444481151632966047740583539454488232216388308299503129892656814962238386222995387787074530151173515835774172341113153924268653274210010830431617266231895651198976989796620254642528
b = 83977895709438322981595417453453058400465353471362634652936475655371158094363869813512319678334779139681172477729044378942906546785697439730712057649619691929500952253818768414839548038664187232924265128952392200845425064991075296143440829148415481807496095010301335416711112897000382336725454278461965303477
c = 21459707600930866066419234194792759634183685313775248277484460333960658047171300820279668556014320938220170794027117386852057041210320434076253459389230704653466300429747719579911728990434338588576613885658479123772761552010662234507298817973164062457755456249314287213795660922615911433075228241429771610549

ainv = inverse(a,n)
binv = inverse(b,n)
minv = (c * ainv * binv)%n
print(long_to_bytes(inverse(minv,n)))


CakeCTF{oh_you_got_a_tepid_cake_sorry}

コメント

CakeCTF 2022 開催記より引用(リンク)．

warmupでRSAの乗法準同型性に関する知識とフェルマーの小定理を要求していてなかなかハードですね。とはいえCTFの暗号分野では基礎となるような数学の知識ですので、CTFの問題としてはこのくらいは出題したいところです。これが解けたらある程度のCryptoに関する実力がありますと言って良いんじゃないかと思います。

ある程度のCryptoに関する実力があるそうです．暗号er名乗っていいですか！

CakeCTF2022 brand new crypto

問題

問題リンク

素数$p,q$があり，$n=pq$．$\phi=(p-1)(q-1)$として$0$以上$\phi$以下の整数$a,s$があり，

$$ \begin{align} \phi &= (p-1)(q-1) \\ b &= \phi + 1 -a \\ t &= -sa b^{-1} \pmod \phi \end{align} $$

$b$と$\phi$は互いに素であることが保証される． $0$以上$n$以下の整数$r$を使って次のように暗号化される $$ c_1 \equiv mr^s \pmod n\\ c_2 \equiv mr^t \pmod n $$ 復元は次のようにできる $$ m = c_1 ^a c_2^b \pmod n $$

その他色々な条件があるが，この暗号が破綻しないために例外を考えなくていいということなんだろう．

そして，各フラグの$i$文字目の文字コード$m_i$についてこの暗号化をした値$c_1,c_2$が与えられる．また，全体で$a,b,s,t,p,q$の値は固定．$r$だけランダム． 与えられる値は，各暗号化された値と$s,t,n$．

考えたこと

なんかよくわからないのでまず復元で何が起こっているかを見ておく． 確かに， $$ m\equiv c_1 ^a c_2 ^b \equiv (mr^s)^a (mr^t)^b \equiv m^a r^{sa} m^b r^{-sab^{-1}b} \equiv m^{ab}r^{sa-sa} \equiv m^{ab} \equiv m^{\phi+1} \equiv m \pmod n $$ と成り立っている． なんとなく，$t$が$a,b$にから計算されているので，これをうまく使うんじゃないかと思う． あと，$m_i$がせいぜい256通りなので，それっぽい値がわかれば全探索が可能．

4時間後，次の方法が思いついた．

$$ (mr^s)^t (mr^t)^{-s} \equiv m^{t-s} r^{st-st} \equiv m^{t-s} \pmod n $$

これで，$m$を全探索して$m^{t-s}\pmod n$と一致するものを見つければ良い． $s$と$t$が具体的にどんな方法で出された値であるかを考える必要はなかったのだ．

from Crypto.Util.number import inverse , long_to_bytes

s,t,n = 長いので省略
cs = 

flag = ""
for c1,c2 in cs:
    mst = (pow(c1,t,n)*pow(pow(c2,s,n)%n,-1,n))%n
    print(mst)
    for m in range(256):
        if pow(m,t-s,n)==mst:
            print(chr(m))
            flag += chr(m)
print(flag)


CakeCTF{s0_anyway_tak3_car3_0f_0n3_byt3_p1aint3xt}

コメント

悩んだ割に結構解法がシンプルでした．こういうちょっと複雑になっただけで頭が堅くなってしまう！ $m$が同じで$e$が異なるRSAへの攻撃手法を思い出しました． 同じ数の異なる冪数があるときはこの道の解法を考えると良さそう．

waniCTF2021 sweet_curve

問題

問題ファイル ．次の有限体$\mathbb{F}_p$の楕円曲線上の点$P,Q$が与えられるので，$P+Q$の$x$を求めよという問題． $$ y^2 \equiv x^3 - x + 1 \pmod p $$

解法

これを解くsagemathのソースコードは次の通り．

from Crypto.Util.number import long_to_bytes

# Given:
# - An elliptic curve: y**2 = x**3 - x + 1 (mod p)
# - Two points: P(x_P, y_P) and Q(x_Q, y_Q)

# Find the point P+Q
# The flag is the x value of P+Q
# Don't forget to convert it into a string!
p = 0x89a4e2c7f834f5fbc6f2a314e373e3723de7df6283c5d97cbca509c61e02965b7ef96efce1d827bfdfa7f21d22803558bb549f9ea15dfe9f47d3976648c55feb
x_P = 0x1e1cba0e07c61cf88e9f23b9859093c33c26cf83bcfb6fe24d7559cd0ea86fb2f144ae643ac5edf6f04ef065dc7c2c18d88ae02843592d5e611029fefc0fece
y_P = 0x198420b30a4330f82380326895d0ac06a1859bc49d45cd4b08021b857d23d515163b9151fbaf7ae5f816d485d129d3b1c4630d1fb45c6790af551428a5c85667
x_Q = 0x7e32edfd7befd8df93d7b738d6a1c95e1cfd56b3a6ccc4a62e4e0ae9059b4903e71fccbe07d8d45c762b4a3ed5c9d1a2505043d033e58adb72191259b81bc47d
y_Q = 0x46016c676585feaf048fff9d5cbb45dbd598c6c4c81694e0881bf110b57012f0bac6eaf7376fee015c8cecba1fc92206ca346f7d72ee1d60f820091c85fa76b3

# y^2 + a1 xy + a3 y = x^3 + a2 x^2 + a4 x + a6
# [a4,a6]
E = EllipticCurve(GF(p), [-1,1])
P = E([x_P, y_P])
Q = E([x_Q, y_Q])
x = (P+Q)[0]
print(x)
print(long_to_bytes(int(x)))

sagemathにおける楕円曲線についてはこちらに載っている．

コメント

僕にとってsagemathのリファレンスはほとんど意味がわかりません．

InterKosenCTF2020 ciphertexts

問題

平文$m$，素数$p,q,r$があって，$n_1=pq$，$n_2=pqr$，素数$e_1$とその次に大きい素数$e_2$を用意． $$ \begin{align} c_1 &= m^{e_1} \pmod {pq} \\ c_2 &= m^{e_2} \pmod {pqr} \end{align} $$ $p,q,r$以外は与えられる．

解法

r = n2//n1
d=pow(e1,-1,r-1)
m=pow(c1,d,r)
print(long_to_bytes(m))

$r$がバレているので$\mod r$の世界で考えれば行けるんじゃないかと思ったがだめだった． では，$\mod pq$の世界ではどうだろうか．$c_2$を$\pmod {pq}$で考えて，$e_1x+e_2y=1$となるような$x,y$を見つけてくれば良い． $$ c_1^x c_2^y \equiv (m^{e_1})^x(m^{e_2})^y \equiv m^{e_1x+e_2y} \equiv m \pmod {pq} $$

x = -74571
y = 74570
print(e1*x+e2*y) # 1
m = (pow(c1,x,n1)*pow(c2,y,n1))%n1
print(long_to_bytes(m))

1
b'KosenCTF{HALDYN_D0M3}'

出てきた．

コメント

warmup問題として出たらしい．

CrewCTF2022 The HUGE e

問題

p = 127557933868274766492781168166651795645253551106939814103375361345423596703884421796150924794852741931334746816404778765897684777811408386179315837751682393250322682273488477810275794941270780027115435485813413822503016999058941190903932883823
e1 = 219560036291700924162367491740680392841
e2 = 325829142086458078752836113369745585569
e3 = 237262361171684477270779152881433264701
c = 962976093858853504877937799237367527464560456536071770645193845048591657714868645727169308285896910567283470660044952959089092802768837038911347652160892917850466319249036343642773207046774240176141525105555149800395040339351956120433647613

のパラメータが与えられる．$c$は，$m$を次の式によって計算された値である． $$ c \equiv m^{e_1^{e_2^{e_3}}} \pmod p $$ また，$p$はとてもsmoothである．

解法

$e=e_1^{e_2^{e_3}}$として$d=e^1\mod \phi(p)$が求まれば良いわけだが，タイトルの通り$e$がとんでもなく大きな数になってしまうため，何か工夫が必要だ．

オイラーの定理(またはフェルマーの小定理)より，$e\equiv e_1^{e_2^{e^3}} \pmod {\phi(p)}$としてしまって良い．これで，$ e_1^{e_2^{e^3}}\pmod {p-1}$の値を求める問題になった． ここでさらに，$e_1^{e_2^{e^3}}=e_1^{e_4}$とおくと，$e_4 \equiv e_2^{e_3} \pmod {\phi(p-1)}$としてしまって良い．これなら簡単に求められる．$\phi(p-1)$の値だが，$p-1$がsmoothであることを使えば簡単に求められる．

def factor(N):
    f = [] # p-1の素因数分解
    i = 2
    N = p-1
    while i*i<=N:
        if N%i==0:
            f.append(i)
            N = N//i
        else:
            i+=1
    f.append(N)
    return f

p = 127557933868274766492781168166651795645253551106939814103375361345423596703884421796150924794852741931334746816404778765897684777811408386179315837751682393250322682273488477810275794941270780027115435485813413822503016999058941190903932883823
e1 = 219560036291700924162367491740680392841
e2 = 325829142086458078752836113369745585569
e3 = 237262361171684477270779152881433264701
c = 962976093858853504877937799237367527464560456536071770645193845048591657714868645727169308285896910567283470660044952959089092802768837038911347652160892917850466319249036343642773207046774240176141525105555149800395040339351956120433647613
phi = p-1
phiphi = 1
fs = factor(phi)
for f in fs:
    phiphi *= f-1
e4 = pow(e2,e3,phiphi)
e = pow(e1,e4,phi)
d = pow(e,-1,phi)
m = pow(c,d,p)
print(long_to_bytes(m))

crew{7hi5_1s_4_5ma11er_numb3r_7han_7h3_Gr4ham_numb3r}

コメント

フェルマーの小定理やオイラー関数を正しく使えるかを問う問題だった．競プロでもABC228-Eみたいなフェルマーの小定理をしっかり使う問題が出ています．

11月

easy

easyではわざわざ1ページを作るほどでもないシンプルな問題や簡単な問題を解く．

Archived Challenges - July 2021 smth here

:4E7L6oD*049p==b?8b=D07EHN

色々試すとROT47だとわかる． ictf{e@sY_chAll3ng3ls_ftw}

Archived Challenges - August 2021 I can't hear you!

100011110010101100010101001011011100100010111110100011101101000110010010100101110010001110011100100110011101011100101110010110010100011001010110100101010011011011011111001110011100001000011110100101110100001010100111100101011010101011011100001101001011101101110011100011110001011010010100010101110010000110000011010110110001100000100111100011101110100100101100001110010011101110110101010110011001010101001100001011101010100101100111001111101101010001011101001101101011010010010001100110011010110001010101010101011011100111100010100101111100010111001101010011010110011011011111100110101110010101010010001101101100110000001000010011110100010111001101010110010101011101111011000111011001110111111001010110110010011011011110001011101100101010001110001101011111100010101110010111110100001011001011100011110011101011001110

repetition codeというものが存在する．

from Crypto.Util.number import *
s = (omit)
t = ""

for i in range(0,len(s),3):
    a = int(s[i:i+3],2)
    if a == 0 or a==1 or a==2 or a==4:
        t += "0"
    else:
        t += "1"


n = int(t,2)
print(long_to_bytes(n))

ImaginaryCTF October 2022 RSA-ECB

問題

フラグの各1文字ずつ，文字コードがRSAで暗号化されている．パラメータは$n,e$のみ既知．

#!/usr/bin/env python3

from Crypto.Util.number import *

p = getPrime(512)
q = getPrime(512)
n = p*q
e = 65537

m = open("flag.txt", 'rb').read()

out = open('output', 'wb')

out.write(long_to_bytes(n))

for c in m:
    out.write(long_to_bytes(pow(c, e, n)))

解法

考えられる候補の少ないところをブルートフォースするタイプの問題． 各1文字は8ビットなので簡単に全探索できる．今回の場合は$n$と各$c_i$がバイナリデータとしてつなげて出力されているので，適切なビット数を区切って取得する必要がある．

from Crypto.Util.number import *

f = open("./output", "rb").read()

l = 1024//8
n = bytes_to_long(f[:l])
cs = []
for i in range(l,len(f),l):
    cs.append(bytes_to_long(f[i:i+l]))

flag = ""
e = 0x10001
print(f"n = {n}")

for c in cs:
    for m in range(1<<8):
        if pow(m,e,n) == c:
            flag += chr(m)
            break

print(flag)

# ictf{dont_mind_me_I'm_just_brute_forcing_rsa}

コメント

よくある一文字ずつブルートフォースするタイプの問題かと思ったら，バイナリに連結されて出力されたので各パラメータのビット数をちゃんと考える必要があった．

ImaginaryCTF October 2022 RSA-CBC

問題

$2048$ビットの$n$を使って，フラグの一文字ずつ$m_i$として次を実行する．$vi$の初期値は256ビットのランダムな値．

  1. $c_i=(vi+m_i)^e$を計算する．
  2. $vi$に$c_i$を代入する．

各$c_i$の値の値と$vi$の初期値が与えられるので，フラグを復元する．

from Crypto.Util.number import getPrime
from secrets import randbelow


class RSACBC:
    def __init__(self, size):
        self.blk = 1
        self.len = size // 8
        self.n = getPrime(size // 2) * getPrime(size // 2)
        self.e = 65537

    def encrypt(self, msg: bytes) -> bytes:
        iv = randbelow(self.n)
        iv0 = iv
        ct = b""
        for i in range(0, len(msg), self.blk):
            m = int.from_bytes(msg[i : i + self.blk], "big")
            c = pow(iv + m, self.e, self.n)
            ct += c.to_bytes(self.len, "big")
            iv = c
        return iv0.to_bytes(self.len, "big"), ct


flag = open("flag.txt", "rb").read().strip()
assert flag.startswith(b"ictf{")
assert flag.endswith(b"}")
flag = flag[5:-1]
cipher = RSACBC(2048)
print(f"n = {cipher.n}")

iv, ct = cipher.encrypt(flag)
print(f"{iv = }")
print(f"{ct = }")

解法

$1$文字ずつ$c_i$をブルートフォースするタイプの問題．

from Crypto.Util.number import *

flag = ""
iv = bytes_to_long(iv)
d = 2048 // 8
for i in range(0,len(ct),d):
    c = bytes_to_long(ct[i:i+d])
    e = 65537
    for m in range(256):
        if pow(iv+m,e,n) == c:
            iv = c
            flag += chr(m)
            break
    
print(flag)

コメント

ecbモードの問題とほぼ同じ解法．RSAはあんまり関係ない．

ImaginaryCTF October 2022 Luggage

問題

ランダムにフラグのビット数と同じ長さのpubがランダム生成され，フラグのi番目のビットが1だったところに対応するpub[i]が足し算されてcとなる．cとpubが与えられる．要するにナップザック問題．

from Crypto.Util.number import bytes_to_long, getPrime
from Crypto.Random.random import getrandbits

flag = b"ictf{xxxxxxxxxxxxxxxxxxxxxxx}"
flag = bytes_to_long(flag)

p = getPrime(512)
k = [getrandbits(n*2+3) for n in range(flag.bit_length())]
assert all(n < p for n in k)

e = getrandbits(1024)
pub = [(m * e) % p for m in k]
print(pub)

c = []
for n in range(flag.bit_length()):
  c.append((flag % 2) * pub[n])
  flag //= 2

print(f"{pub}")
print(f"{sum(c)}")

解法

ナップザック問題を解くにはLLLを使う．

LLLで解くナップザック問題の簡単な説明

格子の作り方は次の通り．

$$ \begin{pmatrix} 1 & 0 & 0 & \cdots & 0 & 0 & 0 & p_1\\ 0 & 1 & 0 & \cdots & 0 & 0 & 0 & p_2 \\ 0 & 0 & 1 & \cdots & 0 & 0 & 0 & p_3 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & 0 & 0 & p_{n-2} \\ 0 & 0 & 0 & \cdots & 0 & 1 & 0 & p_{n-1}\\ 0 & 0 & 0 & \cdots & 0 & 0 & 1 & p_{n}\\ 0 & 0 & 0 & \cdots & 0 & 0 & 0 & -c\\ \end{pmatrix} $$

例えば，$p=(102,103,104)$からいくつか選んで$c=206$を作る組み合わせを知りたい場合，

$$ \begin{pmatrix} 1 & 0 & 0 & 102 \\ 0 & 1 & 0 & 103 \\ 0 & 0 & 1 & 104 \\ 0 & 0 & 0 & -206 \\ \end{pmatrix} $$

をLLLにかける．

sage: X = Matrix(ZZ,4,4)                 
sage: X[0,0]=1                           
sage: X[1,1]=1                           
sage: X[2,2]=1                           
sage: X[0,3]=102                         
sage: X[1,3]=103                         
sage: X[1,3]=104                         
sage: X[3,3]=-206 
sage: X
[   1    0    0  102]
[   0    1    0  103]
[   0    0    1  104]
[   0    0    0 -206]
sage: X.LLL()
[  1   0   1   0]
[ -1   1   0   1]
[  0  -1   1   1]
[ 35   0 -34  34]

LLLは各行をそれぞれベクトルと見たとき，それらのベクトルの適当な整数倍したものがゼロベクトルに近いように計算してくれる． LLLにかける前の行列で，一番右の列以外の$1,0$は，どのベクトルがいくつ足し算されたかを表すために用意されている． この場合，結果の$1$行目がもとの行列の$1,3,4$行目のベクトルを足し算したものになっている．すなわち，$102+104-206=0$であることがわかる．

cが計算されるときにflagの下位ビットから処理されていることに注意して実装する．なお，出力されたベクトルの最終列は無視するべきだが，$0$であるはずなので反転したときに結局関係なくなる(桁の先頭に$0$が入るだけ)ので問題ない．

from Crypto.Util.number import *

n = len(pub)
X = Matrix(ZZ, n+1, n+1)

for i,p in enumerate(pub):
    X[i,i] = 1
    X[i,n] = p

X[n,n] = -c

out = Matrix(X).LLL()

for row in out:
    if all(n in [0, 1] for n in row):
        print(row)
        flag = int("".join(str(n) for n in list(row[::-1])), 2)
        print(long_to_bytes(flag)) #b'ictf{sUpeRinCrEasIng_wH4T???}'

コメント

LLLの結果の反転を忘れて困惑した．

ImaginaryCTF October 2022 Rrrrrrandomness

問題

線形合同法によって乱数列が生成される． 生成に使われるパラメータの$a,b,m$の和を求める問題． ただし，線形合同法とは，次の漸化式と$x_0$によって計算される値である．

$$ x_{i+1} = ax_i + b \pmod m $$

ただし，rand関数にはちょっと小細工が仕込まれていて，$x_i$の次に$x_{i+1}$が生成されるとは限らずに，ランダムに$1$個から$256$個の値がスキップされることがある．

from Crypto.Util.number import getPrime
from secrets import randbelow
from hashlib import sha256

m = getPrime(20)
a = randbelow(m)
b = randbelow(m)
x = randbelow(m)

def rand():
    def rand():
        global a, b, m, x
        x = (a*x + b) % m
        return x
    while 1:
        for _ in range(rand() & 0xFF):
            rand()
        for _ in range(rand() & 0x8):
            yield rand()

def xor(x, y):
    return bytes(a ^ b for a, b in zip(x, y))

rand = rand()
rand = [next(rand) for _ in range(20)]
print('rand =', rand)

print('ct =', xor(b'ictf{REDACTED}', sha256((m + a + b).to_bytes(6, 'big')).digest()))

解説

線形合同法は，連続した乱数列から各パラメータを求めることができる． 次のような連続した乱数列が与えられたとする． $$ \begin{align} x_1 &= ax_0 + b \pmod m \\ x_2 &= ax_1 + b \pmod m \\ x_3 &= ax_2 + b \pmod m \\ x_4 &= ax_3 + b \pmod m \\ x_5 &= ax_4 + b \pmod m \\ x_6 &= ax_5 + b \pmod m \end{align} $$ $b$のみがわからない場合は，次のようにして求めることができる． $$ \begin{align} x_1 &= ax_0 + b \pmod m \\ b &= x_1 - ax_0 \pmod m \end{align} $$ $a,b$がわからない場合は，次のように逆数を用いてまず$a$を求めることができる(残りの$b$を求める方法はしました)． $$ \begin{align} x_2 - x_1 &= ax_1 - ax_0 \pmod m \\ x_2 - x_1 &= a(x_1 - x_0) \pmod m \\ a &= (x_2 - x_1)(x_1 - x_0)^{-1} \pmod m \end{align} $$

$a,b,m$全てわからない場合，次のような$T_0,T_1,T_2,\cdots$を用意する．

$$ \begin{align} T_0 &= x_1 - x_0 \\ T_1 &= x_2 - x_1 = A(x_1-x_0) = A T_0 \pmod m \\ T_2 &= x_3 - x_2 = A(x_2-x_1) = A T_1 \pmod m \\ T_0T_2 - T_1^2 &= A^2T_0^2 - A^2T_0^2 = 0 \pmod m \\ \end{align} $$

ここで，$T_0T_2 - T_1^2 = 0 \pmod m$であることから，添字をずらすと次が成り立つ．

$$ \begin{align} T_1T_3 - T_2^2 &= 0 \pmod m \\ T_2T_4 - T_3^2 &= 0 \pmod m \\ T_3T_5 - T_4^2 &= 0 \pmod m \\ \vdots \\ T_{n-1}T_{n+2} - T_n^2 &= 0 \pmod m \end{align} $$ こられの数は全て$m$で割ったあまりが$0$であるため，これらの数の最大公約数を求めることができれば，それが$m$である可能性1がある．

1

あくまで可能性であり，いずれも同じ数になってしまうことや，最大公約数が$m$の倍数になってしまうことがある．最大公約数を取るときに使う数が多いければ多いほど$m$が求められる確率が高くなる．

以上のことにより，次のスクリプトによって$a,b,m$を求めることができる．

from Crypto.Util.number import *
from hashlib import sha256

def linear_random_crack(rands):
    t = [rands[i+1]-rands[i]  for i in range(len(rands)-1) ]
    s = [(t[i+2]*t[i]-t[i+1]*t[i+1]) for i in range(len(t)-2) ]
    m = 0
    for a in s:
        m = GCD(m,a)
    a = ((t[2]-t[1]) * inverse(t[1]-t[0],m))%m
    b = (rands[1] - a*rands[0])%m
    return a,b,m

def xor(x, y):
    return bytes(a ^ b for a, b in zip(x, y))


ct = b'\x1b\xc3\xc1O\x7f]q\xb98\x8d\xb8\xf5\xec\x82\x8cg\xd0\xed\xbb\t<G\xe6\xde\xf7\xb3\x81\xe05'
r = [830740, 252348, 146586, 407799, 782171, 349709, 751088, 904092, 390201, 909918, 347514, 89924, 7112, 751221, 26415, 299902, 438982, 787802, 1081, 814607]
l = 8 # 必要に応じて小さくする
for i in range(len(r)-l):
    a,b,m = linear_random_crack(r[i:i+l])
    print(a,b,m)
    print(xor(ct,sha256((a+b+m).to_bytes(6, 'big')).digest()))

出力は次のようになる．

963459 253883 977407
b'ictf{n07_50_r4nd0m_4ft3r_4ll}'
0 0 1
b'\x03\xa2\xe9\xf0\xf5\x10\x11Rs\xdc\xa8\xdf\x0e G\r\xdbm\xba\x10K\x1f\xc2^\xce\xe9\xc4\xa4a'
0 0 1
b'\x03\xa2\xe9\xf0\xf5\x10\x11Rs\xdc\xa8\xdf\x0e G\r\xdbm\xba\x10K\x1f\xc2^\xce\xe9\xc4\xa4a'
0 0 1
b'\x03\xa2\xe9\xf0\xf5\x10\x11Rs\xdc\xa8\xdf\x0e G\r\xdbm\xba\x10K\x1f\xc2^\xce\xe9\xc4\xa4a'
0 0 1
b'\x03\xa2\xe9\xf0\xf5\x10\x11Rs\xdc\xa8\xdf\x0e G\r\xdbm\xba\x10K\x1f\xc2^\xce\xe9\xc4\xa4a'
0 0 1
b'\x03\xa2\xe9\xf0\xf5\x10\x11Rs\xdc\xa8\xdf\x0e G\r\xdbm\xba\x10K\x1f\xc2^\xce\xe9\xc4\xa4a'
0 0 1
b'\x03\xa2\xe9\xf0\xf5\x10\x11Rs\xdc\xa8\xdf\x0e G\r\xdbm\xba\x10K\x1f\xc2^\xce\xe9\xc4\xa4a'
0 0 1
b'\x03\xa2\xe9\xf0\xf5\x10\x11Rs\xdc\xa8\xdf\x0e G\r\xdbm\xba\x10K\x1f\xc2^\xce\xe9\xc4\xa4a'
963459 253883 977407
b'ictf{n07_50_r4nd0m_4ft3r_4ll}'
0 0 1
b'\x03\xa2\xe9\xf0\xf5\x10\x11Rs\xdc\xa8\xdf\x0e G\r\xdbm\xba\x10K\x1f\xc2^\xce\xe9\xc4\xa4a'
0 0 1
b'\x03\xa2\xe9\xf0\xf5\x10\x11Rs\xdc\xa8\xdf\x0e G\r\xdbm\xba\x10K\x1f\xc2^\xce\xe9\xc4\xa4a'
0 0 1
b'\x03\xa2\xe9\xf0\xf5\x10\x11Rs\xdc\xa8\xdf\x0e G\r\xdbm\xba\x10K\x1f\xc2^\xce\xe9\xc4\xa4a'

$a=963459,b=253883,m=977407$だとわかり，フラグictf{n07_50_r4nd0m_4ft3r_4ll}が得られる．

コメント

yieldを知らなかった．

ImaginaryCTF October 2022 More pale

問題

$N$と互いに素な$g,r$とフラグ$f$を使って$c$が計算される． $$ c = g^f\times r^N \pmod{N^2} $$

ただし，$N$は$32$ビット程度の素数を$32$個掛け算したものである(簡単のため，それぞれの素数は異なると考える)．

$$ N = \prod^{32}_{i=1} p_i \quad (p_iは素数) $$

解答

$r^N$が邪魔なのでどうにかして消したい． $\pmod{N^2}$で$1$にするには，$\phi(N^2)$乗する必要がある．$\phi(N^2)$を計算してみると，$N$が出てくる．

$$ \begin{align} \phi(N^2) &= \prod^{32}_{i=1} (p_i^2 - p_i) \\ &= \prod^{32}_{i=1} p_i(p_i-1) \\ &= \prod^{32}_{i=1} p_i \prod^{32}_{i=1} (p_i -1) \\ &= N \cdot \phi(N) \end{align} $$ そのまま$c$を$\phi(N^2)$乗すると$1$になってしまうが，既に$r$の$N$乗がかかっていることに注目すると，

$$ \begin{align} c^{\phi(N)} &= g^{f\phi(N)} r^{N\phi(N)} \pmod {N^2} \\ &= g^{f\phi(N)} r^{\phi(N^2)} \pmod {N^2} \\ &= g^{f\phi(N)} \pmod {N^2} \end{align} $$

これで，あとは$f\phi(N)$が求められれば良いが，これは$N^2$が小さな素数の積であることから，Pohlig–Hellman法が使える．

以下sageでの実装

from Crypto.Util.number import *
from math import prod, gcd

N = 11426418812422762280036571700606763567947231773425157536629183225870745966201878199993626829615844927248091186921905998387334803393170756953004161976126607998422555566085789763646344981574364094148009230033109930017512774396115010409334288433850791978891238028784308896039614097042863945347168542666985383
g = 102370043738570361147512561430113690669375642568113520628837722692535092928991996894608072640673225251693957175347411184948751047776938223584014537703671208333116611432564769157326548350590167502807755716922970968951558696873031064519102939250266955847456094728415069300661910400192469539174495731756070447257875542560705682612568014282820199452851866020583046932239921789544226454615507571093721529079064029065323857243515917042869595396534609090834939823155439780919449771486541020286445222568415793241204876414692960607993360820654693596638939971884431900128125455066876042896836557800131056640691313737106
c = 103068079671149839873789585083110486503075572741609832823748309905209629934629965848822090939508870383106139073177857845426077799194203506965719179522047046491489575280275678232439148170329359273033661524521427411191787421596981639709353868254044119073231599736765796677163779301047698718070665219409437641669086148533724636988276093326307749151410207387960521848243363050042170628112380019384839142543642612905997234757798225958950399201463485580893790906185150849471016251892565658403504413779544907210377992966457602587448233119477078937422459927927859270682518316711143908453374720529830188577849652582868

ps = factor(N)
phi = 1
phi2 = 1
for p,e in ps:
    phi *= p - 1
    phi2 *= p**2 - p


gf = pow(c,phi,N*N)
print(gf)
f = discrete_log(gf,Mod(g,N*N))
f = f//phi
print(long_to_bytes(f))

コメント

楽しい