Talk:RSA numbers

Verifiability and notability

For some reason, the RSA challenge has consistently attracted mathematical cranks and pretenders over the years. Likewise, the Internet loves articles that claim that such-and-such has solved, or are about to solve, various RSA challenges. Let's be clear: the solution to each of these challenges is a pair of prime numbers whose product is the semiprime in question. No more, no less. Links to articles claiming that these challenges "have been solved by me", or "will be solved soon," or "will never be solved," or other such meta-discussion, have no place on Wikipedia. Likewise, links to breathless popular articles claiming that the RSA-2048 challenge is "about to be solved", do not constitute supporting evidence.

Two prime numbers. That's what we require. Publish your prime numbers on arxiv.org or someplace else, and then we'll update Wikipedia.

Merger proposal

Other than RSA Factoring Challenge, the content of Category:RSA Factoring Challenge is 54 similar stubs about individual RSA numbers: RSA-100, RSA-1024, RSA-110, RSA-120, RSA-129, RSA-130, RSA-140, RSA-150, RSA-1536, RSA-155, RSA-160, RSA-170, RSA-180, RSA-190, RSA-200, RSA-2048, RSA-210, RSA-220, RSA-230, RSA-232, RSA-240, RSA-250, RSA-260, RSA-270, RSA-280, RSA-290, RSA-300, RSA-309, RSA-310, RSA-320, RSA-330, RSA-340, RSA-350, RSA-360, RSA-370, RSA-380, RSA-390, RSA-400, RSA-410, RSA-420, RSA-430, RSA-440, RSA-450, RSA-460, RSA-470, RSA-480, RSA-490, RSA-500, RSA-576, RSA-617, RSA-640, RSA-704, RSA-768, RSA-896.

The RSA Factoring Challenge ended in 2007 [1] while most of the numbers were still unfactored. Maybe they will be factored anyway when it becomes feasible, but the interest in them now appears limited, and all 54 articles seem likely to remain in Category:Cryptography stubs. I suggest leaving RSA Factoring Challenge as it is and merging all 54 stubs into a new article called RSA numbers. The lead can contain common details and explanations, and each number can then get its own section with same name as the current stub, and basically the same content except redundancies. The stubs can redirect directly to the section about that number. Seeing the numbers together seems more reader friendly to me than 54 stubs with almost the same opening, a decimal expansion, and essentially nothing else for all the unfactored numbers. I also think most of the current stubs (at least all the unfactored numbers) fail Wikipedia:Notability on their own. Schneelocke created most or all the articles and said "I'd not be opposed to a merge" in [2]. I also considered "List of RSA numbers" as name, but in Wikipedia "List of ..." usually implies a list of items with links to other articles (see Wikipedia:Lists (stand-alone lists)). PrimeHunter (talk) 16:50, 15 February 2008 (UTC)

In favor of merge. 54 stubs seems weird, and instead a "list"-like article, merging the above-mentioned numbers, seems a good idea. 212.242.167.26 (talk) 19:06, 26 February 2008 (UTC)

There are no objections after 24 days so I will perform the merger. PrimeHunter (talk) 00:50, 10 March 2008 (UTC)

I have completed the merger and redirected the 54 former articles to the corresponding section. PrimeHunter (talk) 04:52, 11 March 2008 (UTC)

the page

lower level encryptions are marked as unsolved while higher level encryptions are marked as solved... can we just assume that the codes are breakable and not just make up a new odd count and say its unbroken. under that assumption I declare rsa 91 unbreakable. — Preceding unsigned comment added by 98.206.91.158 (talk) 04:26, 2 July 2013 (UTC)

As for why this happens: "The previous challenge, RSA-140, was factored earlier this year. RSA-155 was significant because it matched a common benchmark, 512 bits. RSA-150 hasn't been done yet, since RSA-155 was the more interesting milestone, even though RSA-150 would have been a little easier (since it's shorter than RSA-155)." - https://web.archive.org/web/20061229220749/http://www.rsasecurity.com/rsalabs/node.asp?id=2511 Solomon Ucko (talk) 18:47, 26 October 2023 (UTC)

RSA-200 single computer effort

According to the source http://www.crypto-world.com/announcements/rsa200.txt the single computer effort was the equivalent of 55 years, not 75. Am I missing something or is that a mistake? 89.122.248.132 (talk) 22:40, 15 January 2009 (UTC)

