2020 암호경진대회 4번 문제 풀이 (2)

지난 번 포스팅에서 CPA를 이용하여 주어진 암호화된 hwp 파일을 복호화하였습니다. 해당 hwp파일은 다음과 같습니다.

(아래 hwp 파일은 복호화 후 제가 글씨체와 글씨 크기를 변경한 것입니다. 실제 복호화된 hwp 파일은 글씨체와 크기가 다를 수 있습니다.)

4번 결과.hwp

0.03MB

열심히 주어진 문제를 푸니 또다른 문제가 나왔습니다. 하지만 위 문제는 저도 ecdsa에 대해 잘 모르던 때였지만, 이틀 만에 풀었을 정도로 어렵지 않은 문제입니다. 

 

1. 문제 접근

위 문제는 ECDSA를 이용한 전자서명 문제입니다. 우선 ECDSA에 대해 간략히 소개하면 다음과 같습니다.

ECDSA는 ECC 알고리즘을 이용한 전자서명입니다. ECC란 타원곡선 알고리즘에 기반한 공개키 암호 방식입니다. 

타원곡선(elliptic curve)이라하면, 타원과 비슷하게 생긴 것 아닌가 생각하실 수 있지만, 타원곡선은 타원과는 다른 대수 곡선으로써 정수 연산만을 합니다. (이에 대해 이해하기 위해서는 대수학적인 이해가 필요하지만 넘어가겠습니다.)

 

타원곡선의 일반적인 형태와 연산은 다음과 같습니다. (characteristic 값이 2,3 인 경우는 좀 더 복잡합니다.)

$$ y^2 = x^3 + ax +b $$

ECC 알고리즘을 이용하여 modulo 연산에서 x = B * C (mod p)는 계산하기 쉽지만, A = x * B (mod p)로 주어져있을 때 x를 구하기 어려운 이산 로그 문제를 활용한 전자서명입니다. 실제로 블록체인과 같은 곳에서 많이 쓰이고 있습니다.

 

위키 백과를 참고한 서명 절차는 다음과 같습니다.

ko.wikipedia.org/wiki/%ED%83%80%EC%9B%90%EA%B3%A1%EC%84%A0_DSA

개인키를 찾기 위한 값들은 문제에 모두 주어져있으므로 이를 이용하여 풀어보도록 합시다.

 

2. 문제 풀이

위 문제를 풀기 위해 하나의 힌트를 얻을 수 있습니다. 바로 M1, M2에 대한 서명 값중 r1, r2가 동일하다는 것입니다.

그리고 Elliptic curve에서 P=( x , y ) => -P=( x , -y ) 임을 이용하면 됩니다.

그러므로 $r_1=x_1=(k_1)*G_x \, (mod\,n) , r_2=x_2=(k_2)*G_x \,(mod \,n)$ 이므로 $k_1 = k_2, k_1 = -k_2 $ 두 가지로 나누어 올바른 서명인지 확인하면 됩니다.

 

1. $k_1 = k_2 $

- $r_1 = r_2 = r, k_1 = k_2 = k$라 하자

- $s_1 = k^{-1} (h(M_1)+rd) \,(mod\, n), s_2 = k^{-1} (h(M_2)+rd) \,(mod\, n) $ 을 만족한다.

- $k = (s_1)^{-1} (h(M_1)+rd) = (s_2)^{-1} (h(M_2)+rd) \,(mod\, n) $이므로 다음과 같이 정리할 수 있다.

    → $(h(M_1)+rd)s_2 = (h(M_2)+rd)s_1 \, (mod\, n) $

    → $h(M_1)s_2 - h(M_2)s_1 = rd(s_1 - s_2) \,(mod\, n)$

    → $(h(M_1)s_2 - h(M_2)s_1)r^{-1}(s_1 - s_2)^{-1} = d \, (mod \,n)$

 그러므로 문제에서 주어진 값들만을 이용하여 d를 찾을 수 있습니다.

하지만 이렇게 계산한 d는 다시 검증을 해보면 Q=dG를 만족하지 않습니다.

 

