0

I am playing a game in my university where you have different puzzles based on cryptography and now in a puzzle named 'rsa', we have 2 files: 'key', 'secret'.

The task for this is to decrypt the secret message using the key, and of course I am suspecting some RSA encryption but I can't find anything to decrypt this and I think I might have not enough information. I don't really know. Anyway, here is the key:

308204a40201000282010100b3b77eb538f617a8441cdcf1fb133c1e73156894f1e049402d5c3ca7c74b69c6a8e81913dcfaeaee3e46bee05934ed21c23adc989729c189bf791da75b596ef41a325938205399ec0ca3aceea90238f3589b5b8427f8bae78b801e65d00a4fdd4905bfc650a79d596034b3dc20fd894202a9f718799d742e7df5defde553e3ab8e952e0f3047f73fe1e1c8ca8a66536cf2f0746a0f607de6dba0a8e3570ef83c03420a919a950a5a007597bf2f5cac8d096f3cacb0ca228a73500dd2bd08451effb7ab00c07d92f22607a740a394506a085ab0fb5627a20e6fbf122a9ab369ee2fb61c983620d848a72b16047f265468369ac449e9b4f07361af8e1019df7d570203010001028201010099ee83a329a4efe27a64d6829571863ef687d1ca31dad0231e3730e4ec7915a2c92df3bce5bc2dd9de91ae106f983bbc7ca6fa27e0e22d19955d621ee4c997959192aa84be7b9d0d684e11636273bae004771d4df706bee070c64e431a8c9a978962593ebdfab375c8479bfee26b0753f90027db58df9a91efe5d7185583232f6edaba4d2c6c797ff177eed7e6ee6424adc3af8352e61134265522f0a1334761845231e6708b630caf0ca24a77f597b3ec2e038172017f66b1e76c1cd99d2b5a6a29faab9ba42a89ec44b1ff20ee606f9e7f9556bd9a74e5c1b83d87317f2008ca7790b4f0218292f484ca40a3c3d64c541634bbcc903f1c2cac5971a6f957f102818100bf54486569e2ff77a4fad4e97efd0048978b1d2d5e7b4221c3def2ad6ca0427af42bbf592cf2439048d90eff248810ebf6faf67851c4b1c7dd646f5372e6e9eb46360f737cedba2cc0b5a288ceefcf408e576e8352c990c2470a363085328b4a76732c39251a16ba7d37e0ac14bcec879081214bbdb543acecb31a7d3e670f8502818100f07662fee84a2e05e6997a28dfacbbc160417640cb285d223626b656e0e6c22309d5adef3888b38ad172017d467453ee53e831e2a877f7836aa1a5c19e7443142d5c1dcafc092a2f5c3951458ee0c9cfa153f8eefe22b94e51608e98bd5b3609a3c9f870f09e08c7830df749d96bf0eded633fb1318da083bf2a440fec48fa2b0281804764e4eaeadb28a6f5aa1f9ecda30ce309a1808eb86dd81c8f61773edd84e3a9cbc9334acc69ce6a5db49952fdc7c440b8d5a6f8f8d223e0c7ad3d996f0bd987d09845a5bb9d5dd66b469bd2df1d3f42009b81828176f38c7b43c53acfc92f8ee6aa4d7b396c05c52b0a99ccbca44ec2bb5a6419463e0875d39175b5fc7e2a9d02818042946500b38ca68597bdf32712179fbd014bded43dec252d6dd4f633c3fde0cf16d00562f14258841d4df5bf9c1c6588ddceb2d15158363e3aee1b192b2881d23a650112cd0a3495fc711a61aa17ef88ffe06252ba271f2be2385c034a9ad0b1869a4ba1e9ddb80c95eaee07929de28dde66d6a1d758a193190138eb37bf5515028181008d99f0f0beffa8fad237540ed70199de7c6d9324505174115e41031957ec2999017e8b1c7d5f9889a62fe78e1d532dc5ef41fa694e49aca5d52987d8f70f96413506e4714e11006dbcec3c318d6211de7f8548b4b37abedd2b2f96b367b0ebcfd0166c6582a660ce9f79b74ef83bb0bbc87604fdefc3b2bfcb1215b2f9ca1d35

And here is the message:

4c0605e901b09d75c5f5befe7438d7246f988531cc7a39a59f24b9488d47dfae9fc8beb5117f34a316f9380607bf239ba6eca84da47a12d720986a8a0100a7e9d7028d7e423557055b9e250f271d6436018c58e79a8f26bac10768776f06dc1786dd7428b3c445b8993e884630b36cb2d300fa5dc1fe0eba9e433062d9d8a58f33bf6f93aa37298a5703ccbf71c93adea447f018e9f75bb43dbc528cfc9bed865a9ba43f926071dabc89ccca2e000f1a966855cc9816e45c0113edb55a700198d346a90487b5ff1191994973eb1b5252b22c6410aa70ea4e9c3ebd468ef273d7cf9d15b5824244cd25f252886d1edfe2d6f2caa5d5e00fd84597e3de192db41b

