Skip to content

Instantly share code, notes, and snippets.

@JuliaPoo

JuliaPoo/Hackbash 2024 Training Challenge Solutions - Jules.ipynb

Created March 11, 2024 03:26
Show Gist options
  • Save JuliaPoo/e2315c8bd263c8d1d29d04696bc94711 to your computer and use it in GitHub Desktop.
Save JuliaPoo/e2315c8bd263c8d1d29d04696bc94711 to your computer and use it in GitHub Desktop.
Download ZIP
Hackbash 2024 Training Challenge Solutions - Jules
Display the source blob
Display the rendered blob
Raw
Hackbash 2024 Training Challenge Solutions - Jules.ipynb
{
"cells": [
{
"cell_type": "markdown",
"id": "15435831",
"metadata": {},
"source": [
"# Asymmetric Ciphers - Weird Prime Generation\n",
"\n",
"Author: Jules"
]
},
{
"cell_type": "markdown",
"id": "e84b3e7c",
"metadata": {},
"source": [
"## Challenge File"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "32bde4eb",
"metadata": {},
"outputs": [],
"source": [
"from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime, isPrime\n",
"import random\n",
"\n",
"e = 0x10001\n",
"\n",
"flag = b\"flag{XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX}\"\n",
"flag += (128 - len(flag)) * b\"\\xfe\"\n",
"m = bytes_to_long(flag)\n",
"\n",
"prime_pool = [getPrime(512) for _ in range(100)]\n",
"ns, cs = [], []\n",
"for _ in range(12):\n",
" i,j = random.randint(0,99), random.randint(0,99)\n",
" p,q = prime_pool[i], prime_pool[j]\n",
" n = p*q\n",
" c = pow(m, e, n)\n",
" ns.append(n), cs.append(c)\n",
" \n",
"print(\"ns =\", ns)\n",
"print(\"cs =\", cs)\n",
"# ns = [115641056846455972041580910058788571106267762146826701440167610652756301162757603339591932359133673630769463128111516027845797060766642512576605043516162066685762400258977477588147426327479898350524009677087742239805803037949675221368764583197392955053924317962785480020086196285819293532772652095837977625527, 115306186394142656571245840342113676710496189429342634665044052302056698985637627964614094161160205001043610584537738300891018914343357952628583675114971788123033431200781510767176814914346265868845468880832496660320184360965513994421378298950368815275542734751289433111973786169737358055060003761801477879017, 127133293304022566519674742296096024681010395128559139652590611223375565931751496177088031514201938210974807972683167474153479293458770920979364262201663122992166918921371887187988255033324266657891814956400000486228333703955817200546042999551023548422900500145221018070674842336888990664618824028047213976233, 143288862056979321081104218540581099766309051494861856523872952892347012363601483252385194427745175760230994293032241190697815692960618393577820913010073835103168758828556886318989352692900953058283718981307794270274314687276694475283229710870764842264694827904770938241440800286478854209793420791237001183047, 148271362517171391698300566508903241271035368616957036162999625044712523480212636207411855320759257788966345192295098828451866182179767194040596237490232715434023576051082166412051827838258036637546099755991794525882074133101922710591978613930777717337337043902278331130254366312739316767969140957830179497649, 46948286205191528300750551703486658468835222211998262085945354809055208962645340774807744432826691736284128563552764053951450276857586416809302853843085739000920684948344344906827533861700331248068069812394622505656160226766451999951188672305574204213023950279013811842976235568539234319273467929102373335951, 93874368205746970354007744261304523378522953891751677041466486550083669525058773586269614953018803999996213710072958398427348326208354236449620862509721222963984475559044695479393235537093474935912779171621361304825120910111202542899454057185426495233493174474496752592055472395378657364429145801083394033233, 83120251934517766228228566911354657390536990677362157443027757336993898207799261269768565759975791856152817556751946140599751236769200376779462404676963694713746403211070555782044442230191172254267805136257190436528912035027441964046587815829859552233658658069859621581418337149457860940013230047967364653637, 75125428758316819970265608079756035785634945147971064921430505635309578370900741939574987046472341215493883527084322367116527230918813980231569750837476612170680688465357070160805638467354835435231993017910377610220448370353928377287718691411628730666889105122637983149663648586442046881594376843365555610373, 93885747229946868470804484720063117037231479871689132766177754587772397215827395083949189572455570837999104272809367194243695906075873058345366717589642543933027516079095231332310268883844119986948926142341950474718940163429112854705103519320741676297857578446950975723776948778805306939280855934960383864481, 93159733149519219861469573229705094654389151822016299979043226740893551683167043351637604156639623673443838636161493332516920159383892191697162250131735840077185137616335836900081507100229649907638013716217355976541009858684397186045839706734777653015832145194392667917112119395355222813800365927761231115117, 125760469735883528418186599919274100965838726128568287972605851797005896888191045744170365060297409566584569043065191498692305297811021004323378633856836058780321869088893091080241136909875088356268488798671598970207774651938786924993197784886279200719545424116510776861811746493216454981376487799730277004919]\n",
"# cs = [29211141025281378814750464133646009333317281612638600549183697893972372814144692553229486780956908929079448299318665141640210664689647755789948911400438263621728751448690406885045351082354085766284908645711944954656395854561029995371471131033536876401407878817935675971125583344720778820344053851319122587911, 10508622343508790435130348307299867325545819141465194036502607054604735736027017207459025390740193557256529377516372440560073827723762600481794162275330166430322358854489807837791244498213521993764426054439128537744540826611422187044769651867773695945370561563111173197862108490612139524097466841666412622374, 58159082857504357527388848526435107831435712256601132318323113349330481036476149722145518786555411754825645600986572402508976869682835534184854941014897622539850623566444487629080136084260768243061959379543843869211558165877016817897372584985441763988315686002104823427189490957211909716190882376508337390522, 134208623939387928441655120898217043819319758788787167543909572891879172129982542940068708032722933058862462913580677502958562054762854307226183944757133371140334015498882772507265578945714924530560172540910458846566238852825814539680437008646817942730108863687697372535900452856746046155459916014877382704139, 52152091976888036635166713944541596262473043611630591201091841068963186035735613199794305724876329564074293050475091338111203222061054758058763334768950027088072886661859473164990817568559923411208899643837453220731293563969913653888795919900512160745990805425257336004482392365524187135982459500976110164284, 2191940651459376161612049054906551848787925348335594541981566622488661841290093825127573090611791027572484483671395453902164434732408211369509160483430942997201751393280357979975101670158574456951152500791462843720238697336461048936918193859283628653558516819240267870990182443479255014451758100166236964037, 45452718793025484873293735987043487162105576875111865714171455230160965304726087746739665352275114538125115086839863275326328349748223804559901387548450361068108627735671747652189438882535574296112592027838881580601621061189650707565560765164921489534988454406553800328832600227758114136964516354879255003127, 19732966941142952790543543998975761951116185335231402280920578531142050458339828932497509685341339905949398063525689111513680767687471759058414318841042524242786696613919098423371418773716105365195799779269744328217934011592099366142602320396815286613015615335561116457133753440054633085755556240741616905238, 41011809208251571526963965206444968455478668546456566762679437955779969092183036332335892156896224868651465936442726603226308578130868634040287174718046601546292001666472148782024373784832587116644794171483311071152559621755949325383878635894013649722186376898796236989584685137796735480450809161522836440819, 50287302376988054827274133464373378602542103812978482587299447036965724249411626238450468046608326805517546264515893352074608858684643804444626255282461335896939376899630293326171546033632154828003493468965688686207594939641807428354001313953340335723917038462598946476546406403069564891092317503175377354290, 4393167213080179301104107768357617112316544034154682857717269550375344981364388677299910417848041833268325062034414236080963730390871640938096611853561293665742445303589779256462290686191925916178438683095907790338924880453972168458672114548211729000682003881476489306052897401920197921944258438355880162642, 99872358189751859456464258885959795072114971343050409823935478674214362685502670423183624997480056574742243044219122130894662766629445618944062304182623832815428971174151955217356379033071444929116972647699876027725831844515167317573335269122363716018945005225929141687486351100245394684034945466907827580605]"
]
},
{
"cell_type": "markdown",
"id": "a12290e1",
"metadata": {},
"source": [
"## Solution\n",
"\n",
"This challenge is inspired by a [real life attack](https://eprint.iacr.org/2012/064.pdf) plaguing RSA private keys in the wild, where two public modulus might share the same factor.\n",
"\n",
"The challenge generates a pool (`prime_pool`) of $100$ primes, and encrypts the flag $12$ times, producing ciphertexts $c_i, 1 <= i <= 12$. Each time, the challenge generates the public key $n_i, 1 <= i <= 12$ by choosing primes $p,q$ randomly from `prime_pool` and computing $n_i = pq$\n",
"\n",
"The key insight is that there is a fairly high probability that for two of public keys (call them $n_i$, $n_j$), it $n_i$ and $n_j$ chose the same prime $p$. This means that $gcd(n_i, n_j) = p \\ne 1$. We can then factor $n_i$ by computing $q = \\frac{n_i}{p}$ so $pq = n_i$.\n",
"\n",
"While factoring a large integer is generally pretty hard, computing the [**Greatest Common Divisor**](https://en.wikipedia.org/wiki/Greatest_common_divisor) between two large integers is really fast.\n",
"\n",
"So all we have to do to factor one of the $n_i$ is to compute the $gcd$ of all possible pairs of public keys."
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "c67d533e",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"flag{aww_i_was_just_tryna_save_time}\n"
]
}
],
"source": [
"from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime, isPrime\n",
"from itertools import combinations\n",
"from math import gcd\n",
"\n",
"ns = [115641056846455972041580910058788571106267762146826701440167610652756301162757603339591932359133673630769463128111516027845797060766642512576605043516162066685762400258977477588147426327479898350524009677087742239805803037949675221368764583197392955053924317962785480020086196285819293532772652095837977625527, 115306186394142656571245840342113676710496189429342634665044052302056698985637627964614094161160205001043610584537738300891018914343357952628583675114971788123033431200781510767176814914346265868845468880832496660320184360965513994421378298950368815275542734751289433111973786169737358055060003761801477879017, 127133293304022566519674742296096024681010395128559139652590611223375565931751496177088031514201938210974807972683167474153479293458770920979364262201663122992166918921371887187988255033324266657891814956400000486228333703955817200546042999551023548422900500145221018070674842336888990664618824028047213976233, 143288862056979321081104218540581099766309051494861856523872952892347012363601483252385194427745175760230994293032241190697815692960618393577820913010073835103168758828556886318989352692900953058283718981307794270274314687276694475283229710870764842264694827904770938241440800286478854209793420791237001183047, 148271362517171391698300566508903241271035368616957036162999625044712523480212636207411855320759257788966345192295098828451866182179767194040596237490232715434023576051082166412051827838258036637546099755991794525882074133101922710591978613930777717337337043902278331130254366312739316767969140957830179497649, 46948286205191528300750551703486658468835222211998262085945354809055208962645340774807744432826691736284128563552764053951450276857586416809302853843085739000920684948344344906827533861700331248068069812394622505656160226766451999951188672305574204213023950279013811842976235568539234319273467929102373335951, 93874368205746970354007744261304523378522953891751677041466486550083669525058773586269614953018803999996213710072958398427348326208354236449620862509721222963984475559044695479393235537093474935912779171621361304825120910111202542899454057185426495233493174474496752592055472395378657364429145801083394033233, 83120251934517766228228566911354657390536990677362157443027757336993898207799261269768565759975791856152817556751946140599751236769200376779462404676963694713746403211070555782044442230191172254267805136257190436528912035027441964046587815829859552233658658069859621581418337149457860940013230047967364653637, 75125428758316819970265608079756035785634945147971064921430505635309578370900741939574987046472341215493883527084322367116527230918813980231569750837476612170680688465357070160805638467354835435231993017910377610220448370353928377287718691411628730666889105122637983149663648586442046881594376843365555610373, 93885747229946868470804484720063117037231479871689132766177754587772397215827395083949189572455570837999104272809367194243695906075873058345366717589642543933027516079095231332310268883844119986948926142341950474718940163429112854705103519320741676297857578446950975723776948778805306939280855934960383864481, 93159733149519219861469573229705094654389151822016299979043226740893551683167043351637604156639623673443838636161493332516920159383892191697162250131735840077185137616335836900081507100229649907638013716217355976541009858684397186045839706734777653015832145194392667917112119395355222813800365927761231115117, 125760469735883528418186599919274100965838726128568287972605851797005896888191045744170365060297409566584569043065191498692305297811021004323378633856836058780321869088893091080241136909875088356268488798671598970207774651938786924993197784886279200719545424116510776861811746493216454981376487799730277004919]\n",
"cs = [29211141025281378814750464133646009333317281612638600549183697893972372814144692553229486780956908929079448299318665141640210664689647755789948911400438263621728751448690406885045351082354085766284908645711944954656395854561029995371471131033536876401407878817935675971125583344720778820344053851319122587911, 10508622343508790435130348307299867325545819141465194036502607054604735736027017207459025390740193557256529377516372440560073827723762600481794162275330166430322358854489807837791244498213521993764426054439128537744540826611422187044769651867773695945370561563111173197862108490612139524097466841666412622374, 58159082857504357527388848526435107831435712256601132318323113349330481036476149722145518786555411754825645600986572402508976869682835534184854941014897622539850623566444487629080136084260768243061959379543843869211558165877016817897372584985441763988315686002104823427189490957211909716190882376508337390522, 134208623939387928441655120898217043819319758788787167543909572891879172129982542940068708032722933058862462913580677502958562054762854307226183944757133371140334015498882772507265578945714924530560172540910458846566238852825814539680437008646817942730108863687697372535900452856746046155459916014877382704139, 52152091976888036635166713944541596262473043611630591201091841068963186035735613199794305724876329564074293050475091338111203222061054758058763334768950027088072886661859473164990817568559923411208899643837453220731293563969913653888795919900512160745990805425257336004482392365524187135982459500976110164284, 2191940651459376161612049054906551848787925348335594541981566622488661841290093825127573090611791027572484483671395453902164434732408211369509160483430942997201751393280357979975101670158574456951152500791462843720238697336461048936918193859283628653558516819240267870990182443479255014451758100166236964037, 45452718793025484873293735987043487162105576875111865714171455230160965304726087746739665352275114538125115086839863275326328349748223804559901387548450361068108627735671747652189438882535574296112592027838881580601621061189650707565560765164921489534988454406553800328832600227758114136964516354879255003127, 19732966941142952790543543998975761951116185335231402280920578531142050458339828932497509685341339905949398063525689111513680767687471759058414318841042524242786696613919098423371418773716105365195799779269744328217934011592099366142602320396815286613015615335561116457133753440054633085755556240741616905238, 41011809208251571526963965206444968455478668546456566762679437955779969092183036332335892156896224868651465936442726603226308578130868634040287174718046601546292001666472148782024373784832587116644794171483311071152559621755949325383878635894013649722186376898796236989584685137796735480450809161522836440819, 50287302376988054827274133464373378602542103812978482587299447036965724249411626238450468046608326805517546264515893352074608858684643804444626255282461335896939376899630293326171546033632154828003493468965688686207594939641807428354001313953340335723917038462598946476546406403069564891092317503175377354290, 4393167213080179301104107768357617112316544034154682857717269550375344981364388677299910417848041833268325062034414236080963730390871640938096611853561293665742445303589779256462290686191925916178438683095907790338924880453972168458672114548211729000682003881476489306052897401920197921944258438355880162642, 99872358189751859456464258885959795072114971343050409823935478674214362685502670423183624997480056574742243044219122130894662766629445618944062304182623832815428971174151955217356379033071444929116972647699876027725831844515167317573335269122363716018945005225929141687486351100245394684034945466907827580605]\n",
"e = 65537\n",
"\n",
"for (n1,c1),(n2,c2) in combinations(zip(ns,cs), 2):\n",
" g = gcd(n1,n2)\n",
" if g != 1: break\n",
" \n",
"p,q = g, n1//g\n",
"d = pow(e, -1, (p-1)*(q-1))\n",
"m = pow(c1, d, n1)\n",
"print(long_to_bytes(m).strip(b\"\\xfe\").decode())"
]
},
{
"cell_type": "markdown",
"id": "2ff6626f",
"metadata": {},
"source": [
"# Asymmetric Ciphers - DES Weak Keys\n",
"\n",
"Author: Jules"
]
},
{
"cell_type": "markdown",
"id": "89382a10",
"metadata": {},
"source": [
"## Challenge File"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "bc51df85",
"metadata": {},
"outputs": [],
"source": [
"from Crypto.Cipher import DES\n",
"\n",
"def encrypt(key:bytes, plaintext:bytes) -> (bytes, bytes):\n",
" k1, k2 = key[:8], key[8:]\n",
" cipher1 = DES.new(k1, DES.MODE_ECB)\n",
" cipher2 = DES.new(k2, DES.MODE_ECB)\n",
" peek = cipher1.encrypt(m)\n",
" return cipher2.encrypt(peek), peek\n",
"\n",
"flag = b'flag{XXXXXXXXXXXXXXXXXXXXXXXXXXX}' # OMITTED HAHAHA\n",
"m = flag + b\"\\0\" * ((-len(flag)) % 8)\n",
"\n",
"key = b'XXXXXXXXXXXXXXXX' # OMITTED HAHAHA\n",
"c, peek = encrypt(key, m)\n",
"assert m == c\n",
"\n",
"print(\"peek =\", peek.hex())\n",
"# peek = 7dd4f19ad6b80c973209e59d862094348d855f4259a430a0b9008cf9b24ce9295206b6bd9ec4d2a4"
]
},
{
"cell_type": "markdown",
"id": "1af818a0",
"metadata": {},
"source": [
"## Solution\n",
"\n",
"If you are to search `DES Weak Keys` on google, you'd encounter this wikipeida [article](https://en.wikipedia.org/wiki/Weak_key#Weak_keys_in_DES). In it, it mentions _weak keys_ and _semi weak keys_.\n",
"\n",
"Let $E_k(m)$ denote encryption of message $m$ with key $k$. Let $D_k(m)$ denote decryption of message $m$ with key $k$. Then from the wikipedia article, you'd have gained:\n",
"\n",
"- _weak keys_: For a weak key $k$, encryption is equivalent to decryption, i.e., $E_k (E_k (m)) = m$\n",
"- _semi weak keys_: Semi weak keys come in pairs $k_1$, $k_2$ such that $E_{k_2} (E_{k_1} (m)) = m$\n",
"\n",
"Furthermore, the wikipedia article also lists all the weak and semi weak keys of DES.\n",
"\n",
"Now, the challenge encrypts the flag $m$ with two keys $k_1$, $k_2$ in the following way: \n",
"$$\n",
"c = E_{k_2} (E_{k_1} (m))\n",
"$$\n",
"\n",
"Furthermore, we are given that $c = m$, and $\\text{peek} = E_{k_1}(m)$. One can hence reason that one of the following two cases has happened:\n",
"\n",
"1. $k_1 = k_2$ and $k_1$ is a _weak key_. Then $m = D_{k_1}(\\text{peek})$.\n",
"2. $k_1, k_2$ are pairs of _semi weak keys_. Then $m = D_{k_1}(\\text{peek})$\n",
"\n",
"Therefore, it suffices to collect all possible weak and semi weak keys of DES $k$, and computing $D_k(\\text{peek})$.\n",
"\n",
"**Note**: The wikipedia gives the keys in hex format, you'd have to convert them to bytes."
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "1016cccf",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"flag{why_are_these_keys_so_weak?}\u0000\u0000\u0000\u0000\u0000\u0000\u0000\n"
]
}
],
"source": [
"from Crypto.Cipher import DES\n",
"\n",
"peek = bytes.fromhex('7dd4f19ad6b80c973209e59d862094348d855f4259a430a0b9008cf9b24ce9295206b6bd9ec4d2a4')\n",
"\n",
"weak_keys = [\n",
" 0x0101010101010101, 0x1010101010101010,\n",
" 0xFEFEFEFEFEFEFEFE, 0xEFEFEFEFEFEFEFEF,\n",
" 0xE0E0E0E0F1F1F1F1,\n",
" 0x1F1F1F1F0E0E0E0E,\n",
" 0x0000000000000000,\n",
" 0xFFFFFFFFFFFFFFFF,\n",
" 0xE1E1E1E1F0F0F0F0,\n",
" 0x1E1E1E1E0F0F0F0F,\n",
"]\n",
"\n",
"semiweak_keys = [\n",
" 0x011F011F010E010E, 0x1F011F010E010E01,\n",
" 0x01E001E001F101F1, 0xE001E001F101F101,\n",
" 0x01FE01FE01FE01FE, 0xFE01FE01FE01FE01,\n",
" 0x1FE01FE00EF10EF1, 0xE01FE01FF10EF10E,\n",
" 0x1FFE1FFE0EFE0EFE, 0xFE1FFE1FFE0EFE0E,\n",
" 0xE0FEE0FEF1FEF1FE, 0xFEE0FEE0FEF1FEF1,\n",
"]\n",
"\n",
"for k in weak_keys + semiweak_keys:\n",
" k = k.to_bytes(8, 'big')\n",
" m = DES.new(k, DES.MODE_ECB).encrypt(peek)\n",
" if b\"flag\" in m:\n",
" print(m.decode())"
]
},
{
"cell_type": "markdown",
"id": "a8134347",
"metadata": {},
"source": [
"# Asymmetric Ciphers - Small Message Again\n",
"\n",
"Author: Jules"
]
},
{
"cell_type": "markdown",
"id": "9bbd6734",
"metadata": {},
"source": [
"## Challenge File"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "82ec0d7a",
"metadata": {},
"outputs": [],
"source": [
"from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime\n",
"\n",
"message = b\"XXXXXXXXXXXXXXXXXXXX\" # I replaced each character with an `X` HAHAHAHAHA\n",
"flag = \"flag{\" + message.decode() + \"}\"\n",
"m = bytes_to_long(message)\n",
"nbits = 632\n",
"p,q = getPrime(nbits), getPrime(nbits)\n",
"n = p*q\n",
"e = 8\n",
"c = pow(m, e, n)\n",
"\n",
"print(\"c =\", c)\n",
"print(\"n =\", n)\n",
"# c = 23965790658009916031696292154239687991326434808126937936323279539527574371744576958848321183942689578488108708090204264281234425279645871337130565890080553808286438515223159187176347615720948597941926154290059517927271273443279014021993150936914996059185621898372665540262508940585954336627247149084360680096370504712966571457587699331961735094863336202844831343021213343719068703\n",
"# n = 189837407291613686919566769420272986448887534101748508070907335184348859008673016485968480064813107452336510716209913153290507313137443655096566113288817486410790226639142211212337576873005124899472566893871237221782815126355733037194994994186981409359274410396627201503295100149056825213695727311814873644431153627454770965400706379939864430240987135360486090463455805641835098883"
]
},
{
"cell_type": "markdown",
"id": "83d335ea",
"metadata": {},
"source": [
"## Solution\n",
"\n",
"We are given:\n",
"- Tiny exponent $e = 8$.\n",
"- Tiny message $m$ (only $20$ chars, or $160$ bits)\n",
" - This implies $m^e$ is roughly $e \\times 160 = 1280$ bits.\n",
"- $n$ is roughly $632 \\times 2 = 1264$ bits.\n",
"\n",
"Hence, $m^e > n$ and we can't simply take $\\sqrt[e]{c}$ and call it a day. However, we can write:\n",
"\n",
"$$\n",
"m^e = c + k n\n",
"$$\n",
"\n",
"for some integer $k$. We can approximate the upper-bound of the value of $k$: \n",
"\n",
"$$\n",
"k \\le \\frac{m^e}{n} \\sim \\frac{2^{1280}}{2^{1264}} = 2^{1280 - 1264} = 2^{16}\n",
"$$\n",
"\n",
"$k$ is pretty tiny! This means all we have to do is to bruteforce tiny $k$, and compute $\\sqrt[e]{c + k n}$.\n",
"\n",
"We can implement $\\sqrt[e]{x} = \\sqrt[8]{x}$ in python as `isqrt(isqrt(isqrt(x)))`, where `isqrt` is an import from the module `math`."
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "fe5812c0",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"We need to bruteforce around 65536 possibilities.\n",
"flag{wow_the_key_is_huge!}\n"
]
}
],
"source": [
"message = b\"XXXXXXXXXXXXXXXXXXXX\"\n",
"e = 8\n",
"c = 23965790658009916031696292154239687991326434808126937936323279539527574371744576958848321183942689578488108708090204264281234425279645871337130565890080553808286438515223159187176347615720948597941926154290059517927271273443279014021993150936914996059185621898372665540262508940585954336627247149084360680096370504712966571457587699331961735094863336202844831343021213343719068703\n",
"n = 189837407291613686919566769420272986448887534101748508070907335184348859008673016485968480064813107452336510716209913153290507313137443655096566113288817486410790226639142211212337576873005124899472566893871237221782815126355733037194994994186981409359274410396627201503295100149056825213695727311814873644431153627454770965400706379939864430240987135360486090463455805641835098883\n",
"\n",
"from math import isqrt\n",
"import string\n",
"\n",
"max_bruteforce = 1 << (len(message)*8*e - n.bit_length())\n",
"print(f\"We need to bruteforce around {max_bruteforce} possibilities.\")\n",
"\n",
"for i in range(max_bruteforce):\n",
" m = isqrt(isqrt(isqrt(c + n * i)))\n",
" m = long_to_bytes(m)\n",
" try: \n",
" m.decode()\n",
" break\n",
" except: pass\n",
" \n",
"flag = \"flag{\" + m.decode() + \"}\"\n",
"\n",
"print(flag)"
]
},
{
"cell_type": "markdown",
"id": "8db4a0ef",
"metadata": {},
"source": [
"# Asymmetric Ciphers - RSA Different Exponents\n",
"\n",
"Author: Jules"
]
},
{
"cell_type": "markdown",
"id": "1c61ef63",
"metadata": {},
"source": [
"## Challenge File"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "4b5c9e52",
"metadata": {},
"outputs": [],
"source": [
"from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime\n",
"\n",
"flag = \"flag{XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX}\"\n",
"flag = flag.encode()\n",
"flag += (128 - len(flag)) * b\"\\xfe\"\n",
"m = bytes_to_long(flag)\n",
"p,q = getPrime(512), getPrime(512)\n",
"n = p*q\n",
"\n",
"e1 = 65537\n",
"e2 = 65535\n",
"c1 = pow(m, e1, n)\n",
"c2 = pow(m, e2, n)\n",
"\n",
"print(\"c1 =\", c1)\n",
"print(\"c2 =\", c2)\n",
"print(\"n =\", n)\n",
"# c1 = 57576421921329359882210075590816676710304346949975382238994271927770832252713290614991357107031340919814972019433190753833591828944539089456349817331681032738353511384554741260139743102216557092417167001701115337752709734708422751343051475020635607732427676252058128731753389548565382099634409802943671930845\n",
"# c2 = 64510543795466649991723004002162538032648776847385366201982025607931103839166464682878922600039791044865168146992842739945001720272393623001330060753106834593920507761561069093832675358103414080201716879554351626465084950343675275891715005743127118933743366498522862088770663809048507715825815027152191238110\n",
"# n = 90049837223316610102220046539784857746465111483217133962369907717666214142893158736821702145720455536994831424211430647483851034847327353552367905452764521882800296610826293260979140254898973449089206530668173893937824445602837062664620242123775857496420982568030035661191235022771303550302949536869831182503"
]
},
{
"cell_type": "markdown",
"id": "0457d419",
"metadata": {},
"source": [
"## Solution\n",
"\n",
"We are given two encryptions $c_1, c_2$ of the same message $m$ (the flag), with the same modulus $n$ but different exponents $e_1, e_2$. We can write $c_1, c_2$ as follows:\n",
"\n",
"$$\n",
"c_1 = m^{e_1} \\mod n \\\\\n",
"c_2 = m^{e_2} \\mod n\n",
"$$\n",
"\n",
"Our goal is to recover $m$. Note that for any integers $x,y$,\n",
"\n",
"$$\n",
"c_1^x c_2^y = m^{x e_1} m^{y e_2} = m^{x e_1 + y e_2} \\mod n\n",
"$$\n",
"\n",
"Now, the question is, is it possible to find $x$ and $y$ such that $x e_1 + y e_2 = 1$? Finding such $x,y$ would give:\n",
"\n",
"$$\n",
"c_1^x c_2^y = m^{x e_1 + y e_2} = m^1 = m \\mod n\n",
"$$\n",
"\n",
"and hence recovers $m$. The answer is yes, iff $\\gcd(e_1, e_2) = 1$. Finding such $x,y$ can be done via the [**Extended Euclid's Algorithm**](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm) of which you can find countless implementations of online."
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "93add5c6",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"flag{this_is_why_e_is_usually_always_65537}\n"
]
}
],
"source": [
"c1 = 57576421921329359882210075590816676710304346949975382238994271927770832252713290614991357107031340919814972019433190753833591828944539089456349817331681032738353511384554741260139743102216557092417167001701115337752709734708422751343051475020635607732427676252058128731753389548565382099634409802943671930845\n",
"c2 = 64510543795466649991723004002162538032648776847385366201982025607931103839166464682878922600039791044865168146992842739945001720272393623001330060753106834593920507761561069093832675358103414080201716879554351626465084950343675275891715005743127118933743366498522862088770663809048507715825815027152191238110\n",
"n = 90049837223316610102220046539784857746465111483217133962369907717666214142893158736821702145720455536994831424211430647483851034847327353552367905452764521882800296610826293260979140254898973449089206530668173893937824445602837062664620242123775857496420982568030035661191235022771303550302949536869831182503\n",
"e1 = 65537\n",
"e2 = 65535\n",
"\n",
"def egcd(a, b):\n",
" \"\"\"\n",
" Implements the extended euclid algorithm.\n",
" Returns (g, x, y), where\n",
" - g = gcd(a,b)\n",
" - x,y are integers such that g = a*x + b*y\n",
" \"\"\"\n",
" if a == 0: return (b, 0, 1)\n",
" g, x, y = egcd(b % a, a)\n",
" return (g, y - (b // a) * x, x)\n",
"\n",
"g, x, y = egcd(e1,e2)\n",
"assert g == 1\n",
"\n",
"m = (pow(c1, x, n)*pow(c2, y, n)) % n\n",
"flag = long_to_bytes(m).strip(b\"\\xfe\").decode()\n",
"\n",
"print(flag)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.8.10"
}
},
"nbformat": 4,
"nbformat_minor": 5
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment