[HackingWeek 2015] [Crypto4] Write UpIntroduction
Session Start: Thu Feb 05 20:49:04 2015
Session Ident: #mastercsi
[20:49] * Now talking in #mastercsi
[20:49] * Topic is 'http://mastercsi.labri.fr/'
[20:49] * Set by admin!~admin on Sat Nov 22 00:06:50
[20:49] and I got an old RSA key that Alice used
[20:49] alice, alice's? you gotta be kidding me?
[20:49] haha no
[20:49] but there was just half, I had to complete with random values to make it work
[20:49] it seems to work anyway, if you have something to decipher...
[20:49] wait, I have her public key lying around somewhere, and even an encrypted file. I've always wondered what it was ...
[20:49] maybe it's the same key?
[20:50] I sent you the thing, take a look
[21:22] * Disconnected
Session Close: Thu Feb 05 21:22:11 2015
The validation key is the message encrypted with the private key of Alice, rebuild it using the following files:alice.pub
mykey.pem (If you have some issues trying to download this file : right click -> save as …)
secret
Resolution
First if all, we analyze the -valid- public key in order to get the Modulus (N) and the exponent (e):
$ openssl pkey -pubin -in alice.pub -text -noout
Public-Key: (1024 bit)
Modulus:
00:c6:c8:35:29:a2:38:8f:14:63:65:c5:f5:fd:4b:
0d:88:89:61:b9:5d:e1:0f:fa:88:53:a3:c2:cb:ed:
75:0e:99:59:bd:0f:f8:72:c2:23:2f:6b:ad:32:62:
4f:35:6a:82:d0:62:75:5e:1e:4f:ed:ae:54:e8:ca:
24:71:fc:8d:13:ac:70:0e:e2:57:20:d4:d9:08:9f:
d6:fb:d4:2f:12:e6:a4:1e:1c:1d:e8:1f:57:8c:32:
13:2a:d0:85:94:e8:51:84:1d:02:39:cd:41:0d:ef:
11:d1:c1:5e:e7:5b:92:f8:6a:04:f7:c6:c7:f3:6b:
90:46:b8:fb:2f:e2:95:65:b1
Exponent: 65537 (0x10001)
Next step is to check the good values into the private key:
$ openssl rsa -in mykey.pem -text -noout
Private-Key: (1024 bit)
modulus:
00:c6:c8:35:29:a2:38:8f:14:63:65:c5:f5:fd:4b:
0d:88:89:61:b9:5d:e1:0f:fa:88:53:a3:c2:cb:ed:
75:0e:99:59:bd:0f:f8:72:c2:23:2f:6b:ad:32:62:
4f:35:6a:82:d0:62:75:5e:1e:4f:ed:ae:54:e8:ca:
24:71:fc:8d:13:ac:70:0e:e2:57:20:d4:d9:08:9f:
d6:fb:d4:2f:12:e6:a4:1e:1c:1d:e8:1f:57:8c:32:
13:2a:d0:85:94:e8:51:84:1d:02:39:cd:41:0d:ef:
11:d1:c1:5e:e7:5b:92:f8:6a:04:f7:c6:c7:f3:6b:
90:46:b8:fb:2f:e2:95:65:b1
publicExponent: 3 (0x3)
privateExponent:
00:84:85:78:c6:6c:25:b4:b8:42:43:d9:4e:a8:dc:
b3:b0:5b:96:7b:93:eb:5f:fc:5a:e2:6d:2c:87:f3:
a3:5f:10:e6:7e:0a:a5:a1:d6:c2:1f:9d:1e:21:96:
df:78:f1:ac:8a:ec:4e:3e:be:df:f3:c9:8d:f0:86:
c2:f6:a8:5e:0b:ef:c0:ca:19:c5:e2:49:55:49:fe:
e5:2e:51:3e:7b:e9:f2:22:07:d2:4b:84:7f:bb:0c:
b5:ba:b7:95:c6:90:05:3e:65:2d:11:53:9a:2d:96:
0f:ea:de:cb:9b:17:54:87:00:0f:78:12:ce:ac:f5:
db:83:30:16:06:cc:35:7d:a3
prime1: 245 (0xf5)
prime2: 207 (0xcf)
exponent1: 163 (0xa3)
exponent2: 138 (0x8a)
coefficient: 189 (0xbd)
As we can see :
The modulus (N) is the same as the public key : OK
The publicExponent (e) should be 65537, like the public key : NOK
The privateExponent (d) seems to be a correct value : OK?
All the others values are wrong.
Let’s transform all hex values into a decimal format :
For the modulus (N):
$ python -c "print int('00c6c83529a2388f146365c5f5fd4b0d888961b95de10ffa8853a3c2cbed750e9959bd0ff872c2232f6bad32624f356a82d062755e1e4fedae54e8ca2471fc8d13ac700ee25720d4d9089fd6fbd42f12e6a41e1c1de81f578c32132ad08594e851841d0239cd410def11d1c15ee75b92f86a04f7c6c7f36b9046b8fb2fe29565b1', 16)"
139589510448559426270140350106792398328403552834675368794733962561525914206396716036189393374294367303846992780695341826824306948258043034537162671328717852010658546072889560963675752283945322326005793726927254786393742142055806404861768824642002369852610966461772991591954263592365958281593575065087653537201
For the privateExponent (d):
$ python -c "print int('00848578c66c25b4b84243d94ea8dcb3b05b967b93eb5ffc5ae26d2c87f3a35f10e67e0aa5a1d6c21f9d1e2196df78f1ac8aec4e3ebedff3c98df086c2f6a85e0befc0ca19c5e2495549fee52e513e7be9f22207d24b847fbb0cb5bab795c690053e652d11539a2d960feadecb9b175487000f7812ceacf5db83301606cc357da3', 16)"
93059673632372950846760233404528265552269035223116912529822641707683942804264477357459595582862911535897995187130227884549537965505362023024775114219145218863449310278405967527628414837264004662699074903716560546461614167980089864300514695266151435327524971233343815264097726955869839543417933242229553724835
For prime1 (p):
$ python -c "print int('00f5a798bad756b8ee9b4e3a91fe1cafd7ffad5770377af0156c23c64d407f92dbe24a92ae7427fd7eb18c620341a17dc7670986ee676e17d99d497bcfea0b9ec3', 16)"
12865979254173524318205154356956226942340819748396485453570850199275733851574194544096345303446141207553525448737577133880210914025405392588238363787239107
For prime2 (q = N/p):
$ python -c "print int('00cf274700d6f6adea7e5344a45c34a92fb93db8f23f5da7de32decc6fe46b7d6dc43aabf15bb1cc0f4865112a3d17166682e43cbc2a81e2ed64a75e55c6398a7b', 16)"
10849505326481756291467078773071822372991137432974866960395851121614351820034216452685397471770720115956086308531118673792947647173561074086963379535710843
We verify if we can get the modulus (N) with prime1 (p) and prime2 (q):
>>> from __future__ import division >>> p=12865979254173524318205154356956226942340819748396485453570850199275733851574194544096345303446141207553525448737577133880210914025405392588238363787239107 >>> q=10849505326481756291467078773071822372991137432974866960395851121614351820034216452685397471770720115956086308531118673792947647173561074086963379535710843 >>> N=p*q >>> N
139589510448559426270140350106792398328403552834675368794733962561525914206396716036189393374294367303846992780695341826824306948258043034537162671328717852010658546072889560963675752283945322326005793726927254786393742142055806404861768824642002369852610966461772991591954263592365958281593575065087653537201L
It’s ok 🙂
Let’s finish by writing the private key !
>>> from pyasn1.codec.der import encoder >>> from pyasn1.type.univ import * >>> import base64, gmpy >>> e = 65537 >>> phi = (p - 1) * (q - 1) >>> d = gmpy.invert (e, phi) >>> dp = d % (p - 1) >>> dq = d % (q - 1) >>> qinv = gmpy.invert (q, p) >>> seq = Sequence() >>> for x in [0, N, e, d, p, q, dp, dq, qinv]: ... seq.setComponentByPosition (len (seq), Integer (x)) ...
Sequence().setComponentByPosition(0, Integer(0))
Sequence().setComponentByPosition(0, Integer(0)).setComponentByPosition(1, Integer(139589510448559426270140350106792398328403552834675368794733962561525914206396716036189393374294367303846992780695341826824306948258043034537162671328717852010658546072889560963675752283945322326005793726927254786393742142055806404861768824642002369852610966461772991591954263592365958281593575065087653537201))
Sequence().setComponentByPosition(0, Integer(0)).setComponentByPosition(1, Integer(139589510448559426270140350106792398328403552834675368794733962561525914206396716036189393374294367303846992780695341826824306948258043034537162671328717852010658546072889560963675752283945322326005793726927254786393742142055806404861768824642002369852610966461772991591954263592365958281593575065087653537201)).setComponentByPosition(2, Integer(65537))
Sequence().setComponentByPosition(0, Integer(0)).setComponentByPosition(1, Integer(139589510448559426270140350106792398328403552834675368794733962561525914206396716036189393374294367303846992780695341826824306948258043034537162671328717852010658546072889560963675752283945322326005793726927254786393742142055806404861768824642002369852610966461772991591954263592365958281593575065087653537201)).setComponentByPosition(2, Integer(65537)).setComponentByPosition(3, Integer(116686325898559281150851716438813414560069277484395919923870567846722243677361455228750167487332996908219077048043297780501744539014123771367073863406510482709352129658639986382507478487983991442421215180551628537559387916260003733597190832631815010596681142500744028001624957052131771889465677130681230555137))
Sequence().setComponentByPosition(0, Integer(0)).setComponentByPosition(1, Integer(139589510448559426270140350106792398328403552834675368794733962561525914206396716036189393374294367303846992780695341826824306948258043034537162671328717852010658546072889560963675752283945322326005793726927254786393742142055806404861768824642002369852610966461772991591954263592365958281593575065087653537201)).setComponentByPosition(2, Integer(65537)).setComponentByPosition(3, Integer(116686325898559281150851716438813414560069277484395919923870567846722243677361455228750167487332996908219077048043297780501744539014123771367073863406510482709352129658639986382507478487983991442421215180551628537559387916260003733597190832631815010596681142500744028001624957052131771889465677130681230555137)).setComponentByPosition(4, Integer(12865979254173524318205154356956226942340819748396485453570850199275733851574194544096345303446141207553525448737577133880210914025405392588238363787239107))
Sequence().setComponentByPosition(0, Integer(0)).setComponentByPosition(1, Integer(139589510448559426270140350106792398328403552834675368794733962561525914206396716036189393374294367303846992780695341826824306948258043034537162671328717852010658546072889560963675752283945322326005793726927254786393742142055806404861768824642002369852610966461772991591954263592365958281593575065087653537201)).setComponentByPosition(2, Integer(65537)).setComponentByPosition(3, Integer(116686325898559281150851716438813414560069277484395919923870567846722243677361455228750167487332996908219077048043297780501744539014123771367073863406510482709352129658639986382507478487983991442421215180551628537559387916260003733597190832631815010596681142500744028001624957052131771889465677130681230555137)).setComponentByPosition(4, Integer(12865979254173524318205154356956226942340819748396485453570850199275733851574194544096345303446141207553525448737577133880210914025405392588238363787239107)).setComponentByPosition(5, Integer(10849505326481756291467078773071822372991137432974866960395851121614351820034216452685397471770720115956086308531118673792947647173561074086963379535710843))
Sequence().setComponentByPosition(0, Integer(0)).setComponentByPosition(1, Integer(139589510448559426270140350106792398328403552834675368794733962561525914206396716036189393374294367303846992780695341826824306948258043034537162671328717852010658546072889560963675752283945322326005793726927254786393742142055806404861768824642002369852610966461772991591954263592365958281593575065087653537201)).setComponentByPosition(2, Integer(65537)).setComponentByPosition(3, Integer(116686325898559281150851716438813414560069277484395919923870567846722243677361455228750167487332996908219077048043297780501744539014123771367073863406510482709352129658639986382507478487983991442421215180551628537559387916260003733597190832631815010596681142500744028001624957052131771889465677130681230555137)).setComponentByPosition(4, Integer(12865979254173524318205154356956226942340819748396485453570850199275733851574194544096345303446141207553525448737577133880210914025405392588238363787239107)).setComponentByPosition(5, Integer(10849505326481756291467078773071822372991137432974866960395851121614351820034216452685397471770720115956086308531118673792947647173561074086963379535710843)).setComponentByPosition(6, Integer(9006008793280290951640469599239619008802433830625276869288535527896826074445979747477300468370412559264506766572109663499316045606534818270372994472429223))
Sequence().setComponentByPosition(0, Integer(0)).setComponentByPosition(1, Integer(139589510448559426270140350106792398328403552834675368794733962561525914206396716036189393374294367303846992780695341826824306948258043034537162671328717852010658546072889560963675752283945322326005793726927254786393742142055806404861768824642002369852610966461772991591954263592365958281593575065087653537201)).setComponentByPosition(2, Integer(65537)).setComponentByPosition(3, Integer(116686325898559281150851716438813414560069277484395919923870567846722243677361455228750167487332996908219077048043297780501744539014123771367073863406510482709352129658639986382507478487983991442421215180551628537559387916260003733597190832631815010596681142500744028001624957052131771889465677130681230555137)).setComponentByPosition(4, Integer(12865979254173524318205154356956226942340819748396485453570850199275733851574194544096345303446141207553525448737577133880210914025405392588238363787239107)).setComponentByPosition(5, Integer(10849505326481756291467078773071822372991137432974866960395851121614351820034216452685397471770720115956086308531118673792947647173561074086963379535710843)).setComponentByPosition(6, Integer(9006008793280290951640469599239619008802433830625276869288535527896826074445979747477300468370412559264506766572109663499316045606534818270372994472429223)).setComponentByPosition(7, Integer(433073011185685558668811176440116076838195454852407830208821681403529980945260085756519214888569873862720627784570646362243481468575549228855397727473329))
Sequence().setComponentByPosition(0, Integer(0)).setComponentByPosition(1, Integer(139589510448559426270140350106792398328403552834675368794733962561525914206396716036189393374294367303846992780695341826824306948258043034537162671328717852010658546072889560963675752283945322326005793726927254786393742142055806404861768824642002369852610966461772991591954263592365958281593575065087653537201)).setComponentByPosition(2, Integer(65537)).setComponentByPosition(3, Integer(116686325898559281150851716438813414560069277484395919923870567846722243677361455228750167487332996908219077048043297780501744539014123771367073863406510482709352129658639986382507478487983991442421215180551628537559387916260003733597190832631815010596681142500744028001624957052131771889465677130681230555137)).setComponentByPosition(4, Integer(12865979254173524318205154356956226942340819748396485453570850199275733851574194544096345303446141207553525448737577133880210914025405392588238363787239107)).setComponentByPosition(5, Integer(10849505326481756291467078773071822372991137432974866960395851121614351820034216452685397471770720115956086308531118673792947647173561074086963379535710843)).setComponentByPosition(6, Integer(9006008793280290951640469599239619008802433830625276869288535527896826074445979747477300468370412559264506766572109663499316045606534818270372994472429223)).setComponentByPosition(7, Integer(433073011185685558668811176440116076838195454852407830208821681403529980945260085756519214888569873862720627784570646362243481468575549228855397727473329)).setComponentByPosition(8, Integer(9943622598605961738794853212753664521202749308617237244167579884977660696850096171514979228017789146088690098832680432096076986782959551629877639877585393))
>>> print "\n\n-----BEGIN RSA PRIVATE KEY-----\n%s-----END RSA PRIVATE KEY-----\n\n" % base64.encodestring(encoder.encode (seq))
-----BEGIN RSA PRIVATE KEY-----
MIICXgIBAAKBgQDGyDUpojiPFGNlxfX9Sw2IiWG5XeEP+ohTo8LL7XUOmVm9D/hywiMva60yYk81
aoLQYnVeHk/trlToyiRx/I0TrHAO4lcg1NkIn9b71C8S5qQeHB3oH1eMMhMq0IWU6FGEHQI5zUEN
7xHRwV7nW5L4agT3xsfza5BGuPsv4pVlsQIDAQABAoGBAKYqtkYXVTBF2tE4qmkSVD3OmeJal8jD
pTJFspDF7xRFHL7umsFTiBYb7KwxggUlBDUuGO6UaDxHfrMaR10BwOs2tYa0ymvzh/5Anx50wOSf
c/030Xjfq0nfpf96M1PHQsv6EYioS6rdfxgCRUsy9cpRSRRGgOBfZ+AXa4cah/gBAkEA9aeYutdW
uO6bTjqR/hyv1/+tV3A3evAVbCPGTUB/ktviSpKudCf9frGMYgNBoX3HZwmG7mduF9mdSXvP6gue
wwJBAM8nRwDW9q3qflNEpFw0qS+5PbjyP12n3jLezG/ka31txDqr8VuxzA9IZREqPRcWZoLkPLwq
geLtZKdeVcY5insCQQCr9HQ5nZDsBMIb4W3eVdBVP3jkMv3zBWnJd8VQwCxM7bQahVCuqGuOqtPc
q/DeDUBuhMG50hbDhSXPkWZ5q0anAkAIRNEYv3vpRUr1l+/XnmKCfSpxj3noCyNbdHlEniGMSC1l
CigAOQCkO4eNP9pgaYx9/Q5PlILKxB8YbzONTg6xAkEAvdtqMYcnXrhttTgCEWe/07KPUhgXvL5E
iaRT8Oxrxa+0jCWMlGCaZPr+w4Se7jqSyiIIKE30Oz3fiBgM8Hlp8Q==
-----END RSA PRIVATE KEY-----
We paste it into a “newprivate.key” and run the decrypt:
$ openssl rsautl -decrypt -inkey newprivate.key -in secret -out flag
We display the file’s contents:
$ cat flag
kenny
Flag is “kenny“.