UPDATE: No, I'm not sure, don't think that the message is encoded in hexa too.

found out that RSA KEY was actually coded in hexa and the RSA key is basically:

MIIEpAIBAAKCAQEAs7d+tTj2F6hEHNzx+xM8HnMVaJTx4ElALVw8p8dLacao6BkT3Prq7j5GvuBZNO0hwjrcmJcpwYm/eR2nW1lu9BoyWTggU5nsDKOs7qkCOPNYm1uEJ/i654uAHmXQCk/dSQW/xlCnnVlgNLPcIP2JQgKp9xh5nXQuffXe/eVT46uOlS4PMEf3P+HhyMqKZlNs8vB0ag9gfebboKjjVw74PANCCpGalQpaAHWXvy9crI0JbzyssMoiinNQDdK9CEUe/7erAMB9kvImB6dAo5RQaghasPtWJ6IOb78SKpqzae4vthyYNiDYSKcrFgR/JlRoNprESem08HNhr44QGd99VwIDAQABAoIBAQCZ7oOjKaTv4npk1oKVcYY+9ofRyjHa0CMeNzDk7HkVoskt87zlvC3Z3pGuEG+YO7x8pvon4OItGZVdYh7kyZeVkZKqhL57nQ1oThFjYnO64AR3HU33Br7gcMZOQxqMmpeJYlk+vfqzdchHm/7iawdT+QAn21jfmpHv5dcYVYMjL27auk0sbHl/8Xfu1+buZCStw6+DUuYRNCZVIvChM0dhhFIx5nCLYwyvDKJKd/WXs+wuA4FyAX9msedsHNmdK1pqKfqrm6QqiexEsf8g7mBvnn+VVr2adOXBuD2HMX8gCMp3kLTwIYKS9ITKQKPD1kxUFjS7zJA/HCysWXGm+VfxAoGBAL9USGVp4v93pPrU6X79AEiXix0tXntCIcPe8q1soEJ69Cu/WSzyQ5BI2Q7/JIgQ6/b69nhRxLHH3WRvU3Lm6etGNg9zfO26LMC1oojO789Ajldug1LJkMJHCjYwhTKLSnZzLDklGha6fTfgrBS87IeQgSFLvbVDrOyzGn0+Zw+FAoGBAPB2Yv7oSi4F5pl6KN+su8FgQXZAyyhdIjYmtlbg5sIjCdWt7ziIs4rRcgF9RnRT7lPoMeKod/eDaqGlwZ50QxQtXB3K/AkqL1w5UUWO4MnPoVP47v4iuU5RYI6YvVs2CaPJ+HDwngjHgw33Sdlr8O3tYz+xMY2gg78qRA/sSPorAoGAR2Tk6urbKKb1qh+ezaMM4wmhgI64bdgcj2F3Pt2E46nLyTNKzGnOal20mVL9x8RAuNWm+PjSI+DHrT2ZbwvZh9CYRaW7nV3Wa0ab0t8dP0IAm4GCgXbzjHtDxTrPyS+O5qpNezlsBcUrCpnMvKROwrtaZBlGPgh105F1tfx+Kp0CgYBClGUAs4ymhZe98ycSF5+9AUve1D3sJS1t1PYzw/3gzxbQBWLxQliEHU31v5wcZYjdzrLRUVg2PjruGxkrKIHSOmUBEs0KNJX8cRphqhfviP/gYlK6Jx8r4jhcA0qa0LGGmkuh6d24DJXq7geSneKN3mbWoddYoZMZATjrN79VFQKBgQCNmfDwvv+o+tI3VA7XAZnefG2TJFBRdBFeQQMZV+wpmQF+ixx9X5iJpi/njh1TLcXvQfppTkmspdUph9j3D5ZBNQbkcU4RAG287DwxjWIR3n+FSLSzer7dKy+Ws2ew68/QFmxlgqZgzp95t074O7C7yHYE/e/Dsr/LEhWy+codNQ==

