0
$\begingroup$

To factorize N = p * q with p < q e (p-2) mod 9 = 0, there are a set of equations. These equations can be put into any popular math solver, in order to gain access to the primes p and q. For instance, the prime components of the public key N = 209 can be solved as follows:

[(h+1)^2]*[(2*h+2)^2/2-1] = X*(209-4-2*n+2*(p-2)),(h+1)/3=(k+1)/6 ,p^2+n*p=209, 
                            h+1+k+1=(209-4-2*n+2*(p-2)),h,X,n,k

->

h = (2 (-209 + 99 p + 2 p^2))/(3 p)

[(h+1)^2]*[(2*h+2)^2/2-1] = X*(209-4-2*n),(h+1)/3=(k+1)/6 ,p^2+n*p=209,
                            h+1+k+1=(209-4-2*n),h,X,n,k

->

h=(2 (-209 + 101 p + p^2))/(3 p)

(2 (-209 + 99 p + 2 p^2))/(3 p)-(2 (-209 + 101 p + p^2))/(3 p)=6

-> 

p=11

This shows that p = 11. By simple division, it can be determined that q = 19.

It seems to me as if this approach is somewhat obvious, and I'd like to know how RSA is still considered secure if I can do these calculations in a math solver?

Improve this question
$\endgroup$
3
  • $\begingroup$ This was not my question. The original question is this: The question is when will I be able to release information? $\endgroup$
    – Alberico Lepore
    Sep 30, 2019 at 14:22
  • $\begingroup$ Now. You can release it now. $\endgroup$
    – A. Hersean
    Sep 30, 2019 at 16:30
  • 1
    $\begingroup$ For how to release it, you can publish a paper on arXiv.org, so that it cannot be deleted by censors. You could also try to publish it in a peer-review journal or conference, but your evidence might be too ground-breaking to pass the review process: the reviewers could be inclined to dismiss it out of hand. $\endgroup$
    – A. Hersean
    Sep 30, 2019 at 16:35

4 Answers 4

Reset to default
7
$\begingroup$

The RSA problem, which is the underlying problem that makes RSA cryptographically secure, is currently considered as an unsolved problem. There exists no known algorithm to efficiently compute P, given the public key (N, e) and the ciphertext C ≡ Pe (mod N).

But who cares about theory, right? You claim to have a solution, then try it! Here is an RSA public key:

    -----BEGIN PUBLIC KEY-----
MIICIjANBgkqhkiG9w0BAQEFAAOCAg8AMIICCgKCAgEApjP/ml4yt/iLr3Kzt7yv
H+7zEdnJ04xCTeW+Vx9CBRQukRdkVoMYntP6RHx6mZSeMKTXtOt87LHVxOoNi2Bf
efoQAxB1ehXW4h8F1tnmSruKt87U9YDe0W8Z9GOC63vq5eu95zqDvWQ6s42P4Gga
eZGXD6RKaw6TcYqfl7MWR6I21lOgFUKojNb0+LD4wdaES1L7pOlbCLstaQO91Dea
3HyD1h+NKEDrVT2goVnTbsF9AZf8xHmEHhWAZNRpsskiXlG6PKdlzuBbt1q+5b4J
0Kimw01mwgKt/2k4LkPa6PaM2PoiXisfDeaRLFV5F3INokhwaYNTolzEaz7y+Tyr
OhBwrcvMK+/1iMPzNgSk0qsnObX0+fn9e/RZvzxz8hdlWqVGVb4sswWt+bJnn1Bv
zZ58Q+NlQG7kQb58i+zHuBqvbunbMWT9osmbS4W+PVKG0nGrusRlTc3lY10HfoPE
hX3r1L4rYQUO1wdukkdfKOL0lcITu1A8Wv6olFpQna8u/hIW0dY0qdqiHO/kSLjJ
zCJNX/hzx3Cy1oUSrEaIjs5Lv6Nuu0r2mFwS6f8kgg5rXPI97homStro8bmwQQF8
EcyPlq9OXS2Ide/F6IxY/HzkpOlbwzoSsqyjoJCC9mwd+67ItShKUQdx/1c4aZme
6+9s50KyK5Pna5dVi+CVrEkCAwEAAQ==
-----END PUBLIC KEY-----

Here is a ciphertext, encrypted with said public key and encoded in base64:

mFrcsgt06GQ8xAK60D5iMBMc/oDTj/MwvG/obnS6pDl3svhlde4aOfkAIUPlawfl2uDYuX2TD3VB
L5iJYCDRsCoGcxbnQ1kS6Q2zXevBzs33RQg5sanXVt8Jic+OWWVPPwN3JPDuS3Ot4ljgs8eB7LTR
hvmeyVMfT6iue3AMU+B1EOnMpij5I9HQs6eUGO29ROU6WJk7PFYIY6M0FrTVyYXHoSwl+zukQzdu
kYPcj0ST4NsjR93h7drPeyo7y/LVI5mCIp+kPD2SXH1BAzxGAcZLA85MZFHypbqiU+7eO4iBmYPD
BJDU02PiTyB6YGFrsQFZWeVeycdniuCfbQeaGH6eb4qZxHsNhosCEdyxQRF8c4Nh2+q8LwqrPwid
kKcoEqh4/HbBqgXQ/UXLTvUCucowDtW4sDFlT1nsup3Tod0xd3Ea3hEf9qZJnVKe/puHxEB6cwf1
5SbEBBRBCusJ8o6MhmWa2U14dBuO4J+YDJiCiL6PMJ2sCjeTEsKdegx0O82Bvs4sMbbTFZUb/T0u
oC1P0o4MHAFHwNkl85rkgih2d15lyOSsYiZ6TEQ41EE7wckIV/48rjL1JoXIFsxVDsuihXhSOpR4
/LKhXv0OdkrPOeZpjPwNq9eo/DgiCTVwtxWYxvk5UKT+64fefqpyqwM9YOqWEQfJkeh/niVlsrc=

