Official TwoForOne Discussion

Try and think of what the public and private keys are actually doing. There is a mathematical theorem that does the same thing

Nice Challenge, need more reading to figure out the attack. anyway solved with full understanding.

Hint:

compare both keys there is something common between them. :wink:

I think I understand what needs to be done but I feel stupid cause I canā€™t find a way to get the message1 and 2 into an integer to perform the mathematical functions required. You guys have any hint on how to do that?

@splintercelian I would recommend you check pycrtodome documentation. They might have something ^^

I think I know the theory behind the attack but actually implementing it is causing me problems. Assuming I have ā€œuā€ (some value that I will use as ā€œeā€ or ā€œdā€ in RSA), how do I compute m**u?

Hi there, Iā€™m having some problems to solve this challenge. Iā€™ve tried working with the phi(n) function (from sympy) to calculate the private exponent (d). However until this moment it havenā€™t worked because it seems a complicate calculation for large numbers (or I donā€™t know if Iā€™m using the incorrect function since @Fukurou mentioned that It only need basic math). I would thank if someone could advice me or told me If Iā€™ve forgotten a step to find the solution.

@rdanilu your idea is technically correct. However, this amounts to factoring n which at the point is impossible unless you want to wait a while. You need to think more basic number theory. Google can be a great help too

Hi, can I pm someone for a hint on how to start this challenge ?

@lel1q I would appreciate some help. Thank you

Hey , I think I got the original message but its in the format of large integer (got this after some calculations ). Can someone please help me to get string from this large int?

@Fukurou, computing Pow(message[as a big int], relative big number[~100K]) takes forever, is there a trick to avoid this computation?

EDIT: was long but worked at the end! Nice challenge :slight_smile:

Hello, I have studied how RSA and generic public key cryptographic algorithms work, but I donā€™t understand how to obtain all the elements that are needed to perform the necessary computation. Also, the fact that here someone is talking about basic math gets me confused, but in general I think I am not converting the public key/the messages in the correct way. If someone could give me some help Iā€™d be very grateful

EDIT: I finally managed to retrieve the correct information from the .pem files (before I was using simple string-to-hex encoding), but now retrieving a private key seems unfeasible due to the huge numbers, even though many of you said only basic math is needed :confused:

EDIT: finally got it, it was a really hard challenge, despite what others may say, if you are not really into the topic. Still I am now really satisfied with what I learned. For anyone having trouble, feel free to dm me, I can give some hints without spoiling anything :slight_smile:

(Plaintext^public_key)%N = cipher text. Since plain text is same can we try to compare two equation to find N

Donā€™t know if I am correct

when I run:
$ openssl x509 -in key1.pem -text -noout

I get:
unable to load certificate. 139729726211392:error:0909006C:PEM routines:get_name:no start line:ā€¦/crypto/pem/pem_lib.c:745:Expecting: TRUSTED CERTIFICATE

Also, some common python modules fail to load these PEM files too. I was able to parse them with some other tools and get the necessary information, but I am wondering why the most common methods fail? Am I overlooking something silly? Can anyone kindly explain? I feel frustrated.
~Thanks!

@JumpingLlama said:

when I run:
$ openssl x509 -in key1.pem -text -noout

I get:
unable to load certificate. 139729726211392:error:0909006C:PEM routines:get_name:no start line:ā€¦/crypto/pem/pem_lib.c:745:Expecting: TRUSTED CERTIFICATE

Also, some common python modules fail to load these PEM files too. I was able to parse them with some other tools and get the necessary information, but I am wondering why the most common methods fail? Am I overlooking something silly? Can anyone kindly explain? I feel frustrated.
~Thanks!

The file isnā€™t an x.509 certificate, but ā€œonlyā€ a public key. In those cases, you need to use

openssl rsa -in key1.pem -pubin -noout -text

:wink:

Type your comment> @HomeSen said:

:wink:

forehead slap Thank you!! Thatā€™s exactly the help I needed :slight_smile:

Edit: ā€¦and, solved now. Nice challenge. If you google using the correct name of the attack, there is quite a ā€œcommonā€ amount of info out there.

Hello Iā€™ve been at this for a long time now. Iā€™ve tried small public exponent attack, factorizing n, but no luck. Can I DM somebody for a hint?

edit: I found the attack but when i use it, python reports OverflowError: int too large to convert to float.

edit: I completed the challenge. Apply modulus every time possible, donā€™t wait for the final calculation to finish and then apply modulus. Donā€™t use pythonā€™s ** operator or pow function DIRECTLY for negative powers while dealing with modulo arithmetic.

Not too easy. But it made sense after. If you are stuck, this may help

Hello friends. I solved this challenge, but I am not happy with the way I walked towards the solutionā€¦ Have you created your own scripts or have you used existing scripts from Github? In addition, have you done deep mathmatic researches to understand this attack? Iā€™ve googled for the attack name, found theoretical descriptions of the mathematics behind this attack and various scripts on Github, but I am not very happy about this :frowning: because I have not put in so much of my own work and knowledge :frowning:

I solved it few minutes ago after 6 hours of search, Iā€™m pretty new to crypto, but canā€™t say I dislike all that math formulas and crazy ways of reversing the operations
This one is surely hard for people who are starting, but the point may not be in reinventing all the formulas for each problem you find (although it being a good exercise in case you have 200 IQ)
The point may be in fact of knowing what formulas you can use and when you should use them

For anyone starting, keep in mind that the internet is a great source of information and tools, use everything you have and search for all that you can :relaxed:

R :heart: