mersenneforum.org Behold, "The World's Most Secure RSA key"®©™ : 2^1277-1
 Register FAQ Search Today's Posts Mark Forums Read

 2019-09-16, 07:56 #1 jdcs   Sep 2019 10002 Posts Behold, "The World's Most Secure RSA key"®©™ : 2^1277-1 Since the world's Mersenne Forum's best minds have tried to factor M1277 and none has succeeded, it must mean that 2^1277-1 is impossible to factor ... which makes it the world's most secure RSA modulus: Code: -----BEGIN PGP PUBLIC KEY BLOCK----- mKsEXX4CgwEE/R////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// //////////////////////////////////8AAQG0GE1lcnNlbm5lIDEyNzcgPDJe MTI3Ny0xPojVBBMBAgAgAhsDBAsHCAkDFQgCBBYDAgECHgECF4AFAl1/L18CGQEA CgkQwOplJxxx/xFMOgTxAf////////////////////////////////////////// //////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////ADAhMAkG BSsOAwIaBQAEFEw6OaDNBA4AZdu9aCnhmS7hlB6vuKwEXX7xkgEE/R////////// //////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// //////////8ACwT9iL4EGAECAAkFAl1+8ZICGwwACgkQwOplJxxx/xFItQTxAf// //////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// ////////////////////////////////ADAhMAkGBSsOAwIaBQAEFEi1Kw2NUHLo 5j00UwH3YABnS0aA =A2gW -----END PGP PUBLIC KEY BLOCK----- (All those slashes are from the 1's in the M1277.) Obviously, please don't encrypt anything to this key, because it will be forever un-decryptable, and the no one will never be able to read your message.
 2019-09-16, 08:14 #2 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 71·139 Posts We believe that the number in cause is quite near to be factored... Just wait and see... You should have chose some RSA-2048 or so, for the candidate (although, many "keys" can be given, with a random higher length, which are more difficult to crack). (edit, yeah, I know, there is nothing like a joke killer...) Last fiddled with by LaurV on 2019-09-16 at 09:35
2019-09-16, 08:50   #3
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

633110 Posts

Quote:
 Originally Posted by jdcs Since the world's Mersenne Forum's best minds have tried to factor M1277 and none has succeeded, it must mean that 2^1277-1 is impossible to factor ... which makes it the world's most secure RSA modulus:
Yep. No factor up to 11 so you are correct.

Are you sure it is more secure than RSA's 2048 bit "modulus"? That also has no factor up to 11. I'm confused!?

2019-09-16, 11:13   #4
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

1,531 Posts

Quote:
 Originally Posted by jdcs Since the world's Mersenne Forum's best minds have tried to factor M1277 and none has succeeded, it must mean that 2^1277-1 is impossible to factor ... which makes it the world's most secure RSA modulus:
If you want to use it then you have to factorize M1277. Learn more.

2019-09-16, 15:09   #5
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2×5,569 Posts

Quote:
 Originally Posted by R. Gerbicz If you want to use it then you have to factorize M1277. Learn more.
Emphasis mine.

AFAIK, although it is widely believed that breaking RSA is as hard as integer factorization, there is no proof of this. Neither is there a proof that an efficient attack on breaking RSA yields a factorization of the modulus; the converse, of course, was proved a very long time ago.

One way of breaking RSA which does not yield a factorization (AFAIK) is to encrypt each possible plaintext in turn until the ciphertext is produced. This is a mildly inferior algorithm to factoring the modulus by trial division in that the latter has an obvious optimization: test only prime divisors, which have a density O(N / log N) whereas trial plaintexts have density O(N).

Last fiddled with by xilman on 2019-09-16 at 15:10

2019-09-16, 16:27   #6
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

1,531 Posts

Quote:
 Originally Posted by xilman If you can prove this statement please publish your proof. You will become famous. Otherwise, learn more. AFAIK, although it is widely believed that breaking RSA is as hard as integer factorization, there is no proof of this.
Learnt this, but there should be a better wording on this, beacuse if n is a Carmichael number (OK, poor choice for RSA) then actually you don't need to factorize n, although a factorization on these numbers is in polynomial time, but just one RSA decryption is faster.

