Upsolving log

암호학 문제에 대한 감이 많이 죽은 것 같아서 시간 날 때마다 예전의 문제들 업솔빙해보고, 기록을 남겨놓고자 한다. 기록용이기에 일반적인 롸업 형식보다는 뭘 배웠는지 혹은 간단한 풀이를 계속해서 업데이트할 것이다. (맘대로 쓰겠다는 뜻)


풀어볼 것들:
https://github.com/maple3142/My-CTF-Challenges
https://github.com/pcw109550/my-ctf-challenges
https://github.com/sajjadium/ctf-archives/tree/main/ctfs/HITCON/

magicRSA

chall

magic이 주어진 상황

neo_rsa

chall

d가 p이고 e가 안주어짐, flag와 sha256(flag)에 대한 암호문 2개 주어진 상황

m2는 256비트이고 $c2 - m2 = 0 \ (mod \ p)$ 이므로 coppersmith로 m2 알아내서 소인수분해 가능

NotLFSR

chall

완전히 선형적으로 다음 rng state가 계산되고, key가 128비트인데 output으로 256비트 준 상황. 일반적인 LFSR과 다르게 state 계산할 때 초기상태가 1(affine꼴)이지만 여전히 선형이므로 충분한 길이의 output이 있다면 berlekamp massey알고리즘으로 recurrent sequence를 복구할 수 있음

Baby ECDLP

chall
음 baby는 아닌 것 같은데..
$n = pq$ 인 $n$에 대해 $(p, p), (q, q)$를 지나는 EllipticCurve에 대한 dlp를 푸는 문제
$a, b, C=flag*G$가 주어짐
1. $(p, p), (q, q)$ 이거 연립하면

이므로 $b$가 $n$의 배수이고, 점 $C$로 $n$ 배수 하나 더 구할 수 있으니, $n$ 구할 수 있음
2. $a$식이랑 $pq = n$ 이용해서 $p, q$ leak
3. $p = q = 3 \ (mod \ 4)$이고 $y^2 = x^3 + ax$꼴이므로 order가 각각 $p+1$, $q+1$이다. (참고) 따라서, $order \ | \ p^k-1$이 되는 최소 $k$가 2가 되고, move attack을 사용할 수 있다. $p, q$에 대해 각각 dlp하고 crt로 합치면 됨

항상 느끼는건데 maple3142님은 익스 코드가 깔끔한듯

# k = 2인 상황에 대한 move attack by maple3142
def mov_attack(E, P, G):
    k = 2
    p = E.base_ring().characteristic()
    K = GF(p**k, "a")
    EK = E.base_extend(K)
    PK = EK(P)
    GK = EK(G)
    QK = EK.random_point()  # Assuming QK is linear independent to PK
    egqn = PK.tate_pairing(QK, E.order(), k)  # e(P,Q)=e(G,Q)^n
    egq = GK.tate_pairing(QK, E.order(), k)  # e(G,Q)
    odr = ZZ(pari.fforder(egq, p + 1))
    lg = ZZ(pari.fflog(egqn, egq, odr))
    return lg, odr

작성중...