0

I am doing a hacking challenge but I don't manage to know how to decrypt the private key from the public key and the given private key "prime1" parameter.

I've seen a private key is composed of :

  • modulus
  • publicExponent
  • privateExponent
  • prime1
  • prime2
  • exponent1
  • exponent2
  • coefficient

I've been able to retrieve :

  • modulus
  • prime1
  • publicExponent

Concerning prime2, I tried to compute it (by dividing modulus and prime1) and I get the following value : 

19D28095CF467FE66ADBDBBA576B9C4CB14F352196A464AC4E501DF3D3949AEA6092BE46055C0E5E1A45B4053DFD00C87B1D26E09375FCADB23204CB51EBB0ED010767BE04EE8AC6E1912524A9491BBCB674EFCFF367EDFACC7D80C34BB431FA36B5D1E240D6DAE99412C06294AD23E25460245EDEE063AF51D953F67D1A0330B49CF3DE1F77CED7D868B43BCD3FF4726E6A555E3C399F1BC170BC4160CCE1CFD7ED1394CDB274FC5A30F81642A5233920A0032AB18A360A9C578A0E3AAA9823A0382DE703654F3C8175B963E304A7FFA2A0316CF0CFEB6A0413174A9948E5309EEF6F3ABFE43CBCC186809296F869710C263BAA4EC1F959B00893AC3C23066B6

which translates in :

00:19:D2:80:95:CF:46:7F:E6:6A:DB:DB:BA:57:6B:
9C:4C:B1:4F:35:21:96:A4:64:AC:4E:50:1D:F3:D3:
94:9A:EA:60:92:BE:46:05:5C:0E:5E:1A:45:B4:05:
3D:FD:00:C8:7B:1D:26:E0:93:75:FC:AD:B2:32:04:
CB:51:EB:B0:ED:01:07:67:BE:04:EE:8A:C6:E1:91:
25:24:A9:49:1B:BC:B6:74:EF:CF:F3:67:ED:FA:CC:
7D:80:C3:4B:B4:31:FA:36:B5:D1:E2:40:D6:DA:E9:
94:12:C0:62:94:AD:23:E2:54:60:24:5E:DE:E0:63:
AF:51:D9:53:F6:7D:1A:03:30:B4:9C:F3:DE:1F:77:
CE:D7:D8:68:B4:3B:CD:3F:F4:72:6E:6A:55:5E:3C:
39:9F:1B:C1:70:BC:41:60:CC:E1:CF:D7:ED:13:94:
CD:B2:74:FC:5A:30:F8:16:42:A5:23:39:20:A0:03:
2A:B1:8A:36:0A:9C:57:8A:0E:3A:AA:98:23:A0:38:
2D:E7:03:65:4F:3C:81:75:B9:63:E3:04:A7:FF:A2:
A0:31:6C:F0:CF:EB:6A:04:13:17:4A:99:48:E5:30:
9E:EF:6F:3A:BF:E4:3C:BC:C1:86:80:92:96:F8:69:
71:0C:26:3B:AA:4E:C1:F9:59:B0:08:93:AC:3C:23:
06:6B:6

Which is quite a problem as it ends with "6". I added the leading 00.

Values I extracted so far :

prime1:
007f40dc44ba03d15342f75908e0f9300596644ade94685e08e28c9ab1640c2f62c29ab9a239824b9ebeeb76ae6d8721a35e9ed98d7ea4383e590934a578b5f72e895d5c3752eafdf631ccbad2d960e4451d6776d21ff49c9dc9b1904551edd27fddb674b4997fb10ad9b7c2be8ba407220a8e3a36ff6dc11d6393afcb4ec0479f65bfdfe3f05f1e98614574ec36a7a5b1f18d3d976b5a82490900080d9dc274a44e30a139682f22347113aa3bf2204f8e10ebd4d09bb58cc2535f9d71130c0f21b66e133940d3a6b1eb74addd0a291481b190ade053f089c800fedcad5659fc281dc0cf5e08c0163324a352bbf3251043c373b8404ffc6b6b77bd5f2224eb7f15