You and at least five others [3][4][5][6][7] are missing that there were two phases: sieving for 55 years and the matrix step for 80 × 3 months = 20 years. The mistake was so common that I added a comment to stop people from readding it: [8]. The comment is still in RSA numbers#RSA-200 where the article was merged so I guess you would have seen it if you tried to change it, but thanks for asking here first. PrimeHunter (talk) 01:13, 16 January 2009 (UTC)

RSA-2048

I think i have an answer to RSA- 2048. It is simply 3 and 1731969491885964498009061080016132857143094042068010675925712612014554006902531852088006175293594802306096880416505027396432853049725394834269496373357614997562464269095925578657139449090087298791671657274897055025871126619698566699110153249602809467265809700214152897272398372915373838390884877427405623329183060807477879086361713955154014525599474462394924815973579978078861607941427066054605003558270150553459102018733873225418711281381201277968138317544810730038219181484726141340308205505241116926235916605708590822654308795452124429970718277146055966628346815121341175793983792878854797070670132374274040240119 71.68.22.243 (talk) 01:39, 19 November 2009 (UTC)

I don't know whether you are serious. Your large number starts 173... and RSA-2048 starts 251... so there is clearly not a factor 3 between them. But if we remove the initial digit 2 from RSA-2048 then your number would be correct: RSA-2048 = 3×(your number) + 2×10⁶¹⁶. By the way, your number is composite and its prime factors include 3, 19, 2544428255363, 208173594889846026817379. PrimeHunter (talk) 03:11, 19 November 2009 (UTC)

Magic words in RSA-129

How are these words encoded in the prime factors? --RokerHRO (talk) 10:52, 12 March 2010 (UTC)

I guess you refer to The Magic Words are Squeamish Ossifrage. See RSA for how RSA encryption works. RSA-129 or any other RSA number can be used to encrypt any text. "The Magic Words are Squeamish Ossifrage" was an example text that was encrypted with RSA-129 but there is no connection between the example text and the prime factors of RSA-129. However, you need the prime factors to decrypt the encrypted version of the text. PrimeHunter (talk) 13:58, 12 March 2010 (UTC)

Question about RSA numbers

All the RSA numbers that have been factored not only have exactly two prime factors, but appear to have exactly two prime factors of roughly equal size. How do they know in advance that the given RSA numbers are not prime, for one, and that their two factors are about the same size, for two? Did they already know the answers, and were putting the RSA numbers out there to see who could manage to factor them, and thereby encourage research in this area? Or did they have some way to know each number would have exactly two equal-sized prime factors?

Leisulin2 (talk) 02:19, 13 June 2012 (UTC)

They used a computer to find two random primes of equal size satisfying certain other criteria. They then multiplied them, stored the product, and deleted the original primes. Assuming this deletion was done honestly and correctly, they no longer know the prime factors and have no way of retrieving them other than trying to factor the numbers in the same way as others. See http://www.rsa.com/rsalabs/node.asp?id=2094#HowWereTheNumbersGenerated which is referenced in the fourth paragraph of RSA Factoring Challenge. By the way, there are many known primality tests which can easily determine that numbers of this size are composite without finding a prime factor. But apart from factoring the numbers which is hard, there are no known tests to determine whether they have exactly two factors or the factors are of similar size. PrimeHunter (talk) 10:41, 13 June 2012 (UTC)

Enigmail uses 2048

Enigmail uses 2048 bits. Does that change RSA-1024 at all? --XndrK (talk · contribs · count) 21:16, 24 August 2013 (UTC)

What do you mean by "change"? In this article, RSA-1024 refers to a specific 1024-bit number and not to 1024-bit RSA encryption in general. PrimeHunter (talk) 00:05, 25 August 2013 (UTC)

amibiguous wording

The article describes semiprimes as "numbers with exactly two prime factors." This could be taken to mean "numbers with multiple possible factors, exactly two of which happen to be primes." More precisely, "semprime" means: "numbers with four factors: 1, itself, and exactly two prime numbers." For example, 10 has factors 1, 10, 5, and 2. — Preceding unsigned comment added by Lashdown1 (talk • contribs) 15:17, 30 April 2015 (UTC)