2. $k_1 = -k_2$

 - $s_1 = k^{-1}(h(M_1) + rd)\, (mod \,n), s_2 = (-k)^{-1}(h(M_2) + rd)\, (mod\, n)$ 입니다.

 - 위와 마찬가지 과정으로 계산하면 다음과 같습니다.

 - $( -h(M_1)s_2 -h(M_2)s_1 )r^{-1}( s_1 + s_2)^{-1} = d\,(mod \,n)$

 

이렇게 계산한 d를 이용해 검증하면 Q=dG가 맞게 나옵니다.

( d=0xbea4fd03c804ea0160a096f4c6b438d54ab78458e124e8f68d42cd7010807a1b )

 

맞는 경우만 확인하면 다음과 같습니다! 혹시 모르기에 문제에 주어진 조건들도 올바른 점인지, identity가 아닌지, 기본적인 ECDSA 성질을 만족하는 지에 대한 체크도 같이 하였습니다. 모든 결과를 다 통과하였습니다.

   

아래 소스 코드를 참고하여 보시면 됩니다!

p=0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
a=-3
b=0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
gx=0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296 
gy=0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5
n=0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551

h1=0xE06554818E902B4BA339F066967C0000DA3FCDA4FD7EB4EF89C124FA78BDA419
h2=0x5D2D3CEB7ABE552344276D47D36A8175B7AEB250A9BF0BF00E850CD23ECF2E43

r=0xF42A3ADB78BF22D9AA571FDFB0C93B415C8B50719C25B23F6F77DC299C01F2D7
s1=0x90A7F16EAFE3DB7923A07A6E8CF68F688100ABE3730A5416B37FA4BFBA7F5E22
s2=0x865BF221DD856B991EB6EF7EF1E0D263215FC8D7F2283A22C1F927ABDCC35B5B

qx=0xF44CD6277CED3F9CC2F29144CDBCFDC40F1BF556707ED8190E838D711A12EC03
qy=0x68B6FAF59BEC47A11D98800B4BE578CA4399B34EF94D6B602F5186D41B7430C9

def inverse_modn(a,n):
    r1,r2=a,n
    t1,t2=1,0
    while (r2>0):
        q=r1//r2
        r=(r1-q*r2)%n
        r1,r2=r2,r
        t=(t1-q*t2)%n
        t1,t2=t2,t
    return t1%n

def doubling(Qx,Qy,p,a):
    lambda_=((3*Qx*Qx+a)*inverse_modn(2*Qy,p))%p
    x_res=(lambda_**2-2*Qx)%p
    y_res=((Qx-x_res)*lambda_-Qy)%p
    result=(x_res,y_res)
    return result

def add(Px,Py,Qx,Qy,p):
    lambda__=(Qy-Py)*(inverse_modn(Qx-Px,p))%p
    x_res=(lambda__**2-Px-Qx)%p
    y_res=((Px-x_res)*lambda__-Py)%p
    result=(x_res,y_res)
    return result

####@@@@@#####
#n,h1,h2=256bit 이므로 z1=h1,z2=h2
# r1=x1=kG mod n
# r2=x2=k'G mod n
# r1=r2 => k'=-k
#d 계산
z1,z2=h1,h2
t=((-1)*((z1*s2)+(z2*s1)))%n
inv=inverse_modn(((s1+s2)*r)%n,n)
d=(t*inv)%n
print("private key:",hex(d))

#####@@@@@#####
#개인키 d가 맞는가
check=(gx,gy)
bin_d=bin(d)[2:]

for i in range(1,len(bin_d)):
    if bin_d[i]=='1':
        check=doubling(check[0],check[1],p,a)
        check=add(check[0],check[1],gx,gy,p)
    elif bin_d[i]=='0':
        check=doubling(check[0],check[1],p,a)

if qx==check[0] and qy==check[1]:
    print("d is right") 

#####@@@@@#####
#Q가 curve 위 점인가
if (qy**2)%p==(qx**3+a*qx+b)%p:
    print('Q is in curve')

