BaaaaaaaarkingDog
코딩, 해킹
[Cryptanalysis] RSA - Factorisation

주어진 pem 파일의 $N$은 576bit입니다. 맨 처음엔 소인수분해를 yafu로 하려고 했는데 잘 안되길래 혹시 유명한 $N$인가 싶어 검색해보니 해당 소수는 RSA-576이었고 $p$, $q$를 쉽게 찾을 수 있었습니다. 이후에는 그냥 RSA decryption을 수행하면 됩니다.

되게 의미가 없을 것 같이 생긴걸 평문이라고 줘서 맨 처음에 당황했네요

import base64

def gcd(a, b):
  if a == 0: return b
  return gcd(b%a, a)

def egcd(a, b):
  if a == 0:
    return (b, 0, 1)
  g, y, x = egcd(b%a,a)
  return (g, x - (b//a) * y, y)

def inv(a, m):
  g, x, y = egcd(a, m)
  if g != 1:
    raise Exception('No modular inverse')
  return x%m

n = 188198812920607963838697239461650439807163563379417382700763356422988859715234665485319060606504743045317388011303396716199692321205734031879550656996221305168759307650257059
p = 398075086424064937397125500550386491199064362342526708406385189575946388957261768583317
q = 472772146107435302536223071973048224632914695302097116459852171130520711256363590397527
e = 0x10001
d = inv(e,(p-1)*(q-1))
Cipher_b64 = 'e8oQDihsmkvjT3sZe+EE8lwNvBEsFegYF6+OOFOiR6gMtMZxxba/bIgLUD8pV3yEf0gOOfHuB5bC3vQmo7bE4PcIKfpFGZBA'
C = int.from_bytes(base64.b64decode(Cipher_b64),"big")
P = pow(C,d,n).to_bytes(200,byteorder='big')
print(P)
  Comments
댓글 쓰기