The worst RSA Joke (Crypto 350)
公開鍵と暗号ファイルが与えられている。まず、公開鍵を見てみる。
$ openssl rsa -pubin -text < public.pem
Public-Key: (2049 bit)
Modulus:
01:21:3b:05:7d:6f:de:bc:45:27:b5:b7:42:1a:c1:
e9:3c:cf:fe:a7:6c:4f:08:74:99:1c:f3:fa:cf:0e:
ab:9e:f6:46:a2:18:39:82:0b:4d:65:3a:91:6b:68:
f2:58:e9:d3:f7:c2:ba:05:4e:4a:f0:5f:3e:4d:61:
b3:de:77:2d:2a:d2:33:8b:0e:ae:6e:a0:8f:20:76:
e4:e4:b0:8a:b2:09:20:fa:68:85:e6:c4:4d:ec:1b:
ee:28:a8:76:53:c7:4b:cb:9e:9f:12:94:de:8a:48:
bd:61:46:52:a3:d6:59:df:ce:7b:89:44:61:0f:25:
bf:af:93:6e:9a:54:16:7c:4d:22:7d:16:d3:2e:65:
ea:45:8b:69:d6:0d:ec:d7:fa:03:4c:1b:3b:d8:62:
71:71:64:e7:78:5e:b0:6d:cc:5b:88:ba:a2:62:e4:
31:20:e5:46:65:c0:cb:cb:3e:ad:51:b0:a0:08:19:
b4:e9:1d:48:72:d3:fb:e7:72:4e:03:ab:71:bc:af:
8b:b8:4c:74:de:c9:6a:ad:fc:b1:86:53:a8:f0:53:
93:d6:66:06:99:23:bc:7b:9b:31:36:3d:6d:6d:9b:
45:9f:46:db:5b:af:96:f8:40:4a:af:1a:83:1f:0d:
b8:aa:d7:d9:3a:42:56:e8:15:6b:2b:70:75:7a:01:
20:93
Exponent: 65537 (0x10001)
writing RSA key
-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEBITsFfW/evEUntbdCGsHp
PM/+p2xPCHSZHPP6zw6rnvZGohg5ggtNZTqRa2jyWOnT98K6BU5K8F8+TWGz3nct
KtIziw6ubqCPIHbk5LCKsgkg+miF5sRN7BvuKKh2U8dLy56fEpTeiki9YUZSo9ZZ
3857iURhDyW/r5NumlQWfE0ifRbTLmXqRYtp1g3s1/oDTBs72GJxcWTneF6wbcxb
iLqiYuQxIOVGZcDLyz6tUbCgCBm06R1IctP753JOA6txvK+LuEx03slqrfyxhlOo
8FOT1mYGmSO8e5sxNj1tbZtFn0bbW6+W+EBKrxqDHw24qtfZOkJW6BVrK3B1egEg
kwIDAQAB
-----END PUBLIC KEY-----
n = 0x01213b057d6fdebc4527b5b7421ac1e93ccffea76c4f0874991cf3facf0eab9ef646a21839820b4d653a916b68f258e9d3f7c2ba054e4af05f3e4d61b3de772d2ad2338b0eae6ea08f2076e4e4b08ab20920fa6885e6c44dec1bee28a87653c74bcb9e9f1294de8a48bd614652a3d659dfce7b8944610f25bfaf936e9a54167c4d227d16d32e65ea458b69d60decd7fa034c1b3bd862717164e7785eb06dcc5b88baa262e43120e54665c0cbcb3ead51b0a00819b4e91d4872d3fbe7724e03ab71bcaf8bb84c74dec96aadfcb18653a8f05393d666069923bc7b9b31363d6d6d9b459f46db5baf96f8404aaf1a831f0db8aad7d93a4256e8156b2b70757a012093
= 36511974694593690272644354864534934200522045623187752384823594729275730789191680514905027084950729514148679507005058047146031869995768765034876499069680202424692876360895377987654388335335689563844006584610187090074654410815638237841872991488680663410743679302763304922852173164820002226109196761249018548478251723505481964749218302723593776180246783117481280725673997940309717028451914887375722437833384305529884261542397905220138488012276363046571670926597766521674838665982314321651508118240682649024780239598188845543243957916954287138820155843952556411235376764737602711594439293285811102883736229645274092478611
nを素因数分解してみる。
$ python -m primefac 36511974694593690272644354864534934200522045623187752384823594729275730789191680514905027084950729514148679507005058047146031869995768765034876499069680202424692876360895377987654388335335689563844006584610187090074654410815638237841872991488680663410743679302763304922852173164820002226109196761249018548478251723505481964749218302723593776180246783117481280725673997940309717028451914887375722437833384305529884261542397905220138488012276363046571670926597766521674838665982314321651508118240682649024780239598188845543243957916954287138820155843952556411235376764737602711594439293285811102883736229645274092478611
36511974694593690272644354864534934200522045623187752384823594729275730789191680514905027084950729514148679507005058047146031869995768765034876499069680202424692876360895377987654388335335689563844006584610187090074654410815638237841872991488680663410743679302763304922852173164820002226109196761249018548478251723505481964749218302723593776180246783117481280725673997940309717028451914887375722437833384305529884261542397905220138488012276363046571670926597766521674838665982314321651508118240682649024780239598188845543243957916954287138820155843952556411235376764737602711594439293285811102883736229645274092478611: 36511974694593690272644354864534934200522045623187752384823594729275730789191680514905027084950729514148679507005058047146031869995768765034876499069680202424692876360895377987654388335335689563844006584610187090074654410815638237841872991488680663410743679302763304922852173164820002226109196761249018548478251723505481964749218302723593776180246783117481280725673997940309717028451914887375722437833384305529884261542397905220138488012276363046571670926597766521674838665982314321651508118240682649024780239598188845543243957916954287138820155843952556411235376764737602711594439293285811102883736229645274092478611
nが素数のようだ。RSA暗号の仕組みを考える。
c = m^e % n
↓
c = m^e % (素数 * n)
この場合は復号結果が複数出るが、文字として読み取れるものをブルートフォースで探す。
from Crypto.PublicKey import RSA
def is_prime(d):
if d < 2:
return False
if d == 2:
return True
if d % 2 == 0:
return False
a = 3
while a ** 2 <= d:
if d % a == 0:
return False
a = a + 2
return True
def is_printable(s):
for i in range(len(s)):
if ord(s[i]) < 32 or ord(s[i]) > 126:
return False
return True
with open('RSA_Worst_Joke/public.pem', 'r') as f:
pub_data = f.read()
pubkey = RSA.importKey(pub_data)
p = pubkey.n
e = pubkey.e
with open('RSA_Worst_Joke/flag.enc', 'r') as f:
c = int(f.read().decode('base64').encode('hex'), 16)
for q in range(50):
if is_prime(q):
n = p * q
phi = (p - 1) * (q - 1)
x = 0
while True:
if (phi * x + 1) % e == 0:
d = (phi * x + 1) / e
break
x = x + 1
m = pow(c, d, n)
hex_flag = '%x' % m
if len(hex_flag) % 2 == 1:
hex_flag = '0' + hex_flag
flag = hex_flag.decode('hex')
if is_printable(flag):
print 'q =', q
print flag
実行結果は以下の通り。
q = 47
The empire secret system has been exposed ! The top secret flag is : Flag{S1nGL3_PR1m3_M0duLUs_ATT4cK_TaK3d_D0wn_RSA_T0_A_Sym3tr1c_ALg0r1thm}
Flag{S1nGL3_PR1m3_M0duLUs_ATT4cK_TaK3d_D0wn_RSA_T0_A_Sym3tr1c_ALg0r1thm}
Improve the quality (Crypto 800)
decription.txtには以下のように記載されている。
Hello Every one,
We didn't know what to do, so we are asking for your help.
A friend of us sent us the following text:
I used an elliptic curve encrytion for the first time.
The only thing that i kown about elliptic curve is that a number K must always be hidden.
so i made multiple encryption to send some information.
Here is all the informations about the elliptic curve that i used excep the K number.
The elliptic curve is :
y^2 = x^3 + A*x + B
A = 658974
Sorry i forget the B :/ , I just remember that it's most significant number is 6
As an order of a finite field must be a prime power, i used p = 962280654317 (FiniteField(p)).
as a starter point, i used the generator G for this elliptic curve: (518459267012 : 339109212996 : 1)
and each time i reuse it to encrypt again
let my secret message be K .
for exemple I divided my K to 2 elements k1 and k2
then Q1 is k1*G
and Q2 is k2*G
here are the Qi that i got:
[(656055339629 : 670956206845 : 1),
(714432985374 : 30697818482 : 1),
(519532969453 : 833497145865 : 1),
(606806384185 : 353033449641 : 1),
(370553209582 : 211121736115 : 1),
(95617246846 : 666814491609 : 1),
(474872055371 : 795112698430 : 1),
(249845085299 : 222352033875 : 1),
(850954431245 : 810446463695 : 1),
(188731559428 : 877002121896 : 1),
(168665615402 : 464872506873 : 1),
(26722558561 : 269217869309 : 1),
(16403346294 : 478534963882 : 1),
(539749282946 : 332444159141 : 1),
(932295517649 : 23439478940 : 1),
(765194933041 : 920187938377 : 1),
(853124087439 : 845601917928 : 1),
(246454416048 : 212483699689 : 1),
(312547608490 : 688107262695 : 1),
(43261158649 : 439444472742 : 1),
(320785434805 : 477080449838 : 1),
(741706320740 : 672809544395 : 1),
(361762297756 : 858805805323 : 1),
(782235980044 : 600673464737 : 1),
(69196762074 : 327427680437 : 1),
(876001563166 : 573218279075 : 1),
(117946101727 : 954797129239 : 1),
(771781111553 : 314018907599 : 1),
(579549799021 : 322325160055 : 1),
(857081196493 : 464260539273 : 1),
(852938568103 : 429083796488 : 1),
(850954431245 : 810446463695 : 1),
(55203632714 : 255470537391 : 1),
(600464434215 : 605840305721 : 1),
(620532163623 : 575613893944 : 1),
(215810002861 : 481354983411 : 1),
(538481263994 : 666638294130 : 1),
(528666082457 : 895034116069 : 1),
(296218553972 : 899557390183 : 1),
(428618251485 : 445768511836 : 1),
(632412058600 : 685699421425 : 1),
(634041855232 : 495546745721 : 1),
(570481762204 : 252944477333 : 1),
(760959783781 : 435626456209 : 1)]
y^2 = x^3 + a*x + b mod n
→b = y^2 - x^3 - a*x mod n
この場合は以下の文字になるので、まずはBを求める。
a -> A
b -> B
n -> p
p = 962280654317
A = 658974
G = (518459267012, 339109212996)
x = G[0]
y = G[1]
B = (pow(y, 2) - pow(x, 3) - A * x) % p
print 'B =', B
B = 618
Bの値はわかったので、Pohlig–Hellman algorithmを使って、k1から順番に求める。その値を見ながらメッセージになるようASCIIコード(10進数)として2桁ずつ読み込む。
コードは以下の通り。
p = 962280654317
A = 658974
B = 618
G = (518459267012, 339109212996)
Q = [(656055339629, 670956206845),
(714432985374, 30697818482),
(519532969453, 833497145865),
(606806384185, 353033449641),
(370553209582, 211121736115),
(95617246846, 666814491609),
(474872055371, 795112698430),
(249845085299, 222352033875),
(850954431245, 810446463695),
(188731559428, 877002121896),
(168665615402, 464872506873),
(26722558561, 269217869309),
(16403346294, 478534963882),
(539749282946, 332444159141),
(932295517649, 23439478940),
(765194933041, 920187938377),
(853124087439, 845601917928),
(246454416048, 212483699689),
(312547608490, 688107262695),
(43261158649, 439444472742),
(320785434805, 477080449838),
(741706320740, 672809544395),
(361762297756, 858805805323),
(782235980044, 600673464737),
(69196762074, 327427680437),
(876001563166, 573218279075),
(117946101727, 954797129239),
(771781111553, 314018907599),
(579549799021, 322325160055),
(857081196493, 464260539273),
(852938568103, 429083796488),
(850954431245, 810446463695),
(55203632714, 255470537391),
(600464434215, 605840305721),
(620532163623, 575613893944),
(215810002861, 481354983411),
(538481263994, 666638294130),
(528666082457, 895034116069),
(296218553972, 899557390183),
(428618251485, 445768511836),
(632412058600, 685699421425),
(634041855232, 495546745721),
(570481762204, 252944477333),
(760959783781, 435626456209)]
F = FiniteField(p)
E = EllipticCurve(F, [A,B])
G = E.point(G)
factors, exponents = zip(*factor(E.order()))
primes = [factors[i] ^ exponents[i] for i in range(len(factors))]
str_num = ''
for i in range(len(Q)):
dlogs = []
for fac in primes:
t = int(G.order()) / int(fac)
dlog = discrete_log(t*E.point(Q[i]), t*G, operation='+')
dlogs += [dlog]
k = crt(dlogs, primes)
print k
str_num += str(k)
msg = ''
for i in range(0, len(str_num), 2):
msg += chr(int(str_num[i:i+2]))
print msg
実行結果は以下の通り。
CONVERT THIS TO LOWER CASE FIRST :
THIS IMAGE CONTAINS THE FLAG, TRY TO GET IT
THE SUBMITTED FLAG MUST BE IN THIS FORMAT:
FLAG-EC[WHAT YOU'LL FIND IN THE IMAGE]
IMAGE URL:
HTTP://CRYPTO.CTFSECURINETS.COM/1/STEG-PART.PNG
上記で大文字、小文字が関係するところは小文字にする。
http://crypto.ctfsecurinets.com/1/steg-part.pngのファイルを見たら、フラグが書いてあった。
flag-ec[EC_St!e-g1(a)no]