modulus:
CD5F8A24C7605008897A3C922C0E812E769DE0A46442C350CB78C7868539F3D38AAC80B3E6A506605910E8599806B4D1D148F2F6B81DA04796A8A5AEE18F29E83E16775A2A0A00870541F6574ED1438636AE0A0C116E07104F48F72094863A3869E1C8FC220627278962FB22873E3156F18E55DEC94E970064EC7F4E0E88454012E2FD5DFE5F8D19BF170F9CCB3F46E0FD1019BCB02D9083A0703C617F996379E6478354A73AE6E6ACBCE1F4333ECFAF24366A3E977D3CD3CBFE8D8A387BD876BFDAB8488F6F47BF1FBE33010FD2D7E22B4DB2E567783CE0B606DB86B93759714C4F6396A7FB9F74C4021043B0F3D46D2633EBD43A877863DF7D680F506587C119DD64100CA831CE2AF33D951B524C5F06B49F5BF2CB381E74181930D06A80505C06ABD5BF4870F0C9FB581BD80DBA889660639F936EDEA8FE5D0C9EAE58062ED693252583C71CC782BA613E01438E69B43F9E64ECA84F9EA04E811AD7B39EFD7876D1B6B501C4F48ACCE6F24239F6C04028788135CD88C3D15BE0F2EBB7DE9E9C19A7A93037005EE0A9A640BADA332EC0D05EE9F08A832354A0487A927D5E88066E2569E6C5D4688E422BFA0B27C6171C6D7BF029BFD9165752AF19AA71B33A1EA70B6C371FB21E47F527D80B7D04F582AD9F9935AF723682DC01CA9880621870DECB7AD15648CDF4EF153016F3E6D87933B8EC54CFA1FDF87C467020A3E753

publicExponent:
65537 (0x10001)
  • Can I get the private key from theses parameters (modulus, publicExponent and prime1) ?
  • Is my reasoning about "prime2" right ? (by dividing the modulus and the prime1).
  • How to get the last elements ?
  • Have you any tool which automatically computes a private key from theses parameters ?
Improve this question
5
  • It seems that your first prime is a multiple of $5$ and of $65119$ and of $980579$
    – Hagen von Eitzen
    May 18, 2019 at 15:17
  • Does that mean the prime1 is invalid ? @HagenvonEitzen
    – secavfr
    May 18, 2019 at 18:36
  • 1
    The solution is in the sed commands, you didn't replace properly.
    – TheFrog21
    May 18, 2019 at 19:23
  • It seems I replaced correctly the prime number hex values with the sed commands (in inverse order of course). I checked several times. But it seems the prime1 is still not prime. Do you assert it is prime ?
    – secavfr
    May 18, 2019 at 21:04
  • original values may have already be sed substitute result
    – r043v
    Jun 5, 2019 at 10:33

2 Answers 2

Reset to default
4

This challenge is part of an ongoing French DGSE services challenge. You have one thing that's missing. Check again how you obtained your prime1 number. The parameter went through specific substitutions that can be reversed but not in a simple way.

Improve this answer
1
  • @Shutdown I love your pseudo! ShutUp wasn't available?
    – RawBean
    May 28, 2019 at 11:48
2

After many reasearches, I've been able to find the correct tool to generate a private key given its modulus (n), prime1 (p) and prime2 (q) parameters (prime2 is even facultative, in reality).

Check out this gist : https://gist.github.com/flavienbwk/54671449419e1576c2708c9a3a711d78.

Tho: there still seem to be a problem with the prime1 number provided as it is... not prime.

Improve this answer
6
  • Perhaps this is done on purpose? To my knowledge, RSA would work with non-primes as well. It just would not be secure.
    – user163495
    May 22, 2019 at 10:06
  • Thank you @MechMK1, I tested with the non-prime number I've found and it doesn't decode the message we have to decode with the RSA key. Do you know if the leading zeros in "prime1" or "prime2" parameters impact the encoding/decoding ?
    – secavfr
    May 22, 2019 at 10:08
  • 1
    Mathematically speaking, no. Leading zeroes do not affect any computation. 13 + 24 = 37 is the same as 00013 + 00000024 = 0037. As for the tools used to decode, that again is up to the tool and how it encodes the variables. Though I have to ask, is this for an ongoing challenge?
    – user163495
    May 22, 2019 at 10:10
  • Thank you for this precision. Yes it is an ongoing challenge.
    – secavfr
    May 22, 2019 at 10:11
  • If the challenge is still ongoing, then to my knowledge we only provide very, very limited help, as it would pose as an unfair advantage to you in comparison to others who try to solve it by themselves. Perhaps someone conducting the challenge is willing to give you a hint, if you explain your steps properly?
    – user163495
    May 22, 2019 at 10:13

Not the answer you're looking for? Browse other questions tagged .