mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Lounge

Reply
 
Thread Tools
Old 2019-09-16, 07:56   #1
jdcs
 
Sep 2019

10002 Posts
Talking 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.
jdcs is offline   Reply With Quote
Old 2019-09-16, 08:14   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

71·139 Posts
Default

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
LaurV is online now   Reply With Quote
Old 2019-09-16, 08:50   #3
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

633110 Posts
Default

Quote:
Originally Posted by jdcs View Post
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:

<snip>
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!?
retina is offline   Reply With Quote
Old 2019-09-16, 11:13   #4
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

1,531 Posts
Default

Quote:
Originally Posted by jdcs View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2019-09-16, 15:09   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2×5,569 Posts
Default

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

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. 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
xilman is online now   Reply With Quote
Old 2019-09-16, 16:27   #6
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

1,531 Posts
Default

Quote:
Originally Posted by xilman View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2019-09-16, 17:57   #7
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2×5,569 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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.
xilman is online now   Reply With Quote
Old 2019-09-17, 02:53   #8
jdcs
 
Sep 2019

10002 Posts
Default

Quote:
Originally Posted by LaurV View Post
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 View Post
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//////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////ADAhMAkGBSsOAwIaBQAEFLFmtP3VkQJB2MCk
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.
jdcs is offline   Reply With Quote
Old 2019-09-17, 09:55   #9
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

153110 Posts
Default

Quote:
Originally Posted by jdcs View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2019-09-18, 06:58   #10
jdcs
 
Sep 2019

810 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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)?
jdcs is offline   Reply With Quote
Old 2019-09-18, 14:24   #11
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009

37318 Posts
Default

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?
storm5510 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
I want to factorize 2^1277-1 tanaydin Information & Answers 69 2021-11-07 23:53
Question: Is Our Forum Secure in Some Areas 9021951 Information & Answers 7 2011-11-02 23:29
World Cup Soccer davieddy Hobbies 111 2011-05-28 19:21
Plans for the end of the world Oddball Lounge 4 2011-04-18 04:06
Change the world! 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