5
  • 2
    I'm voting to close this question as off-topic because the question is about cryptography and not reverse-engineering. You should ask this at Crypto SE. – perror Dec 30 '18 at 11:05
  • @perror man, really? come on, those guys sent me here – C. Cristi Dec 30 '18 at 11:36
  • Well, your question has nothing to do with reverse-engineering... But, okay, I'll help you a bit... – perror Dec 30 '18 at 11:49
  • Is this game an assignment for class? What textbook is being used for the class? What is the exact description of the game with all information included? Are you the only one working on it? If not, have you discussed this with your classmates or colleagues? Are any examples from the lectures relevant to this challenge? Have you talked to the professor? Even though crypto challenges are off topic here we can help you out, as perror has done, but it will be up to you to do the work and solve it – julian Dec 30 '18 at 16:13
  • No, it's not an assignment, it's a game made by students and it's just fun, it's kind of a capture the flag – C. Cristi Dec 30 '18 at 16:15
1

From here the structure of a private key looks like

RSAPrivateKey ::= SEQUENCE {
  version           Version,
  modulus           INTEGER,  -- n
  publicExponent    INTEGER,  -- e
  privateExponent   INTEGER,  -- d
  prime1            INTEGER,  -- p
  prime2            INTEGER,  -- q
  exponent1         INTEGER,  -- d mod (p-1)
  exponent2         INTEGER,  -- d mod (q-1)
  coefficient       INTEGER,  -- (inverse of q) mod p
  otherPrimeInfos   OtherPrimeInfos OPTIONAL
}

If analyzed the base64 data in the ASN.1 decoder

SEQUENCE (9 elem)
  INTEGER 0
  INTEGER (2048 bit) 226871413225308095515915826394392101638242887434378121570998515897193…
  INTEGER 65537
  INTEGER (2048 bit) 194320763995749647278490303169550120288709068819771754524412632427072…
  INTEGER (1024 bit) 134355954175703308272730070638862721054431606752282500957493356998331…
  INTEGER (1024 bit) 168858473461189648019451140006978906971949575614563598413430805554687…
  INTEGER (1023 bit) 501346546129182660757986157052258700182511397092797741873369248728839…
  INTEGER (1023 bit) 467538315673092658034539326878959861744205105375874857990160580678909…
  INTEGER (1024 bit) 994358373821297873423986022178929159513641342137481304248109111567867…

All the values n,e(65537), d, p, q, exponent1, exponent2 and coefficient are present with probably proper lengths. So this is a private key. As already mentioned in other answer, see how you can load this in python

In [1]    from Crypto.PublicKey import RSA  
          from Crypto.Util.number import long_to_bytes, bytes_to_long
          
          k_raw = "MIIEpAIBAAKCAQEAs7d+tTj2F6hEHNzx+xM8HnMVaJTx4ElALVw8p8dLacao6BkT3Prq7j5GvuBZNO0hwjrcmJcpwYm/eR2nW1lu9BoyWTggU5nsDKOs7qkCOPNYm1uEJ/i654uAHmXQCk/dSQW/xlCnnVlgNLPcIP2JQgKp9xh5nXQuffXe/eVT46uOlS4PMEf3P+HhyMqKZlNs8vB0ag9gfebboKjjVw74PANCCpGalQpaAHWXvy9crI0JbzyssMoiinNQDdK9CEUe/7erAMB9kvImB6dAo5RQaghasPtWJ6IOb78SKpqzae4vthyYNiDYSKcrFgR/JlRoNprESem08HNhr44QGd99VwIDAQABAoIBAQCZ7oOjKaTv4npk1oKVcYY+9ofRyjHa0CMeNzDk7HkVoskt87zlvC3Z3pGuEG+YO7x8pvon4OItGZVdYh7kyZeVkZKqhL57nQ1oThFjYnO64AR3HU33Br7gcMZOQxqMmpeJYlk+vfqzdchHm/7iawdT+QAn21jfmpHv5dcYVYMjL27auk0sbHl/8Xfu1+buZCStw6+DUuYRNCZVIvChM0dhhFIx5nCLYwyvDKJKd/WXs+wuA4FyAX9msedsHNmdK1pqKfqrm6QqiexEsf8g7mBvnn+VVr2adOXBuD2HMX8gCMp3kLTwIYKS9ITKQKPD1kxUFjS7zJA/HCysWXGm+VfxAoGBAL9USGVp4v93pPrU6X79AEiXix0tXntCIcPe8q1soEJ69Cu/WSzyQ5BI2Q7/JIgQ6/b69nhRxLHH3WRvU3Lm6etGNg9zfO26LMC1oojO789Ajldug1LJkMJHCjYwhTKLSnZzLDklGha6fTfgrBS87IeQgSFLvbVDrOyzGn0+Zw+FAoGBAPB2Yv7oSi4F5pl6KN+su8FgQXZAyyhdIjYmtlbg5sIjCdWt7ziIs4rRcgF9RnRT7lPoMeKod/eDaqGlwZ50QxQtXB3K/AkqL1w5UUWO4MnPoVP47v4iuU5RYI6YvVs2CaPJ+HDwngjHgw33Sdlr8O3tYz+xMY2gg78qRA/sSPorAoGAR2Tk6urbKKb1qh+ezaMM4wmhgI64bdgcj2F3Pt2E46nLyTNKzGnOal20mVL9x8RAuNWm+PjSI+DHrT2ZbwvZh9CYRaW7nV3Wa0ab0t8dP0IAm4GCgXbzjHtDxTrPyS+O5qpNezlsBcUrCpnMvKROwrtaZBlGPgh105F1tfx+Kp0CgYBClGUAs4ymhZe98ycSF5+9AUve1D3sJS1t1PYzw/3gzxbQBWLxQliEHU31v5wcZYjdzrLRUVg2PjruGxkrKIHSOmUBEs0KNJX8cRphqhfviP/gYlK6Jx8r4jhcA0qa0LGGmkuh6d24DJXq7geSneKN3mbWoddYoZMZATjrN79VFQKBgQCNmfDwvv+o+tI3VA7XAZnefG2TJFBRdBFeQQMZV+wpmQF+ixx9X5iJpi/njh1TLcXvQfppTkmspdUph9j3D5ZBNQbkcU4RAG287DwxjWIR3n+FSLSzer7dKy+Ws2ew68/QFmxlgqZgzp95t074O7C7yHYE/e/Dsr/LEhWy+codNQ=="
          
          k = RSA.importKey("-----BEGIN RSA PRIVATE KEY-----\n%s\n-----END RSA PRIVATE KEY-----\n" % k_raw)
          ciphertext = "4c0605e901b09d75c5f5befe7438d7246f988531cc7a39a59f24b9488d47dfae9fc8beb5117f34a316f9380607bf239ba6eca84da47a12d720986a8a0100a7e9d7028d7e423557055b9e250f271d6436018c58e79a8f26bac10768776f06dc1786dd7428b3c445b8993e884630b36cb2d300fa5dc1fe0eba9e433062d9d8a58f33bf6f93aa37298a5703ccbf71c93adea447f018e9f75bb43dbc528cfc9bed865a9ba43f926071dabc89ccca2e000f1a966855cc9816e45c0113edb55a700198d346a90487b5ff1191994973eb1b5252b22c6410aa70ea4e9c3ebd468ef273d7cf9d15b5824244cd25f252886d1edfe2d6f2caa5d5e00fd84597e3de192db41b".decode('hex')

