Basic_RSA

Basic RSA:Crypto:102pts

RSA暗号の基本的な演算ができますか？
nc rsa.wanictf.org 50000

Solution

RSAの問題が出されるようだ。
一問ずつ解いていくとflagが得られた。

$ nc rsa.wanictf.org 50000

:::::::..   .::::::.   :::.
;;;;``;;;; ;;;`    `   ;;`;;
 [[[,/[[[' '[==/[[[[, ,[[ '[[,
 $$$$$$c     '''    $c$$$cc$$$c
 888b "88bo,88b    dP 888   888,
 MMMM   "W"  "YMmMY"  YMM   ""`


+================================+
| Given : p, q (512-bit integer) |
| Find  : n = p*q                |
+================================+

p = 8365915179498104979090554871625277143504992647638860176610010490541433643795389637599544880352598844673219847269106572680040563604648264721319720972098946
q = 2239017042964099417195521287943682059512294406875125570212840620940696006697447826799851640263097095601582561475204224453314432043536238230876649647842570
[n?] > 18731426666888320003750093892474188470088028912823909842799833107013303754075217745640589155708000765635366672859384914563287428023480000602423675000558663892010501448240450104693097249994858563291522753014546161146697445466095925235180722213658930080105003268501805249623212530574871358476975159433470931220
[+] Correct! Proceed to the next challenge ->



+=======================================+
| Given : m ) Message                   |
|         e ) Public exponent           |
|         n ) p*q  (p, q 512-bit prime) |
| Find  : c = m**e (mod n)              |
+=======================================+

m = 259897694808332217006897063764292467401
e = 65537
n = 68084627084922670952320931976065471752263055988406401541910377430856203068772385082055867280210343073923367519833522314457001962020958872088115809325912557005400008083647370151545248094889344121182283487253337656632807645377002683185972407788077324391582874043514008711105254511566571522893043673450100839157
[c?] > 42722326978969543982424182884339205245470354085736214724473010603037036816343797185320191516547316903875077639419487177841819467277405531496721237135620948769220355601059975864334421926326184597809405527611637363144787815044156582223660404887546678778281592055463859084324606317632508719617011653856253856467
[+] Correct! Proceed to the final challenge!



+=====================================+
| Given :  p, q ) 512-bit primes      |
|          e    ) Public exponent     |
|          c    ) Encrypted message   |
|                 = m**e (mod p*q)    |
| Find  :  m    ) Message             |
+=====================================+

p = 9554795452880463765914948873567605741025700284667822233532810675955733888377972855201338970604346299970556266847991577519399363280286780125862617335506143
q = 11569240456205043834913175759628425652017132503526236497623346027043609747733168416581608706430390998819445259561133839261163582500141601154823051022145489
e = 65537
c = 103411282804169781411109153538512467303136891644631566298401029689331513462041676872103072729281398324521924524917220946189378913279815219099581071718152740625823297701700615612909359730536838114209924264688124181681288602884650573522850028822429580113093432961260481414110973365213877814402545404936801597856
[m?] > 111607414095451345871308831002167917770
[+] Correct! Here's your reward: FLAG{y0uv3_und3rst00d_t3xtb00k_RSA}

以下のコードを用いた。
問題1

p = 8365915179498104979090554871625277143504992647638860176610010490541433643795389637599544880352598844673219847269106572680040563604648264721319720972098946
q = 2239017042964099417195521287943682059512294406875125570212840620940696006697447826799851640263097095601582561475204224453314432043536238230876649647842570
print(p*q)

$ python q1.py
18731426666888320003750093892474188470088028912823909842799833107013303754075217745640589155708000765635366672859384914563287428023480000602423675000558663892010501448240450104693097249994858563291522753014546161146697445466095925235180722213658930080105003268501805249623212530574871358476975159433470931220

問題2

m = 259897694808332217006897063764292467401
e = 65537
n = 68084627084922670952320931976065471752263055988406401541910377430856203068772385082055867280210343073923367519833522314457001962020958872088115809325912557005400008083647370151545248094889344121182283487253337656632807645377002683185972407788077324391582874043514008711105254511566571522893043673450100839157
print(m**e%n)

$ python q2.py
42722326978969543982424182884339205245470354085736214724473010603037036816343797185320191516547316903875077639419487177841819467277405531496721237135620948769220355601059975864334421926326184597809405527611637363144787815044156582223660404887546678778281592055463859084324606317632508719617011653856253856467

問題3

import gmpy2
from Crypto.PublicKey import RSA

p = 9554795452880463765914948873567605741025700284667822233532810675955733888377972855201338970604346299970556266847991577519399363280286780125862617335506143
q = 11569240456205043834913175759628425652017132503526236497623346027043609747733168416581608706430390998819445259561133839261163582500141601154823051022145489
e = 65537L
c = 103411282804169781411109153538512467303136891644631566298401029689331513462041676872103072729281398324521924524917220946189378913279815219099581071718152740625823297701700615612909359730536838114209924264688124181681288602884650573522850028822429580113093432961260481414110973365213877814402545404936801597856
n = p*q
d = lambda p, q, e: int(gmpy2.invert(e, (p-1)*(q-1)))
key = RSA.construct((n, e, d(p,q,e)))
print(key.decrypt(c))

$ python2 q3.py
111607414095451345871308831002167917770

FLAG{y0uv3_und3rst00d_t3xtb00k_RSA}