[Cryptohack] RSA (RSA STARTER 4, 5, 6)

RSA STARTER 4

문제

개인 키 d는 해당 공용 키로 작성된 암호 텍스트를 해독하는 데 사용됩니다(메시지에 "서명"하는 데도 사용되지만 나중에 설명하겠습니다). 개인 키는 암호화 기능을 신속하게 반전시킬 수 있는 비밀 정보 또는 "트랩도어"입니다. RSA가 제대로 구현된 경우 개인 키가 없는 경우 암호를 해독하는 가장 빠른 방법은 먼저 계수를 분해하는 것입니다. RSA에서 개인 키는 N의 합계에 대한 지수 모듈의 모듈식 곱셈 역입니다. 두 소수를 고려할 때: p = 8575040833397127524899993810777 q = 1029224947942998075080348647219 지수: e = 65537 개인 키 d는 무엇입니까?

풀이

RSA에서 개인키는 지수 모듈로서 오일러 피함수의 모듈러 곱셉의 역이기에

p = 857504083339712752489993810777
q = 1029224947942998075080348647219
e = 65537
PRI = (p-1)*(q-1)                        
d = pow(e, -1, PRI)

플래그값은 121832886702415731577073962957377780195510499965398469843281이다.

RSA STARTER 5

문제

공개 키 매개 변수만 사용하여 비밀 번호를 암호화했습니다: N = 882564595536224140639625987659160294262392304614613279163 e = 65537 이 암호문의 암호를 해독하려면 이전 작업에서 찾은 다음 매개 변수에 대한 개인 키를 사용합니다: c = 77578995801157236716362988471867235938148438525223303932

풀이

RSA STARTER 4와 비슷하게  개인키를 구하기 때문에 

p = 857504083339712752489993810777
q = 1029224947942998075080348647219
n = 882564595536224140639625987659416029426239230804614613279163
e = 65537
c = 77578995801157823671636298847186723593814843845525223303932
euler = (p-1)*(q-1)                       
d = pow(e, -1, euler)  

answer = pow(c, d, n)
print(answer)

플래그값은 13371337이다.

RSA STARTER 6

문제

메시지를 받는 사람이 메시지를 작성했다는 것을 어떻게 확인할 수 있습니까? 당신은 데이트 신청을 받았고, 당신은 그들에게 가고 싶다고 메시지를 보내고 싶어하지만 질투심 많은 연인은 이것을 별로 좋아하지 않습니다. 당신이 좋다고 메시지를 보내면, 질투심 많은 애인이 메시지를 가로채서 그것을 손상시켜서 이제는 아니라고 말합니다! 메시지에 서명함으로써 이러한 공격으로부터 보호할 수 있습니다. 당신이 M 메시지를 쓴다고 상상해 보세요. 당신은 친구의 공개 키인 C = Me0 mod N0으로 이 메시지를 암호화합니다. 이 메시지에 서명하려면 메시지 H(M)의 해시를 계산하고 이 해시를 개인 키 S = H(M)d1 mod N1로 "암호화"합니다. 실제 암호화 시스템에서는 메시지를 암호화하고 서명하는 데 별도의 키를 사용하는 것이 좋습니다. 친구는 개인 키(m = Cd0 mod N0)를 사용하여 메시지의 암호를 해독할 수 있습니다. 공개 키를 사용하여 = Se1 모드 N1을 계산합니다. 이제 H(m)를 계산하고 s : assert H(m) == s 와 비교하여 사용자가 보낸 메시지가 자신이 받은 메시지임을 확인할 수 있습니다! 개인 키와 SHA256 해시 함수를 사용하여 플래그 crypto{Imut4ble_m3ssag1ng}에 서명합니다. 해시 함수의 출력은 RSA 연산에 사용할 수 있는 숫자로 변환해야 합니다. Crypto.Util.number에서 가져올 수 있는 유용한 bytes_to_long() 함수를 기억하십시오.

풀이

문제에서 제공하는 private key

이번문제는 개인키와 SHA256 해시함수를 이용하여 플래그값을 해시화한다.

hashlib에도 sha256을 사용할수 있어 이용해보았다.

import hashlib
m = hashlib.sha256(b'crypto{Immut4ble_m3ssag1ng}').hexdigest()
N = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689
flag = pow(int(m,16),d,N)
print(S)

플래그값이다.

플래그값은 진짜 길기 때문에 위사진으로 대체한다.