Of course, since you have the public key, you can make as many ciphertexts as you want with it. I just thought I'd include a little message for you when you are done.

Good luck!

Improve this answer
$\endgroup$
4
  • $\begingroup$ I'm not a programmer I'm an aspiring cryptographer beginner $\endgroup$
    – Alberico Lepore
    Sep 30, 2019 at 8:50
  • 9
    $\begingroup$ @AlbericoLepore Then you should read up on what makes RSA secure. It's not the fact that numbers are impossible to be factorized. It's the fact that extremely large numbers are impossible to factorize in any useful amount of time. $\endgroup$
    – MechMK1
    Sep 30, 2019 at 8:54
  • 2
    $\begingroup$ @AlbericoLepore Also, if you are interested in cryptography, you will find that for anything regarding theory, Cryptography is probably a better place. $\endgroup$
    – MechMK1
    Sep 30, 2019 at 8:55
  • 2
    $\begingroup$ That comment with 8 upvotes states it better than your answer, and your answer should be upgraded by including it. $\endgroup$
    – Maarten Bodewes ♦
    Oct 1, 2019 at 15:31
7
$\begingroup$

Your N value, 209, has 8 bits. In practice, RSA uses N values larger than 2048 bits, which can't be factorized in reasonable time in a math software or any other software.

Improve this answer
$\endgroup$
0
5
$\begingroup$

A "hard problem" does not imply that an algorithm for solving the problem does not exist. It implies that the cost of evaluating that algorithm is prohibitive for hard instances of the problem.

A "hard problem" is only hard for hard instances of the problem. There are best case, average case, and worst case instances of a problems.

The difficulty of factoring is determined by the size of the parameters and the structure of the number being factored.

  • factoring $6$ is really easy because it's so small and its factors are small primes
  • factoring $115792089237316195423570985008687907853269984665640564039457584007913129639936$ is also really easy, because it's a power of two
  • factoring the randomly generated integer $107102089598635530157557077256037441386525158258363879432945096511355440164024$ might be easy, it also might be hard (you won't know until you try)
  • factoring $24109984250528632213098528856848389208129257372741149447743709951065146288467$ is really easy, because it's prime.
    • This is a randomly generated prime of the same size as the randomly generated integer from the prior bullet point, yet it is an easy instance of the problem
  • factoring the number $9529945110340784526041551314773112298204342407290463883781690092959200285718\\745501052325913012973624041832221050278901244595303129344418867150320299759\\010364699435744938952075357276465186460469996896472499808293633204156752926397\\618650032074377605409498162209861565255087688285540332247141722449297509904167\\$ will be prohibitively inconvenient (read: "hard") for most, as it is the product of two 512-bit prime numbers.

Factoring is only hard if:

  • The target $n$ is a product of randomly selected large primes
  • The size of $n$ (alternatively, the size of the factors of $n$) is above a certain threshold, which is determined by the parameters of the system

Running a solver on a hard instance of the problem will not complete in any realistic amount of time. Given infinite time, it would yield a solution. But the real world has limits, and cryptographers explicitly design constructions such that the cost required to solve the problem is greater than the resources available.

Improve this answer
$\endgroup$
2
  • $\begingroup$ @MeirMaor Obviously "randomly selected" was implicit. I can make it explicit for you. $\endgroup$
    – Ella Rose
    Sep 30, 2019 at 20:15
  • $\begingroup$ The randomly generated integer 107102089598635530157557077256037441386525158258363879432945096511355440164024 is really easy to at least partially factor, because it's even (and thus has 2 as a factor). $\endgroup$
    – SAI Peregrinus
    Oct 1, 2019 at 1:45
2
$\begingroup$

RSA problem is conjectured hard. As noted, you used a very small number. There was an RSA Factoring Challenges but the challenge was retracted

The remaining prizes have been retracted since the challenge became inactive in 2007.

These were the remaining prize list that nobody can earn anymore;

  • RSA-896 prize is US\$75,000
  • RSA-1024 prize is US\$100,000
  • RSA-1536 prize is US\$150,000
  • RSA-2048 prize is US\$200,000

If you think that your algorithm is a new breakthrough, go on and break one of the challenges and be famous and you can release your results. Or, break some older challenges faster than the previous results to show that your new method is promising.

The last record according to Wikipedia is

  • RSA-768 US$50,000 on December 12, 2009, broken by Thorsten Kleinjung et. al, however, they are not rewarded.
Improve this answer
$\endgroup$
2
  • $\begingroup$ Actually, those prizes were withdrawn a number of years ago. Breaking them may give you some amount of fame (especially if you do something other than throwing more computation at NFS), however it won't earn you any money... $\endgroup$
    – poncho
    Sep 30, 2019 at 16:02
  • $\begingroup$ @poncho good point. Corrected. $\endgroup$
    – kelalaka
    Sep 30, 2019 at 16:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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