Now decryption is simply a pow operation

print long_to_bytes(pow(bytes_to_long(ciphertext), k.d, k.n))
          
gFmqI4XpJBjprHFWrVqkaQ==
0

First, the first sequence of hexadecimal (the key) and the last (MIIE..) are exactly the same in different encoding (namely base64 encoding). This blob is either a key or a certificate.

Anyway, we are missing the tags at begin and end of file telling what kind of format it is. Something like:

-----BEGIN RSA PRIVATE KEY-----
MIIEpAIBAAKCA...
-----END RSA PRIVATE KEY-----

It is formatted as an ASN.1 file format (see here for more).

What you should do:

  1. You should first find the kind of data that is encoded here before applying the decryption algorithm.

    You say that it is an RSA key, so you might have some clue where to start from.

  2. Then, once you identified the key format, you can use openssl to decrypt your message (look on the web, there are plenty of tutorials about it).

5
  • Hello, I know they are the same in different encoding but from what I say on the internet is that the RSA keys are usually in the base64 format, and I know that that is the key because as i said in the description that there are 2 files: key and secret from which the key ofc will contain the key and secret the message that I have to decrypt however after long searches on the internet and watching tutorials, forgive me man, but I can't figure out how to put this togheter, I feel like I've tried everything – C. Cristi Dec 30 '18 at 13:27
  • In fact, RSA keys, ECDSA keys and X509 certificates are usually encoded in base64 within this format. So, you need to know what kind of key is hiding in this file. I advise you to read this page to know what you can try to decrypt your message. – perror Dec 30 '18 at 17:55
  • Try an ASN.1 decoder here. Read from here about the structure of a private key file. Once you know that this is actually a private key file use RSA module from Crypto.PublicKey in python to import key and decrypt. – sudhackar Dec 31 '18 at 5:40
  • @sudhackar okay how do I deterime if it's a key, do I paste the hex i got into the ASN and then get some other hex over there but in chunks of bytes, right? what do i do with them now? – C. Cristi Dec 31 '18 at 10:53
  • @sudhackar Because it just tells me that it's sequence of 9 integers – C. Cristi Dec 31 '18 at 10:54

Not the answer you're looking for? Browse other questions tagged or ask your own question.