2019-09-16, 17:57   #7
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2×5,569 Posts

Quote:
 Originally Posted by R. Gerbicz Learnt this, but there should be a better wording on this, beacuse if n is a Carmichael number (OK, poor choice for RSA) then actually you don't need to factorize n, although a factorization on these numbers is in polynomial time, but just one RSA decryption is faster.
The better wording might be "solving RSA for arbitrary values of the public modulus". This pedantic wording is generally understood but you are correct, it should be made explicit.

2019-09-17, 02:53   #8
jdcs

Sep 2019

10002 Posts

Quote:
 Originally Posted by LaurV We believe that the number in cause is quite near to be factored... Just wait and see...
Heh, haven't they been saying that the past 10 years? At this point, I'm sure it'll never be factored, so M1277 is perfectly secure :)

Quote:
 Originally Posted by R. Gerbicz If you want to use it then you have to factorize M1277. Learn more.
Nah, we only need to factor it if we want to decrypt any messages encrypted with the key. If we just want to encrypt messages, we can do it without the factors.

But guys, I goofed. I wanted to make a real PGP key with n=M1277. But I got too excited, and made the key above with e=1277 -- and that's the one RSA exponent that does not work :(

So here's the corrected key instead. This is an RSA key with n=M1277, e=65537:

Code:
-----BEGIN PGP PUBLIC KEY BLOCK-----

mKsEXYBAPgEE/R//////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
//////////////////////////////////8AAQG0GE1lcnNlbm5lIDEyNzcgPDJe
MTI3Ny0xPojRBBMBAgAcAhsBAh4BAheABQJdgEEOBAsHCAkCFQgEFgMCAQAKCRBG
eU+ty/qRMQ8cBPEB////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////8AMCEwCQYFKw4D
AhoFAAQUDxwCfLqEuWPYnX3zd2kOycbgFUS4rQRdgEIwAQT9H///////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
/////wARAQABiL4EGAECAAkFAl2AQjACGwwACgkQRnlPrcv6kTGxZgTxAf//////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
VEbJ3hrY7xiJ
=f9Li
-----END PGP PUBLIC KEY BLOCK-----
It's a real and fully usable PGP key. Go send messages to it -- no one will ever be able to read them until we factor M1277.

2019-09-17, 09:55   #9
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

153110 Posts

Quote:
 Originally Posted by jdcs But guys, I goofed. I wanted to make a real PGP key with n=M1277. But I got too excited, and made the key above with e=1277 -- and that's the one RSA exponent that does not work :( So here's the corrected key instead. This is an RSA key with n=M1277, e=65537: ... It's a real and fully usable PGP key. Go send messages to it -- no one will ever be able to read them until we factor M1277.
Probably it is not very known, but there is a huge trap in your method:
if gcd(65537,eulerphi(n)) != 1, then the decryption (in general) is not unique!!!!!!
Not speaking about that it would be a way slower (in these cases), you need to find the original message in a haystack.

2019-09-18, 06:58   #10
jdcs

Sep 2019

810 Posts

Quote:
 Originally Posted by R. Gerbicz if gcd(65537,eulerphi(n)) != 1, then the decryption (in general) is not unique!!!!!!
Heh, that is highly unlikely. What are the chances that 65537 is a factor of φ(M1277)?

 2019-09-18, 14:24 #11 storm5510 Random Account     Aug 2009 37318 Posts The rule of digits I memorized, 2 * log(2) * 1277 indicates 768 digits. Is the implication here meaning this exponent has no factor, or is it saying that current factoring software cannot run it?

 Similar Threads Thread Thread Starter Forum Replies Last Post tanaydin Information & Answers 69 2021-11-07 23:53 9021951 Information & Answers 7 2011-11-02 23:29 davieddy Hobbies 111 2011-05-28 19:21 Oddball Lounge 4 2011-04-18 04:06 Xyzzy Lounge 5 2009-08-31 12:41

All times are UTC. The time now is 08:26.

Sun Jan 23 08:26:52 UTC 2022 up 184 days, 2:55, 0 users, load averages: 0.77, 0.97, 1.16