The article says "semiprimes (numbers with exactly two prime factors)". This is the normal meaning of "exactly" when prime factors are counted, but readers who are in doubt can just click "semiprimes". It's very common to have links to articles with further details. "numbers with four factors: 1, itself, and exactly two prime numbers" is too cumbersome for an article about RSA numbers, and it's also wrong. The square of a prime is a semiprime but it only has 3 factors, and only one of them is prime. For example, 9 = 3×3 has factors 1, 3, 9. Furthermore, "factors" is often implied to mean prime factors so it should say divisors instead if the goal is to avoid ambiguous wording. PrimeHunter (talk) 15:46, 30 April 2015 (UTC)

More accurate would be to say it uses the product of 2 different primes. 'n' can be 35 because its prime factors are different from each other. But RSA won't work with n=49 because p and q must be different from each other. And, there is a variant of 3-prime RSA, where n=p*q*r with all 3 being primes. Silversplash (talk) 13:18, 9 August 2022 (UTC)

Naming Convention

Why is there such a disparity among the names of these numbers?
It seems like they like to alternate between using the number of bits and the numbers of digits; why can't people just pick a convention? 68.82.207.136 (talk) 00:57, 25 August 2015 (UTC)

The lead of RSA numbers says: "The first RSA numbers generated, from RSA-100 to RSA-500, were labeled according to their number of decimal digits. Later, beginning with RSA-576, binary digits are counted instead."

We list the numbers in increasing order and not by publication date. That's why the naming convention often changes in the list. PrimeHunter (talk) 12:18, 2 October 2016 (UTC)

Is RSA cryptosystem broken ?

Look at Bosons1978 (talk) 15:30, 11 February 2021 (UTC)

References

Decryption keys for all solved RSA numbers

If this is too long, can instead use only the info about the largest solved RSA-250. Assuming e=65537, and the public key's 'n' is the RSA Number, here is the smallest 'd' for each RSA Numbers solved so far:

calculated as:

phi = (p-1)*(q-1)
verify gcd(phi,e) = 1 (since e=prime, equivalent is verify phi mod e > 0)
lcm = phi / gcd(p-1,q-1)
d=(1/e mod lcm) (multiplicative inverse of e modulo lcm)

the encryption/decryption would then be

ciphertext = number ^ 65537 mod RSA-number
original = ciphertext ^ d mod RSA-number

signature would be the reverse

signature = message_number ^ d mod RSA-number
verify = signature ^ e mod RSA-number

Examples for RSA-100 through RSA-250

