LINE CTF 2022 write up

Whois_Ajou 팀으로 참여했다.

Crypto

ss-puzzle

단순 xor 역연산이다. 알고 있는 값들을 토대로 하나씩 xor 역연산 해가면서 찾아나아가면 된다.
참고로 S[0] = "LINECTF{" 임을 알고 있으면 된다.

X Factor

rsa blind signature attack 같은 느낌인데 sign을 해주는 기능을 제공해주지는 않는다.
대신 plain -> signature pair들을 제공해주기 때문에 이 값들을 sign함수 대신 사용하는 느낌으로 가야된다.
0x686178656c696f6e 값의 signature를 구하는 문제이다.

문제 제목이 힌트라고 볼 수 있는데, 각 plain 값들을 소인수분해한다. 이는 factordb 사이트를 이용하면 된다.
a ~ g의 값들을 사용하여 Z를 만들어내려면 ( f * b * g * d * g * d ) / ( c * e * a ) 가 된다.

http://the2702.com/2015/09/07/RSA-Blinding-Attack.html

The 2702 - Computer Security and CTF Writeups

http://the2702.com/2015/09/07/RSA-Blinding-Attack.html

plain a ~ g, Z의 signature 값을 Sa ~ Sg, SZ 라고 하면,
위 사진의 식에서
M=Z = ( f * b * g * d * g * d ) / ( c * e * a ) ,
r= Sc * Se * Sa
r^e mod N = c * e * a
이므로 M' = ( f * b * g * d * g * d ) / ( c * e * a ) * (c * e * a) mod N = ( f * b * g * d * g * d )

S' = M'^d mod N = ( f * b * g * d * g * d )^d mod N = ( Sf * Sb * Sg * Sd * Sg * Sd ) mod N

우리가 원하는 S = S'/r mod N = ( ( Sf * Sb * Sg * Sd * Sg * Sd ) / ( Sc * Se * Sa ) ) mod N 이다.

https://ohgym.tistory.com/13, 모듈로 나눗셈 성질

( Sc * Se * Sa ) 의 역원을 구해야 한다.

https://ohgym.tistory.com/13

( Sc * Se * Sa ) 와 N 은 서로소이므로 확장된 유클리드 호제법을 사용하여 역원 x를 구한다.

역원을 얻었다.

S를 연산하고, 검증했다.
클리어.