이 영역을 누르면 첫 페이지로 이동
포렌식 & 개발 이야기 - Forensics & Development 블로그의 첫 페이지로 이동

포렌식 & 개발 이야기 - Forensics & Development

페이지 맨 위로 올라가기

포렌식 & 개발 이야기 - Forensics & Development

Pental - Forensics / iOS / Windows / Android / Kakaotalk / Telegram / Etc

[system32.kr] RSA104

  • 2020.09.28 16:20
  • CTF/system32.kr
글 작성자: pental

import flag
p=random_prime(2**1024,2**2048)
q=random_prime(2**1024,2**2048)
 
m=int("".join(map(lambda x: "%x"%ord(x),flag.RSA104)),16)
 
d=2
 
n=p*q
ph=lcm(p-1,q-1)
 
while True:
    if gcd(d,ph) == 1:
        if gcd(inverse_mod(d,ph),ph) == 1:
            break
    d=random_prime(2**32,(2**196)//3)
 
e = inverse_mod(d,ph)
 
c=power_mod(m,e,n)
print("n : %d"%n)
print("e : %d"%e)
print("c : %d"%c)
 
'''
n : 3032477561712159969038624247612606302727093197744745572360777744993048030579151290131884950670071512201722458811242592707243074323418373868073398996531180136126242688542841461913438478172053913773719857973056957510415089185531311916330433139160859155532409659622858101341629671133093910407988882203728644794239348874379289178268208136028146328608462805956004322306707963431825015814504527120066991706462521947050575789728072629790386979812591216920320695619189898158302924158362481320767791340177005794951187859952230300784183151549243274733552565133526078458260073961873518009693814714967027162359505297313081834097
e : 1284326209972781865603077160971589716597082902272211399147338196589345961573850891014620874113849550830317643345862732752124534686326463252899962000181188143162889928709347890165345017914959645496102666603718956753486894961504533642515954173645086524281277713918605331772209589332254176733343767685347067353884996601325356300748766439627935771840516032698936889600866124222228999743139709077148311384874536127451456213137422854764346519585961972790189180618601186990003649947864963747868420118048077351758919340934501383717797396822778472985089935849274746400142421412113278085759384358033116596950545779218825432105
c : 1806317310369980009932706441907756891122685977239032637376117653939592629181132498482038670618195984694250867867129559863693561069046351110958045303559854954588234447977692922829988785926862451801584819310702407585491177718755152055518733553927421577214740347956274468684747058682785453167186126384869898095355009620193273626895484591988153555158110880196986268949355968500092832237411654394295951441648748044375864656268901973180401377014754165200068392806529746504801815744345095507516459256483869799173054189822960434563127784898151685448212418354649354925633786590825084141495329161421555698179241894408873422390
'''

n값이 크기 때문에 위너 공격을 사용해야 한다.

  • https://github.com/pablocelayes/rsa-wiener-attack
 

pablocelayes/rsa-wiener-attack

A Python implementation of the Wiener attack on RSA public-key encryption scheme. - pablocelayes/rsa-wiener-attack

github.com

'''
Created on Dec 14, 2011

@author: pablocelayes
'''

import ContinuedFractions, Arithmetic, RSAvulnerableKeyGenerator
import crypto
from gmpy2 import *
def hack_RSA(e,n):
    '''
    Finds d knowing (e,n)
    applying the Wiener continued fraction attack
    '''
    frac = ContinuedFractions.rational_to_contfrac(e, n)
    convergents = ContinuedFractions.convergents_from_contfrac(frac)
    
    for (k,d) in convergents:
        
        #check if d is actually the key
        if k!=0 and (e*d-1)%k == 0:
            phi = (e*d-1)//k
            s = n - phi + 1
            # check if the equation x^2 - s*x + n = 0
            # has integer roots
            discr = s*s - 4*n
            if(discr>=0):
                t = Arithmetic.is_perfect_square(discr)
                if t!=-1 and (s+t)%2==0:
                    print("Hacked!")
                    
                    return d

    
if __name__ == "__main__":
    n = 3032477561712159969038624247612606302727093197744745572360777744993048030579151290131884950670071512201722458811242592707243074323418373868073398996531180136126242688542841461913438478172053913773719857973056957510415089185531311916330433139160859155532409659622858101341629671133093910407988882203728644794239348874379289178268208136028146328608462805956004322306707963431825015814504527120066991706462521947050575789728072629790386979812591216920320695619189898158302924158362481320767791340177005794951187859952230300784183151549243274733552565133526078458260073961873518009693814714967027162359505297313081834097
    e = 1284326209972781865603077160971589716597082902272211399147338196589345961573850891014620874113849550830317643345862732752124534686326463252899962000181188143162889928709347890165345017914959645496102666603718956753486894961504533642515954173645086524281277713918605331772209589332254176733343767685347067353884996601325356300748766439627935771840516032698936889600866124222228999743139709077148311384874536127451456213137422854764346519585961972790189180618601186990003649947864963747868420118048077351758919340934501383717797396822778472985089935849274746400142421412113278085759384358033116596950545779218825432105
    c = 1806317310369980009932706441907756891122685977239032637376117653939592629181132498482038670618195984694250867867129559863693561069046351110958045303559854954588234447977692922829988785926862451801584819310702407585491177718755152055518733553927421577214740347956274468684747058682785453167186126384869898095355009620193273626895484591988153555158110880196986268949355968500092832237411654394295951441648748044375864656268901973180401377014754165200068392806529746504801815744345095507516459256483869799173054189822960434563127784898151685448212418354649354925633786590825084141495329161421555698179241894408873422390
    d = hack_RSA(e, n)
    
    print ('%x' % pow(c, d, n))
464c41477b646f5f796f755f756e6465727374616e645f7769656e65727a5f61747461636b3f7d
# -*- coding: utf-8 -*-
result = '464c41477b646f5f796f755f756e6465727374616e645f7769656e65727a5f61747461636b3f7d'
print(result)
print(bytes.fromhex(result).decode('utf-8'))
저작자표시 비영리 (새창열림)

'CTF > system32.kr' 카테고리의 다른 글

[system32.kr] RSA105  (0) 2020.09.28
[system32.kr] RSA103  (0) 2020.09.28
[system32.kr] RSA102  (0) 2020.09.28
[system32.kr] RSA101  (0) 2020.09.28

댓글

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • [system32.kr] RSA105

    [system32.kr] RSA105

    2020.09.28
  • [system32.kr] RSA103

    [system32.kr] RSA103

    2020.09.28
  • [system32.kr] RSA102

    [system32.kr] RSA102

    2020.09.28
  • [system32.kr] RSA101

    [system32.kr] RSA101

    2020.09.28
다른 글 더 둘러보기

정보

포렌식 & 개발 이야기 - Forensics & Development 블로그의 첫 페이지로 이동

포렌식 & 개발 이야기 - Forensics & Development

  • 포렌식 & 개발 이야기 - Forensics & Development의 첫 페이지로 이동

검색

메뉴

  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록

카테고리

  • Category (452) N
    • Forensics (105)
      • Magnet AXIOM (28)
      • Digital Forensics Informati.. (9)
      • Iphone Forensics (24)
      • DFC (7)
      • 디지털포렌식전문가2급 자격증 (10)
      • FTK ACE 자격증 (7)
    • 이것저것 (7)
      • Ubuntu (6)
      • 디스코드 봇 (4)
      • Volatility GUI (2)
    • CTF (32)
      • NEWSECU (14)
      • CTF-d (5)
      • Puzzel - Network Forensics (2)
      • Security Traps (2)
      • system32.kr (5)
      • HMCTF (4)
    • Programming (260) N
      • C (10)
      • Python (11)
      • 백준 (206) N
      • 프로그래머스 (32)
    • 그냥 개발 및 잡담 (16)
      • Docker (2)
      • Google Cloud (3)
      • OS 개발 (3)
    • Best of Best (20)

최근 글

인기 글

댓글

공지사항

아카이브

태그

  • Forensics
  • 프로그래머스
  • 디지털포렌식
  • 백준
  • axiom
  • pental
  • 파이썬
  • 포렌식
  • 전체 보기…

정보

pental의 포렌식 & 개발 이야기 - Forensics & Development

포렌식 & 개발 이야기 - Forensics & Development

pental

블로그 구독하기

  • 구독하기
  • RSS 피드

방문자

  • 전체 방문자
  • 오늘
  • 어제

티스토리

  • 티스토리 홈
  • 이 블로그 관리하기
  • 글쓰기
Powered by Tistory / Kakao. Copyright © pental.

티스토리툴바