RSA-100 bits(d)=329 674017055519394793615501054018264656488178175949461081885760669667137709962139271405715164532578733 RSA-110 bits(d)=360 1649428372106933849588404407500446088729594116806830386931404977866954595872638089493542019852236258928536033 RSA-120 bits(d)=395 72761679205516841695522601578696797363729760559784196552815142907219620114581442879614630977718023137750190028914578865 RSA-129 bits(d)=424 25576912737467718746291912150471253831526413840664456913860920811612904469387504992731026761859802224663184146331463834621351969 RSA-130 bits(d)=427 254489282962912593749039635158525801058390637022188836110375625123010747816390406715398187206626365165411715754336683173420788779 RSA-140 bits(d)=462 9969742502467341192821402416014842550756654123334850984494917591413461975458013427359819501409471867269988361151467518077502245429391330497 RSA-150 bits(d)=495 61444786624354444936935462062916489782489971809844764895695549796756450678621566040699302164943525574130287428336155789152259995199212234116653748233 RSA-155 bits(d)=511 3356466021486090045135760806907538481037017976643893331115734351758556847035118151411660174418113083512004316778795782290583978801930873301988747470904865 RSA-160 bits(d)=528 497166683861051849841267346376402174108229430000972409446123069210910389847872820592375928122389685467078133878078473048713988520533482832762124506673040404535 RSA-170 bits(d)=559 1055582046407532721999965896888724996831095896224398007703045466380446117396795066791289987775037764520035099257693274730827518908030845062952298291007440778026518303729 RSA-576 bits(d)=574 48318251158920145864930035723053089097690375168562443830554407970661009102774592695057202204701378327623682075089028698815133956650193819978456750305738325912711134934968241 RSA-180 bits(d)=588 648588132299459043435653182815352056886381990566762333306741512377432055158563226737497254732273332589193081038405957288362126893747803079702220826989743493310201453684104066041 RSA-190 bits(d)=624 35529030358312758463403087851071219877047376659986945264967647356886718229080498383125000896869870631530481463822087606774769643861381727314108881295458266856585154789133264693797645590987 RSA-640 bits(d)=638 910338839255513594276114642324832689515113980889710354670708902397594519961653811537445732277678004222540118329476931498612079090499977102461065894251786947340598766673618720179745389830242183 RSA-200 bits(d)=662 10023973860458935214629028314921145680101270479410442577556312815382276832630803144587417589218107730987707185221426712308842771610371452124236260109140093479944659458046086660843312930256071913912769 RSA-210 bits(d)=694 61959981734537078212325727674617465946988663457039453582733185593971839659175182077981692640370184394681886086573712402174233346565767780644367735588565491790845748563869681519355799478576445382805794296012633 RSA-704 bits(d)=703 33307131606083860709359654688809620595435784183304180784765475180353602262817269247014766169336517530471801339770560112997370264392886185538231911908428012730752492181217073681726139624557304859252988692991966953 RSA-220 bits(d)=725 108873725181563880907896330797296085419608448005360866376856147732143978076801208447950447593952747247817932522278964171455603168731429913030949244067567110352773891991761510894092458138682974665894042213097315918777165 RSA-230 bits(d)=759 1639715765576499753261847157492109881847156743555050606129872543237996966056688605749786218247959147946493214243581120848763475487967202953578356947107596178040063843659287900742440094274961237224025378856310764824262676982125373 RSA-232 bits(d)=765 140263445445003342932149998481040294415413787087456122902666425053993574190670248627037665960671034610370844595006744370568120076897687690856852182084347222226497720680391611892407399985328357429169244522213002364686909013714364373 RSA-768 bits(d)=764 88720529844692335163713389700574123010404693481428046680816097320523289622619004184847478496075358157554195016815253686520349518198216304347646693811151005917447460056848821441443677696643233522329969838892699195527436526242242049 RSA-240 bits(d)=792 22994213731295823676947530050559667742390792689250743222761893351407301154971518985680200627180376154374827039875826798083334437333283706195620178884424237253880622540760392003939565900121123512977714045301726042805342128125288979246774813 RSA-250 bits(d)=825 148840038351956836000467036246170296373220647333143430331160536062332158045994494297145844382244073230802446288490260360306160856830644396530404954915750385548867348272108765714390476042628759717046390986500425752657379890882687560837119741956970823

The following is how OpenSSL would create a self-signed RSA key pair using the primes in RSA-250 in .pem format, which can be verified with: openssl pkey -in filename.pem -text -out filename.txt (shows numbers in base16 not base10)

Example private key & certificate

