티스토리 뷰
2021 암호분석경진대회
CRYPTO ANALYSIS CONTEST
cryptocontest.kr
3번 문제는 암호응용 분야입니다. 최근 이슈인 암호화폐 중 비트코인 스크립트를 활용하여 구현하는 문제였습니다. 고등부와 공통 문항으로 그렇게 어렵지 않은 문제입니다. 코드짜는데 하루 풀이 쓰는데 하루 썼던 기억이 납니다. 파이썬을 활용하여 구현하였고, 실행결과 이미지는 exe 파일로 제출을 했었기에 윈도우 커맨드 창입니다.
현재 BOB에서 암호화폐 관련 프로젝트를 진행 중인데 지금의 지식 상태로 이 문제를 풀었다면 좀 더 깔끔한 결과가 나왔을 것 같은 아쉬움이 듭니다.
3-1번 문제의 경우 간단한 스택 프로세서를 구현하는 문제였습니다. 동작은 숫자1, 숫자2, add, 숫자3, equal 순으로 push를 진행하는데 add와 equal의 경우 동작과 동시에 해당 숫자를 pop합니다. 간단한 구현이기에 코드만 올리겠습니다.
# -*- coding: utf-8 -*-
# SimpleStack.py
# 초기화
def init():
print("덧셈 연산 결과와 주어진 결과를 비교합니다. ")
stack = []
cnt = 5
return stack, cnt
# 남은 카운트 프린트
def print_cnt(cnt):
if cnt <= 0:
print("남은 기회가 없습니다.")
else:
print("남은 기회 : ", cnt)
return
# 스택 내용 프린트
def print_stack(stack):
if len(stack) == 0:
print("stack is empty")
else:
print("========== stack ===========")
print("top ----> ", stack[-1])
for i in range(len(stack) - 2, -1, -1):
print("============================")
print(" ", stack[i])
print('============================\n')
return
def push(stack, cnt):
print("push 연산입니다.")
while True:
try:
print_cnt(cnt)
if cnt <= 0:
break
num = int(input("정수를 입력하세요 : "))
except :
print("정수가 아닙니다.")
cnt -= 1
else:
stack.append(num)
print_stack(stack)
break
return stack, cnt
def add(stack, cnt):
print("덧셈 연산입니다.")
while True:
try:
print_cnt(cnt)
if cnt <= 0:
break
oper = input("ADD를 입력하세요.")
possible_case = ["ADD", "Add", "add", "+"]
if oper in possible_case:
num1 = stack.pop()
num2 = stack.pop()
num = num1 + num2
stack.append(num)
print_stack(stack)
break
else:
print("잘못 입력하였습니다.")
cnt -= 1
except:
print("잘못 입력하였습니다.")
cnt -= 1
return stack, cnt
def equal(stack, cnt):
print("비교 연산입니다.")
while True:
try:
print_cnt(cnt)
if cnt <= 0:
break
oper = input("EQUAL을 입력하세요.")
possible_case = ["EQUAL", "Equal", "equal", "==", "="]
if oper in possible_case:
num1 = stack.pop()
num2 = stack.pop()
if num1 == num2:
stack.append("True")
else:
stack.append("False")
print_stack(stack)
break
else:
print("잘못 입력하였습니다.")
cnt -= 1
except:
print("잘못 입력하였습니다.")
cnt -= 1
return stack, cnt# -*- coding: utf-8 -*-
# 3-1.py
import SimpleStack as st
import sys
# 남은 횟수 없을 시 종료
def error_check(cnt):
if cnt <= 0:
sys.exit()
else:
return
stack, cnt = st.init()
stack, cnt = st.push(stack, cnt)
error_check(cnt)
stack, cnt = st.push(stack, cnt)
error_check(cnt)
stack, cnt = st.add(stack, cnt)
error_check(cnt)
stack, cnt = st.push(stack, cnt)
error_check(cnt)
stack, cnt = st.equal(stack, cnt)
error_check(cnt)
3-1은 몸풀기였다면 2번부터 본격적인 문제가 시작됩니다.
3-2번 문항은 ECC 중 secp256r1 모드와 LSH 해시함수를 이용하여 ECDSA 서명 생성 및 검증 프로토콜을 구현하는 문제입니다. ECC의 경우 secp256r1, secp256k1 등 다양한 파라미터를 제시하는 모드가 존재합니다. 현재 비트코인에서는 secp256k1 모드를 사용 중이며, 해당 파라미터는 다음 문서에서 확인 가능합니다.
https://www.secg.org/sec2-v2.pdf
해당 문서 13페이지부터 secp256r1 모드에 대한 추천 파라미터가 제공되며, 문제 풀이 시 해당 파라미터를 이용하였습니다.
Elliptic Curve는 위에 나온 p, a, b 값 등에 맞춰 GF(p), y^2 = x^3+ax+b 등이 사용되면 G 값을 통해 generator가 되는 점 또한 확인 가능합니다. 이외 랜덤값을 위한 seed, generator의 order 등도 나와 있으므로 알맞게 사용하면 됩니다.
LSH 해시 함수는 KISA에서 만든 국산 해시함수로 다음 링크에서 알고리즘 확인이 가능합니다.
https://seed.kisa.or.kr/kisa/algorithm/EgovLSHInfo.do
KISA 암호이용활성화 - 국산 암호기술 - LSH
국산 암호기술 정보보호의 기반 암호기술 및 정책에 대한 다양한 정보전달 HOME 국산 암호기술 소개 국산 암호기술 차세대 암호 암호모듈검증 암호 역기능 대응 자료실 알림마당 LSH SEED HIGHT ARIA L
seed.kisa.or.kr
ECDSA의 경우 위키피디아에 서명 생성, 검증 과정이 잘 나와있으므로 해당 알고리즘을 따라 가며 구현을 완료하면 됩니다. 파라미터는 위의 값을 사용하였고, 암호학적으로 안전한 해시함수로 LSH를 사용하면 됩니다. LSH의 경우 KISA에서 각 언어에 맞는 모듈을 제공하므로 해당 모듈을 사용하였습니다.
https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
Elliptic Curve Digital Signature Algorithm - Wikipedia
From Wikipedia, the free encyclopedia Jump to navigation Jump to search In cryptography, the Elliptic Curve Digital Signature Algorithm (ECDSA) offers a variant of the Digital Signature Algorithm (DSA) which uses elliptic curve cryptography. Key and signat
en.wikipedia.org
코드는 다음과 같습니다.
# -*- coding: utf-8 -*-
# ECC P256r1
# ECDSA.py
# 필요 모듈 import
from lsh import LSHDigest
import random
# recommended parameter (SEC2)
# ECC : y^2 = x^3+ax+b over F(p)
p = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
a = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC
b = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
# random seed
S = 0xC49D360886E704936A6678E1139D26B7819F7E90
random.seed(S)
# generating point
Gx = 0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296
Gy = 0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5
# order
n = 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551
# inverse of num (modulo mod) 계산
def inverse(num, mod):
r1, r2 = num, mod
t1, t2 = 1, 0
while (r2 > 0):
q = r1//r2
r = (r1 - q * r2) % mod
r1, r2 = r2, r
t = (t1 - q * t2) % mod
t1, t2 = t2, t
return t1 % mod
# 2*(Qx, Qy) 계산
def doubling(Qx, Qy, Fp, Ea):
# EC : y^2 = x^3 + ax + b over F(p)
# parameter Fp = p, Ea = a in above function
# result is pre-calculated result
lambda_= ((3 * Qx * Qx + Ea) * inverse(2 * Qy, Fp)) % Fp
x_res = (lambda_**2 - 2 * Qx) % Fp
y_res = ((Qx - x_res) * lambda_ - Qy) % Fp
result = (x_res, y_res)
return result
# (Px, Py) + (Qx, Qy) 계산
# Fp는 doubling의 Fp와 동일
def add(Px, Py, Qx, Qy, Fp):
lambda_ = ((Qy - Py) * (inverse(Qx - Px, Fp))) % Fp
x_res = (lambda_**2 - Px - Qx) % Fp
y_res = ((Px - x_res) * lambda_ - Py) % Fp
result = (x_res, y_res)
return result
# k * (Qx, Qy) 계산, shamir trick 이용
# Fp, Ea는 doubling의 Fp, Ea와 동일
def multiple(Qx, Qy, k, Fp, Ea):
bin_k = bin(k)[2:]
result = (Qx, Qy)
for i in range(1, len(bin_k)):
if bin_k[i] == '1':
result = doubling(result[0], result[1], Fp, Ea)
result = add(result[0], result[1], Qx, Qy, Fp)
else:
result = doubling(result[0], result[1], Fp, Ea)
return result
# 특정인 A의 키 쌍 만들기
# (개인키, 공개키)
def make_key():
global p, a, b, S, Gx, Gy, n
PrivateKey = random.randint(1, n-1)
(Qx, Qy) = multiple(Gx, Gy, PrivateKey, p, a)
PublicKey = (Qx, Qy)
result = (PrivateKey, PublicKey)
return result
# LSH256 해시 함수를 이용해 메시지 해싱
def Hashing(msg):
Lsh = LSHDigest.getInstance(256, 256)
if type(msg) is str:
msg = msg.encode('utf-8')
Lsh.update(msg)
Hash = Lsh.final()
return Hash
# 서명 생성
def make_signature(msg, d):
# msg : message, d : private key
global p, a, b, S, Gx, Gy, n
# LSH 해쉬 함수를 이용한 msg 해쉬 결과 = Hash (type=bytearray)
Hash = Hashing(msg)
# 서명 생성
# 계산의 편의를 위해 Hash를 int로 변경 (e)
e = ''.join(format(x, '02x') for x in Hash)
e = int('0x'+e, 16)
Ln = len(bin(n)) - 2 # bin(n) = '0b....'
z = bin(e)[:Ln + 2] # bin(e) = '0b...'
z = int(z, 2)
r, s = 0, 0
while True:
# shamir trick 이용해 k * g 계산
k = random.randint(1,n-1)
(x, y) = multiple(Gx, Gy, k, p, a)
# r = x (mod n) 계산
r = x % n
# s = k^(-1) * (z + rd) (mod n) 계산
inverse_k = inverse(k, n)
s = (inverse_k * (z + r * d)) % n
if r != 0 and s != 0:
break
signature1 = (r, s)
signature2 = (r, ((-1)*s) % n)
signature = (signature1, signature2)
return signature
# 서명 검증
def sig_verification(sig, Q, msg):
# sig : signature, Q : public key, msg : message
global p, a, b, S, Gx, Gy, n
# Q : 곡선 위의 점 인증
Qx, Qy = Q[0], Q[1]
# Q = O(무한 원점) 인지 확인
# Q + Q = Q 이면 Q는 O
if doubling(Qx, Qy, p, a) == Q:
print("Public key Q is O")
return False
# Q가 곡선 위의 점인지 확인
# EC : y^2 = x^3 + ax + b over F(p)
if (Qy**2) % p != (Qx**3 + a * Qx + b) % p:
print("Q is not in curve")
return False
# n * Q = O 인지 확인
# n * Q + Q = Q 이면 n * Q = O
nQ = multiple(Qx, Qy, n, p, a)
if add(nQ[0], nQ[1], Qx, Qy, p) == Q:
print("n*Q is O")
return False
# 서명 유효성 인증
r, s = sig[0], sig[1]
# r, s in [1, n-1] 인지 확인
if r < 1 or r > n or s < 1 or s > n:
print("r, s is not in [1, n-1]")
return False
# LSH 해쉬 함수를 이용한 msg 해쉬 결과 = Hash (type=bytearray)
Hash = Hashing(msg)
# 계산의 편의를 위해 Hash를 int로 변경 (e)
e = ''.join(format(x, '02x') for x in Hash)
e = int('0x'+e, 16)
Ln = len(bin(n)) - 2 # bin(n) = '0b....'
z = bin(e)[:Ln + 2] # bin(e) = '0b...'
z = int(z, 2)
# u1, v1 = zw, u2, v2 = rw 계산, w = s^(-1) mod n
w1 = inverse(s, n)
u1 = (z * w1) % n
u2 = (r * w1) % n
# (x1, y1) = u1 * G + u2 * Q 계산
# (x1, y1) = O (무한원점) 이면 무효
(x1, y1) = (0, 0)
u1xG = multiple(Gx, Gy, u1, p, a)
u2xQ = multiple(Qx, Qy, u2, p, a)
(x1, y1) = add(u1xG[0], u1xG[1], u2xQ[0], u2xQ[1], p)
if doubling(x1, y1, p, a) == (x1, y1) :
print("(x1, y1) is O")
return False
# 최종 검증
if (r % n == x1 % n):
print("signature is valid")
return True
else:
print("signature is invalid")
return False# -*- coding: utf-8 -*-
# 3-2.py
import ECDSA
import random
print("================================")
print("==== ECDSA 서명 생성 및 검증 ====")
print("================================")
print("메시지를 입력하세요.")
msg = input("Enter : ")
print('\n')
print("================================")
print("키를 생성합니다.\n")
key = ECDSA.make_key()
print("개인키 : ")
print("d : ", hex(key[0]))
print('\n')
print("공개키 : ")
print("Qx : ", hex(key[1][0]))
print("Qy : ", hex(key[1][1]))
print('\n')
print("================================")
print("서명을 생성합니다.\n")
signature = ECDSA.make_signature(msg, key[0])
print("서명 = (r1, s1), (r2, s2)")
print("r1 : ")
print(hex(signature[0][0]))
print("s1 : ")
print(hex(signature[0][1]))
print('\n')
print("r2 : ")
print(hex(signature[1][0]))
print("s2 : ")
print(hex(signature[1][1]))
print('\n')
print("====== (r1, s1) 서명 검증 =======")
print("서명 검증을 합니다.\n")
sig = signature[0]
verifying = ECDSA.sig_verification(sig, key[1], msg)
if verifying == True:
print("서명 검증에 성공하였습니다.")
else:
print("서명 검증에 실패하였습니다.")
print('\n')
print("====== (r2, s2) 서명 검증 =======")
print("서명 검증을 합니다.\n")
sig = signature[1]
verifying = ECDSA.sig_verification(sig, key[1], msg)
if verifying == True:
print("서명 검증에 성공하였습니다.")
else:
print("서명 검증에 실패하였습니다.")
print('\n')
print("================================")
print("=====서명 검증 실패 테스트=======")
print("================================")
print("임의의 서명 값을 생성합니다.")
print("기존 공개키로 임의의 서명을 검증합니다.")
n = ECDSA.n
invalid_private_key = random.randint(1, n-1)
invalid_sig = ECDSA.make_signature(msg, invalid_private_key)
print("r1 : ")
print(hex(invalid_sig[0][0]))
print("s1 : ")
print(hex(invalid_sig[0][1]))
print('\n')
print("r2 : ")
print(hex(invalid_sig[1][0]))
print("s2 : ")
print(hex(invalid_sig[1][1]))
print("\n")
print("====== (r1, s1) 서명 검증 =======")
print("서명 검증을 합니다.\n")
verifying = ECDSA.sig_verification(invalid_sig[0], key[1], msg)
if verifying == True:
print("서명 검증에 성공하였습니다.")
else:
print("서명 검증에 실패하였습니다.")
print("\n")
print("====== (r2, s2) 서명 검증 =======")
print("서명 검증을 합니다.\n")
verifying = ECDSA.sig_verification(invalid_sig[1], key[1], msg)
if verifying == True:
print("서명 검증에 성공하였습니다.")
else:
print("서명 검증에 실패하였습니다.")
print('\n')
print("================================")
print("=====서명 검증 실패 테스트=======")
print("================================")
print("임의의 키를 생성합니다.")
print("기존 서명을 임의의 키로 생성된 공개키로 검증합니다.")
invalid_key = ECDSA.make_key()
print("개인키 : ")
print("d : ", hex(invalid_key[0]))
print('\n')
print("공개키 : ")
print("Qx : ", hex(invalid_key[1][0]))
print("Qy : ", hex(invalid_key[1][1]))
print('\n')
print("r1 : ")
print(hex(signature[0][0]))
print("s1 : ")
print(hex(signature[0][1]))
print('\n')
print("r2 : ")
print(hex(signature[1][0]))
print("s2 : ")
print(hex(signature[1][1]))
print("\n")
print("====== (r1, s1) 서명 검증 =======")
print("서명 검증을 합니다.\n")
verifying = ECDSA.sig_verification(signature[0], invalid_key[1], msg)
if verifying == True:
print("서명 검증에 성공하였습니다.")
else:
print("서명 검증에 실패하였습니다.")
print("\n")
print("====== (r2, s2) 서명 검증 =======")
print("서명 검증을 합니다.\n")
verifying = ECDSA.sig_verification(signature[1], invalid_key[1], msg)
if verifying == True:
print("서명 검증에 성공하였습니다.")
else:
print("서명 검증에 실패하였습니다.")
이번 문항으로 ECDSA의 파라미터의 다양성과 KISA의 LSH 함수에 대해 알 수 있었습니다.
3-3번 문항은 실제 비트코인 스크립트에서 사용하는 서명 검증 메커니즘을 이용하는 문제입니다. 이 때 당시 비트코인의 스크립트 문법을 처음 접하였기에 이해하는데 조금 어려웠지만, 공식 문서를 참조하여 이해하면 그렇게 어렵지 않은 문항임을 알 수 있습니다.
Script - Bitcoin Wiki
Bitcoin uses a scripting system for transactions. Forth-like, Script is simple, stack-based, and processed from left to right. It is intentionally not Turing-complete, with no loops. A script is essentially a list of instructions recorded with each transac
en.bitcoin.it
해당 문항도 1번과 마찬가지로 구현하면 되고, 2번 문항에서 사용한 ECDSA 알고리즘을 사용하여 서명 생성 및 검증을 진행하면 됩니다. 문제 풀이에서 스크립트 문법을 시각적으로 보이기 위해 스크립트 문법을 string 처리하였고, 큐를 사용하였지만, 실제로는 이와 같이 비트코인은 동작하지 않습니다.
또한 올바른 서명 생성, 검증 및 스크립트 언어의 동작을 위해 총 5가지 모드로 테스트를 진행하였습니다. 이미지 첨부는 올바른 검증을 진행하는 경우만 첨부하였습니다.
코드는 다음과 같습니다.
# -*- coding: utf-8 -*-
# ExtendedStack.py
import ECDSA
from queue import Queue
import random
# 초기화
def init():
print("확장된 스택 프로세서 입니다.")
print("메시지 소유권을 지정하고 확인합니다.\n")
stack = []
cnt = 5
return stack, cnt
# 남은 카운트 프린트
def print_cnt(cnt):
if cnt <= 0:
print("남은 기회가 없습니다.")
else:
print("남은 기회 : ", cnt)
return
# 스택 내용 프린트
def print_stack(stack):
if len(stack) == 0:
print("stack is empty")
else:
print("========== stack ===========")
if type(stack[-1]) is tuple:
print("top ----> ", (hex(stack[-1][0])[2:], hex(stack[-1][1])[2:]))
else:
print("top ----> ", stack[-1])
for i in range(len(stack) - 2, -1, -1):
print("============================")
if type(stack[i]) is tuple:
print(" ", (hex(stack[i][0])[2:], hex(stack[i][1])[2:]))
else:
print(" ", stack[i])
print('============================\n')
return
# script 생성
# parameter - signature, pubkey : 수신자의 서명, 수신자의 공개키
# msg, mode : 암호화 메시지, 테스트 모드
def make_script(cnt, sig, pubkey, msg, mode):
print_cnt(cnt)
print("================================================")
print("명령어는 다음과 같이 입력됩니다.")
print("<서명(hex)> <공개키(hex)> 복사명령어 해쉬명령어 <공개키 해쉬값(hex)> 동일검증명령어 서명검증명령어")
print("<r,s> <Qx,Qy> OP_DUP OP_HASH <HashX,HashY> OP_EQUALVERIFY OP_CHECKSIG")
print("ex) <abcd,0123> <01234,abcde> OP_DUP OP_HASH <0000,ffff> OP_EQUALVERIFY OP_CHECKSIG")
print("================================================")
if mode == 5:
scripts = input("명령어를 입력하세요 : ")
else:
if mode == 1:
(Qx, Qy) = pubkey
if mode == 2:
AttackerKey = random.randint(1, ECDSA.n)
(Qx, Qy) = ECDSA.multiple(ECDSA.Gx, ECDSA.Gy, AttackerKey, ECDSA.p, ECDSA.a)
if mode == 3:
AttackerKey = random.randint(1, ECDSA.n)
(Qx, Qy) = ECDSA.multiple(ECDSA.Gx, ECDSA.Gy, AttackerKey, ECDSA.p, ECDSA.a)
pubkey = (Qx, Qy)
if mode == 4:
AttackerKey = random.randint(1, ECDSA.n)
AttackerSig = ECDSA.make_signature(msg, AttackerKey)
sig = AttackerSig[0]
(Qx, Qy) = pubkey
Qx_bytes = Qx.to_bytes(32, 'big')
Qy_bytes = Qy.to_bytes(32, 'big')
Hash_Qx = ECDSA.Hashing(Qx_bytes)
Hash_Qy = ECDSA.Hashing(Qy_bytes)
Hash_Qx = ''.join(format(x, '02x') for x in Hash_Qx)
Hash_Qy = ''.join(format(x, '02x') for x in Hash_Qy)
scripts = ""
scripts += "<" + hex(sig[0])[2:] + "," + hex(sig[1])[2:] + "> "
scripts += "<" + hex(pubkey[0])[2:] + "," + hex(pubkey[1])[2:] + "> "
scripts += "OP_DUP OP_HASH "
scripts += "<" + str(Hash_Qx) + "," + str(Hash_Qy) + "> "
scripts += "OP_EQUALVERIFY OP_CHECKSIG "
scriptPubKey = []
scriptSig = []
for i in range(len(scripts.split())):
if i == 0 or i == 1:
scriptSig.append(scripts.split()[i])
else:
scriptPubKey.append(scripts.split()[i])
return scripts, scriptPubKey, scriptSig, cnt
# scripts를 큐로 변환
def scripts_to_queue(scripts, cnt):
queue = Queue()
scripts = scripts.split()
OperDict = {'OP_DUP' : 0x76, 'OP_HASH' : 0xAA, 'OP_EQUALVERIFY' : 0x88, 'OP_CHECKSIG' : 0xAC}
valid_script = True
for oper in scripts:
if oper[0:3] == "OP_":
if oper in OperDict.keys():
queue.put(OperDict[oper])
else:
print("잘못된 명령어입니다.\n")
cnt -= 1
valid_script = False
break
else:
if oper[0] == '<':
try:
numbers = oper.split(',')
num1 = int('0x' + numbers[0][1:], 16)
num2 = int('0x' + numbers[1][:-1], 16)
num_byte = (len(numbers[0][1:]) // 2) + (len(numbers[1][:-1]) // 2)
queue.put(num_byte)
queue.put((num1, num2))
except:
print("잘못된 값입니다.\n")
cnt -= 1
valid_script = False
break
else:
print("잘못된 입력입니다.\n")
cnt -= 1
valid_script = False
break
return queue, cnt, valid_script
# 연산
# op_code : 해당 operation code
# msg : 메시지
# scripts : 전체 명령, type = Queue
def oper(stack, msg, scripts):
# scripts 큐의 front 값으로 op_code 판단
op_code = scripts.get()
# 올바르게 작동 중인지 체크
valid = True
# 해시 값 push
# 올바른 op_code 일 때, 해당 바이트만큼의 값을 push
# ex. op_code = 0x02, scripts = 0x01 0x02 0x03
# 0x0203 = 515 를 stack에 push
if op_code >= 0x01 and op_code <=0x4B:
print("push 입니다.")
num = scripts.get()
stack.append(num)
print_stack(stack)
return stack, valid
# OP_DUP
# 스택의 top 값을 복사
elif op_code == 0x76:
print("duplicate 입니다.")
st_top = stack[-1]
stack.append(st_top)
print_stack(stack)
return stack, valid
# OP_HASH
# 스택의 top 값에 LSH256 적용
# LSH 라이브러리에 적용 시 32바이트로 입력
# ex. 1 = b'\x00\x00\.....\x01'
elif op_code == 0xAA:
print("hash 입니다.")
pubkey = stack.pop()
Qx = pubkey[0]
Qy = pubkey[1]
Qx_bytes = Qx.to_bytes(32, 'big')
Qy_bytes = Qy.to_bytes(32, 'big')
Hash_Qx = ECDSA.Hashing(Qx_bytes)
Hash_Qy = ECDSA.Hashing(Qy_bytes)
Hash_Qx = ''.join(format(x, '02x') for x in Hash_Qx)
Hash_Qy = ''.join(format(x, '02x') for x in Hash_Qy)
Hash_Qx = int('0x' + Hash_Qx, 16)
Hash_Qy = int('0x' + Hash_Qy, 16)
pubkeyHash = (Hash_Qx, Hash_Qy)
stack.append(pubkeyHash)
print_stack(stack)
return stack, valid
# OP_EQUALVERIFY
# 해시 값 검증
elif op_code == 0x88:
print("equal and verify 입니다.")
hash1 = stack.pop()
hash2 = stack.pop()
if hash1 == hash2:
print("hash 값이 일치합니다.")
else:
valid = False
print("hash 값이 일치하지 않습니다.")
print_stack(stack)
return stack, valid
# OP_CHECKSIG
# 서명 검증
elif op_code == 0xAC:
print("check signature 입니다.")
pubkey = stack.pop()
sig = stack.pop()
verifying = ECDSA.sig_verification(sig, pubkey, msg)
if verifying == True:
print("서명 검증에 성공하였습니다.")
stack.append("True")
else:
valid = False
print("서명 검증에 실패하였습니다.")
stack.append("False")
print_stack(stack)
return stack, valid
else:
print("올바르지 않은 명령어(op_code)입니다.")
valid = False
print_stack(stack)
return stack, valid# -*- coding: utf-8 -*-
# 3-3.py
import ECDSA
import ExtendedStack as st
import sys
# 남은 횟수 없을 시 종료
def error_check(cnt):
if cnt <= 0:
sys.exit()
else:
return
def hashing(pubkey):
Qx = pubkey[0]
Qy = pubkey[1]
Qx_bytes = Qx.to_bytes(32, 'big')
Qy_bytes = Qy.to_bytes(32, 'big')
Hash_Qx = ECDSA.Hashing(Qx_bytes)
Hash_Qy = ECDSA.Hashing(Qy_bytes)
Hash_Qx = ''.join(format(x, '02x') for x in Hash_Qx)
Hash_Qy = ''.join(format(x, '02x') for x in Hash_Qy)
return Hash_Qx, Hash_Qy
print("=========================================")
print("메시지를 입력하세요.")
msg = input()
print('\n')
print("키를 생성합니다.\n")
privateKey, publicKey = ECDSA.make_key()
print("서명을 생성합니다.\n")
signature = ECDSA.make_signature(msg, privateKey)
print("생성된 메시지, 키, 서명은 다음과 같습니다.\n")
print("메시지 : ", msg)
print("\n")
print("개인키 : ", hex(privateKey))
print("\n")
print("공개키 : Qx, Qy")
print("Qx : ", hex(publicKey[0]))
print("Qy : ", hex(publicKey[1]))
print("\n")
print("서명 : r, s")
print("r : ", hex(signature[0][0]))
print("s : ", hex(signature[0][1]))
print("\n")
print("공개키의 해시 값 : LSH(Qx), LSH(Qy)")
hx, hy = hashing(publicKey)
print("LSH(Qx) : ", '0x' + hx)
print("LSH(Qy) : ", '0x' + hy)
print("=========================================")
stack, cnt = st.init()
print("모드를 입력하세요.")
print("생성된 서명과 공개키로 서명 검증 확인 (검증 성공) : 1")
print("임의의 공개키에 대한 해시값 생성 (검증 실패) : 2")
print("임의의 공개키를 생성 (검증 실패) : 3")
print("임의의 서명 생성 (검증 실패) : 4")
print("직접 입력 (올바른 입력 시 검증 성공) : 5")
mode = int(input("mode : "))
if mode not in [1, 2, 3, 4, 5]:
print("다시 입력하세요.")
mode = int(input("mode : "))
while True:
# ECDSA 모듈에서 서명 생성 시 (r, s), (r, -s) 2가지 서명 생성
# (r, s)를 사용하기 위해 signature[0]를 택함.
scripts, scriptPubKey, scriptSig, cnt = st.make_script(cnt, signature[0], publicKey, msg, mode)
scripts, cnt, valid = st.scripts_to_queue(scripts, cnt)
if cnt <= 0 or valid == True:
break
error_check(cnt)
print("=========================================")
print("scriptPubKey : ", end = "")
for scr in scriptPubKey:
print(scr, end = " ")
print('\n')
print("scriptSig : ", end = "")
for scr in scriptSig:
print(scr, end=" ")
print('\n')
print("=========================================")
print('\n')
while scripts.empty() == False:
stack, valid = st.oper(stack, msg, scripts)
if valid == False:
break
error_check(cnt)
print('\n')
print("=========================================")
print("최종 결과")
if len(stack) == 1 and stack[0] == "True":
print("서명 검증에 성공하였습니다.")
print("UnLocking Success")
else:
print("서명 검증에 실패하였습니다.")
print("UnLocking Fail")
st.print_stack(stack)
풀이를 위해 스크립트 언어를 시각화하고 스택에 저장되는 모든 과정을 보이다보니 다소 난잡한 느낌이 들지만, 현재 비트코인에서 이루어지는 서명 검증 과정과 locking, unlocking 등의 메커니즘을 이해할 수 있는 문제였습니다.
BOB에서 진행 중인 "양자내성암호를 활용한 블록체인" 프로젝트 또한 잘 마무리하겠습니다.
감사합니다.
'암호학 > 2021 암호경진대회' 카테고리의 다른 글
| 2021 암호분석경진대회 6번 풀이 (0) | 2021.11.23 |
|---|---|
| 2021 암호분석경진대회 4번 풀이 (0) | 2021.11.23 |
| 2021 암호분석경진대회 소감 (6) | 2021.11.22 |
댓글