So, I'm kinda newbie in this cryptography stuff, I just like to understand complex things.A couple of months ago I was learning and I maybe found a pattern in prime numbers and their multiplications, lets check out.

So, it's high demanding to multiplicate random prime numbers, correct? I thought this: Instead of multiplicate the numbers, you can just isolate the last number of each one and sum them up, for example: 23518 and 619741, we can just take the last digit of both and get 2, right? I found out that, if the sum result equals to 2, the ending number in the multiplication it will ALWAYS be 1 (tested with 20k prime numbers)

enter image description here

This also holds true for all sums (2, 4, 6, 8, 10, 12, 14, 16 and 18) Table: 1 [(1, 1), (3, 7), (9, 9)] 3 [(1, 3), (7, 9)] 5 [(1, 5), (3, 5), (5, 5), (5, 7), (5, 9)] 7 [(1, 7), (3, 9)] 9 [(1, 9), (3, 3), (7, 7)]

So in the RSA-260 challenge number

( 2211282552952966643528108525502623092761208950247001539441374831912882294140 2001986512729726569746599085900330031400051170742204560859276357953757185954 2988389587092292384910067030341246205457845664136645406842143612930176940208 46391065875914794251435144458199) we know that the last digit sum MUST BE, 6, 10 or 14, right? reducing our possibilities by a lot.

Can anyone confirm this for me? I'm really dumb in programming but I think this is a start. Check out the spreadsheet I did. https://docs.google.com/spreadsheets/d/1rcAIz5094WGqVZLGgCiTZotzrHg8TeQ2kQSB6lhAEaU/edit?usp=sharing


Yes, this stems from elementary school arithmetic: If you multiply two numbers ending in 1 the resulting least decimal digit or result will always be 1. Primality not required. This does not however mean that if the resulting decimal digit is 1 both original primes end in one: e.g 7*3 or any primes ending in 7 and 3 respectively.

The best way to break RSA (excluding rubber hose cryptography) is to factorize the composite n. This is typically done using: https://en.wikipedia.org/wiki/General_number_field_sieve

Your observational on the behavior of the least significant digits though correct, does not obviously lead to any superior attack.

I use 2048 bit RSA and feel secure, and sometimes 4096 bits for extra safety margin. I expect this to remain this way for many years to come.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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