#####@@@@@#####
#Q가 identity 아닌가
if doubling(qx,qy,p,a)!=(qx,qy):
    print('Q is not identity')

#####@@@@@#####
#n*Q=O 만족하는가
bin_n=bin(n)[2:]
gen=(qx,qy)
for i in range(1,len(bin_n)):
    if bin_n[i]=='1':
        gen=doubling(gen[0],gen[1],p,a)
        gen=add(gen[0],gen[1],qx,qy,p)
    elif bin_n[i]=='0':
        gen=doubling(gen[0],gen[1],p,a)

if add(gen[0],gen[1],qx,qy,p)[0]==qx:
    print("n*Q=O")

#####@@@@@#####
#n*G=O 만족하는가    
gen2=(gx,gy)
for i in range(1,len(bin_n)):
    if bin_n[i]=='1':
        gen2=doubling(gen2[0],gen2[1],p,a)
        gen2=add(gen2[0],gen2[1],gx,gy,p)
    elif bin_n[i]=='0':
        gen2=doubling(gen2[0],gen2[1],p,a)

if add(gen2[0],gen2[1],gx,gy,p)[0]==gx:
    print("n*G=O")

#####@@@@@#####
#r,s는 모두 n보다 작은가
if r<n and s1<n and s2<n:
    print("r,s1,s2 is in 1~(n-1)")

#####@@@@@#####
#서명 유효성 판단
w1=inverse_modn(s1,n)
w2=inverse_modn(s2,n)

u1=(z1*w1)%n
u2=(r*w1)%n

v1=(z2*w2)%n
v2=(r*w2)%n

str1=bin(u1)[2:]
str2=bin(u2)[2:]

str3=bin(v1)[2:]
str4=bin(v2)[2:]

if len(str1)>len(str2):
    while(len(str1)>len(str2)):
        str2='0'+str2

if len(str1)<len(str2):
    while(len(str1)<len(str2)):
        str1='0'+str1

if len(str3)>len(str4):
    while(len(str3)>len(str4)):
        str4='0'+str4

if len(str3)<len(str4):
    while(len(str3)<len(str4)):
        str3='0'+str3

R=add(gx,gy,qx,qy,p)
rx=R[0]
ry=R[1]

if str1[0]=='1':
    test=(gx,gy)
elif str2[0]=='1':
    test=(qx,qy)

#####@@@@@#####
#S1에 대해 판단
for i in range(1,len(str1)):
    if (str1[i]=='0' and str2[i]=='0' ):
        test=doubling(test[0],test[1],p,a)
    elif (str1[i]=='0' and str2[i]=='1'):
        test=doubling(test[0],test[1],p,a)
        test=add(test[0],test[1],qx,qy,p)
    elif (str1[i]=='1' and str2[i]=='0'):
        test=doubling(test[0],test[1],p,a)
        test=add(test[0],test[1],gx,gy,p)
    elif (str1[i]=='1' and str2[i]=='1'):
        test=doubling(test[0],test[1],p,a)
        test=add(test[0],test[1],rx,ry,p)

if test[0]%n==r%n:
    print('signature is valid on S1')
    
if str3[0]=='1':
    test2=(gx,gy)
elif str4[0]=='1':
    test2=(qx,qy)

#####@@@@@#####
#S2에 대해 판단
for i in range(1,len(str3)):
    if (str3[i]=='0' and str4[i]=='0' ):
        test2=doubling(test2[0],test2[1],p,a)
    elif (str3[i]=='0' and str4[i]=='1'):
        test2=doubling(test2[0],test2[1],p,a)
        test2=add(test2[0],test2[1],qx,qy,p)
    elif (str3[i]=='1' and str4[i]=='0'):
        test2=doubling(test2[0],test2[1],p,a)
        test2=add(test2[0],test2[1],gx,gy,p)
    elif (str3[i]=='1' and str4[i]=='1'):
        test2=doubling(test2[0],test2[1],p,a)
        test2=add(test2[0],test2[1],rx,ry,p)

if test2[0]%n==r%n:
    print('signature is valid on S2')