-----BEGIN PRIVATE KEY----- MIICBAIBADANBgkqhkiG9w0BAQEFAASCAe4wggHqAgEAAmgTIdL93ei9nf83mv8D DeIFuEbrXOzED6iqnCqFzj6ZIZPoc7K8Zn2r4qw+6d0js6ntnsDDx0RWY/VFVGm3 J91vvAOxv5XQOhPANoZFdnYwx+q/Xnq1+ie5St5+HiO8xl0qfe0cWzZLUQIDAQAB AmgK5YLUECVUib4oH2EKjkei1leeCWjYKcr4kMUvPE4uzQ7+n5a28vC0iv9rPasz gEpSCc7j3oGmPLiLK2cR7+Uo70jWmshdj7iqVITp9HO/Q9bCpaWNXSf+tmb2ftRz nYuVtHKRteJYeQI0YQT6+B9B/ddha0N49r2ZEpLLLyHBDQbF6OVxpelit+gt/Z/n Eg9tA6hsxrvH3TpigIOe9wI0Mnuf2kshHjv9tU9oDlwEUoqqIEKK4Aj69I32yRP1 dH2GCKWkjiv+QfrnoEaD8jBYUs2t9wI0ToBdIY8JMn+nj8cUhXF7/g9Q4F4LeqLU WFHu1zQ0cGIpdGKB8ZcRujf5bARc/6BSO3JEmQI0LwbOgFFgRoPn8ZBJBKdfN20I 0ghqygxTiqD8dY/sJVoRE9kKE46Tye7q+nj1zRSQEoKbPQI0NPa0sgj5wUggHa4L vptQXiYNnEAUDDbKVopwHjonFAWw4V2fBOlxTpNi2p3snTL6QWZ9DA== -----END PRIVATE KEY----- -----BEGIN CERTIFICATE----- MIIB1TCCAVegAwIBAgIUUlNBLTI1MCBOdW1iZXIgS2V5Li4wDQYJKoZIhvcNAQEN BQAwFzEVMBMGA1UEAwwMc2lsdmVyc3BsYXNoMB4XDTIwMDIyODAyNTAwMFoXDTM4 MDEwMTAwMDAwMFowFzEVMBMGA1UEAwwMc2lsdmVyc3BsYXNoMIGDMA0GCSqGSIb3 DQEBAQUAA3IAMG8CaBMh0v3d6L2d/zea/wMN4gW4Rutc7MQPqKqcKoXOPpkhk+hz srxmfavirD7p3SOzqe2ewMPHRFZj9UVUabcn3W+8A7G/ldA6E8A2hkV2djDH6r9e erX6J7lK3n4eI7zGXSp97RxbNktRAgMBAAGjUzBRMB0GA1UdDgQWBBQVUAxvva4E sHnyZUy/9JJv4Yw/RzAfBgNVHSMEGDAWgBQVUAxvva4EsHnyZUy/9JJv4Yw/RzAP BgNVHRMBAf8EBTADAQH/MA0GCSqGSIb3DQEBDQUAA2kAB47vZUWOhXMqdNFnZm0o JkYxSrQaWJmNz7J2VxXGLW3zXTZSPvcLaoW5HmoxNsDn0fUjIBr1EepCdTZtrGK9 WjS3IF9s0Jvr0laQSMbj5QRXwjIW1kapHdLWZhTOKKnAquIuZ8YaUP0= -----END CERTIFICATE-----

Silversplash (talk) 20:32, 9 August 2022 (UTC)

@Silversplash: Wikipedia is based on published reliable sources. If they don't give this data then neither should we. It's useless for real encryption when the factorizations are publicly known. If the purpose is to illustrate how RSA works then it belongs in RSA (cryptosystem) but it already has a more practical example with small numbers. PrimeHunter (talk) 23:54, 9 August 2022 (UTC)

Question on External links

I built a github repo that is work in progress, which started with this Python script:

https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/python/RSA_numbers_factored.py

It contains all RSA numbers from this Wiki page with entries l, n=p*q=RSA-l[, p, q[, pm1, qm1]], where pm1 and qm1 are prime factorization dictionaries for p-1 and q-1, allowing for efficient computation of .totient_2() and .reduced_totient_2() functions (.totient(.totient(n)). For simpler than RSA-100 testing RSA-59 and RSA-79 examples are provided as well.

Utility class RSA provides other useful functions, like providing both sum of squares and both difference of squares for RSA numbers.

Example:

>>> from RSA_numbers_factored import RSA, digits
>>> RSA=RSA()
>>> l,n,p,q = RSA.get(59)[slice(4)]
>>> l == digits(n)
True
>>> n == p * q
True
>>> RSA.square_sums(59)
[[38768728061109707828243001823, 264836754409721537369435955610], [93861205413769670113229603198, 250662312444502854557140314865]]
>>> for a,b in RSA.square_sums(59):
...     a**2 + b**2 == n
... 
True
True
>>> 

Python script has been manually transpiled to JavaScript/NodeJS as well, see example animation: https://github.com/Hermann-SW/RSA_numbers_factored/raw/main/Peek_2022-12-18_22-29.gif

This library is useful for working with RSA numbers, and I think an external link to this github repo can help others with interest in RSA numbers "to play with them" in Python and/or JavaScript (with arbitrary precision arithmetic).

On the other hand I want to ask here whether such a link could be added to this Wiki page, or not? HermannSW2 (talk) 22:49, 6 February 2023 (UTC)

Table too wide

The lede table is way too wide and exceeds the standard article width.

Unless someone objects, I would remove the announcement, number, factorization, and notes columns, as these are covered in the details. Wqwt (talk) 01:31, 28 September 2024 (UTC)