Fix rsa8192.pem

Fix rsa8192.pem

Q: How did I do that?

A: That's a long story.

Precondition: I used sage 8.1 for the math, it could probably
done with simple python as well but I did not try.

First I extract numbers from rsa8192.pem:

openssl rsa -in rsa8192.pem -noout -text | sed "s/://g; s/ //g;"

cut&paste the numbers into sage:

modulus
00890d9fd57e81b5ed43283d0ea020
4a1229333d6fb9c37a179375b09c4f
7b5b1cf2eb025979b6d90b709928a0
6725e04caf2b0f7fe94afbdf9f3fa5
66f1ba75c2f6dc488039f410eb5fa8
ab152b8cfdb76791bb853059438edf
ae56bc70a32a9f3e2d883e8b751d08
3797999dc81a9c4d6bdb3a75362fd1
d9c497cf5028dfcdd4cc3eb318e79f
c0db45cbeed955da8a447f0872dee5
65bde4013340e767731441fae4fa54
51356bfbc84e1271b39f111f5f8ef3
a6c8973765b39addef80306194f4ea
89fdfc8e9744866323f6936de89b2f
e2741578b8eb3c41676702fabc50ec
c376e6b7b6e7f94e7d7b5c1bab3c9f
23bb0c8f04d8aca64c309fc063c406
553e1c1421cc45060df7f48c49f5c5
b459d572e273402d6a3ff008657fe9
1936714d1823c5cad53d80630b3216
9bf70feb2ebc1af6a35ee0bf059aed
49c4e367d567e130e2846859b271fd
a8949b182e050819866b8e762ed29f
fb3f7ca14cebfc2488662be4b3980f
c8d31890a05f38ae9690cc7d9d3efc
4808e03da104a8c28bb480bb814995
a6e8b8978ab8350d90b3894e3abf7d
c4ad0956335752c8d6944b38a1715e
7d9950f49e6cdba171fbe651a2ca26
65a7c70b6e8cf3a02c2f93dad8aa95
06481cdb032d04082a5a6c6a733b65
20fa80e2ef57b9cf858ca5ea11e084
bc31a386fc6b099f069786207f80d6
1f2bef294400d59394ad1006431366
a54ae09b0ecd3377dcd8af8fde9b94
fd559b0b7adc5113ba66fc4b3dc842
ee562cfcfd39b4ffc31576635873fc
59535b7aa98605772436c251834e23
4fb2347cc970a49818cac2a9ee95eb
b55fa2da66edd53e11245c6732140a
ae41491288cbf462eef8a807b46d0d
affa38d9ccfe8033d2d4a3cf5c5b82
9df12183f7a05d3650153cd317a017
083ac641c2c3ad11305de0a032be45
c439bd7bbbe3cb97850f9d2c66f72a
4a66e9d434544fc6d294ca3c92627b
e518bfa44e3017ac8ad9c0a26a227d
2e8677da0a4de8edb53ac9530adb63
83c72dbf562dc4d0fea4e492f09eb1
74548381a8686db3aeaaa3a9960cff
25e8c64701115da54fa7a1fb2c566a
fcb4b2a63268d818c3391a62885d13
41b3492c4f0167291b3d026a44e68c
02f2d4d255d4c0906b92a2ced0c0bb
f2bcdceaec1189895af4232dc386c9
75bf3477e5a70d3ab0ac0e5dc37024
0e34a276b155d5e290f77416a1986d
ec47f8c78236ac7df249df9ba21a80
2e6bd75b4fb1c6ffe0f4cf548761a5
6a1fcccee156523a718987f3fdaedc
7171c9050db89a83f24c5a283695b9
c28de6d3b69fc1714b0add335a0ce6
fbbdbd0bbdb01e44969d775105bba3
d2947dca2f291250f9b851e76f514d
dc5a3aa4498e6521314991568860eb
ff1258d8b4aee9ee4159153684c0c0
16c60b17537a50b53cd59aad60678b
d73f0714ab4ccae7416bab417b4907
36d59b2e9f

I used echo `echo "<paste>" ` | sed "s/ //g"
to get everything in one line, put that again
into the clipboard and
then start sage, type N=0x<paste><CR>

sage: N=0x00890d9fd57e81b5ed43283d0ea0204a1229333d6fb9c37a179375b09c4f7b5b1cf2eb025979b6d90b709928a06725e04caf2b0f7fe94afbdf9f3fa566f1ba75c2f6dc488039f410eb5fa8ab152b8cfdb76791bb853059438edfae56bc70a32a9f3e2d883e8b751d083797999dc81a9c4d6bdb3a75362fd1d9c497cf5028dfcdd4cc3eb318e79fc0db45cbeed955da8a447f0872dee565bde4013340e767731441fae4fa5451356bfbc84e1271b39f111f5f8ef3a6c8973765b39addef80306194f4ea89fdfc8e9744866323f6936de89b2fe2741578b8eb3c41676702fabc50ecc376e6b7b6e7f94e7d7b5c1bab3c9f23bb0c8f04d8aca64c309fc063c406553e1c1421cc45060df7f48c49f5c5b459d572e273402d6a3ff008657fe91936714d1823c5cad53d80630b32169bf70feb2ebc1af6a35ee0bf059aed49c4e367d567e130e2846859b271fda8949b182e050819866b8e762ed29ffb3f7ca14cebfc2488662be4b3980fc8d31890a05f38ae9690cc7d9d3efc4808e03da104a8c28bb480bb814995a6e8b8978ab8350d90b3894e3abf7dc4ad0956335752c8d6944b38a1715e7d9950f49e6cdba171fbe651a2ca2665a7c70b6e8cf3a02c2f93dad8aa9506481cdb032d04082a5a6c6a733b6520fa80e2ef57b9cf858ca5ea11e084bc31a386fc6b099f069786207f80d61f2bef294400d59394ad1006431366a54ae09b0ecd3377dcd8af8fde9b94fd559b0b7adc5113ba66fc4b3dc842ee562cfcfd39b4ffc31576635873fc59535b7aa98605772436c251834e234fb2347cc970a49818cac2a9ee95ebb55fa2da66edd53e11245c6732140aae41491288cbf462eef8a807b46d0daffa38d9ccfe8033d2d4a3cf5c5b829df12183f7a05d3650153cd317a017083ac641c2c3ad11305de0a032be45c439bd7bbbe3cb97850f9d2c66f72a4a66e9d434544fc6d294ca3c92627be518bfa44e3017ac8ad9c0a26a227d2e8677da0a4de8edb53ac9530adb6383c72dbf562dc4d0fea4e492f09eb174548381a8686db3aeaaa3a9960cff25e8c64701115da54fa7a1fb2c566afcb4b2a63268d818c3391a62885d1341b3492c4f0167291b3d026a44e68c02f2d4d255d4c0906b92a2ced0c0bbf2bcdceaec1189895af4232dc386c975bf3477e5a70d3ab0ac0e5dc370240e34a276b155d5e290f77416a1986dec47f8c78236ac7df249df9ba21a802e6bd75b4fb1c6ffe0f4cf548761a56a1fcccee156523a718987f3fdaedc7171c9050db89a83f24c5a283695b9c28de6d3b69fc1714b0add335a0ce6fbbdbd0bbdb01e44969d775105bba3d2947dca2f291250f9b851e76f514ddc5a3aa4498e6521314991568860ebff1258d8b4aee9ee4159153684c0c016c60b17537a50b53cd59aad60678bd73f0714ab4ccae7416bab417b490736d59b2e9f

likewise for prime1 (P), prime2 (Q) and
privateExponent (D) and publicExponent (E)

sage: P=0x00c6d6eb9c0f93f8b8de74b2799798c1c1ed47549426a0d76af61f04f0b455184acfeec354c1703709e8727ea0213001738e395b5ca5ed4deec30f8b1ae0e54a516777c5ae897a5562e77dfe378dbba32ee30bcdb275ab7f87f8b9af02712d371a6aa671b44e0f667a6f2d406e5099d942f592ff5c517d452d58cf3f51120062a878fb77066650275b897caf078a5353f1d714963ff90818b6b87c6db438681b4b315c4fd256c1bd383fcf8e67b49a3ee077373a66d77e4c02eebe9350478a51cdfa395d60d905c1189ed7041373f1609075faf9d9f39d3d7b0e7fc8b1d36cb8c5c48731ef5cd87e11f480cdfa4b3ee6cf7eebd3e13f4244647396d52030b82c39d69a3a4075ee90531d1ddb5f1284dc7ab09a3892de5c0ddeed115c7c9ee5fc008658830b0e6f7f366a72f215192498474ade046fc10e92591dfa133e4beff98758e0e92c05f999504a486e3f71c15b73adf7fe0d311f0d0dc1a8e2aff92572475a92e60f970174c80c4948a0cb86635cb438519b18c260ff9f212925e684ef151cc91fa1c4c8dbbc337c9b46f9a93c88cce49e49a670762186e8858051f93ebff7b0b50caadd9b32f93e396b5a6d1cd7f77b2e50e83fae5f3928433268f6cc28810071ce334025a24c7ebf92e631df0d26e99923018946de4ea5e30e868c33ea3d408d8c58815ecf9892fa3afa5f6fbef9a1dfda2da51b6f01f3dae588bdf17b
sage: Q=0x00b073b35a3bba0954b242961630e8e0af8d3ea8aad80d55669e9e79c388983363d96fe471205743001b4798b81de1be3fb06353fd0c9c4fd43f91f9cb2162b00583cc94ff791a615348d01977ca05f4796d5bff41d94dda1cb3ef2433ff4f6500d15ab290a14e651efa91b7df5d5e50f8356188d9842dcdd67c89eb7d40baa78f045969b804f7a985d35a8a8ac32715cb212a34fb89e85e538275e53663fe675944d2b5dba77b7b7abfacd8fbddee4427db6460b728952af882992750c2542d2122247d7f431ec2fe64c0311b0de5290eb619c6ab476308d59f3efff7255d07ebb51fe64ac5967c0b79bae07d36283cf768c8eee2054349cefe90876da66a52e9e0ff20cc00a40fb0c69524e7a01e5c2f07239831a0fa2f56ad405b3a25537907d990e8f5a3e4f3df99dda6afc30d4565aa5881f64adcc6f6be4077893c7e7710623e6158359c3facfef5036779903065fd0d0a2ed8bf2e53a46758dbff06284670bf10bd2e13cba4323ce50fa43df373bd0940011c424f41c5035a10b8095f420ddb67189f6dad62f1257b0f46e353a90eacc145c7db74998a5d0d8772ba1286eb582504465290171e4db87f2e89564214a2317953a7307b1b4c8dad5920866087d7ae80845478813bdf5f6740d0f3b975a344272804b036e4fef09e91d60d1a730fda2f5c222f7636bbe252f9a6caa86d5e8be7e7db2cf912817a0898a4742d
sage: D=0x3b900240c4a416aeb09b123e02f5457bb31023c9249081c5313edaac741686388492020964ce4471a653c9c63c4dc7b74c0188d0ec50bc3a29797da6c9b3616e83dea45ba5d41e6e4cba7eefca6791f45d3c86a491a899a5c42c7e61930a3681d281f34e4b49707e9bba74f68f7a91274c92904b546b5fe6267c5b8ad8d8bb199a523d7fbb5a40748b56dfccf074f3d664e705153dd903b7cd95bac556be3ab59a165d7cbb765e21a4a1d97e34b412baf1caacb57543d2bd8e5ae5cd2a86dc41e256f3f5c0073052859d1c8a12f4973caa88de2e5eb2eef8d6ebdb66fe154d8e383cba74693753affaf4dbc8e2988c08f947b1f8473a7163775656448572c325250ad2cd75c9f5d42721b91ae8fb427773605afa2f4297daf7ab34f5d71144185f3f5cbc94041081fae19fd5d47fc49421080edc5d658b5f223fb1e9b172f4da1a92263fa922225d4c0231e35d94d276fcb0e0999f5f26068528c83f49b0dd79fb157c49fe8b3d80e7cd2b3da76478ebd2ae2c8164583bee2f96591e2f41ad799ae0e2855a5699996fb2c7efb69f86874bca58628e512d579b247e43ee8db04b424e84e44cf753f86e12dd8d2e0ea0b800e6c313317c14658993b8e04c7fb5de1cba0829123dc518957be2a46f76f8ff305fee17b2310bfdd66a93c8b050451f8ceb26c518b7abb72faf08fca0bf6df8a80de511ffc00dc350cd87e52c9cf5771892300e420929da698b6b973da849c89410f089e9b39de79fc1a01a27d2f879ce5cd80ca0a3899d9f480c68d7a5f8c8b3c74936b19f0c7174987df437658046adaffdaddc3540be7fc06a1d2290f58ad9a2992d32e9ecbadf2eed961b4e68c8a89a5709a334082ad297348c4c31c54a3dadccb93afaa9f1786c4167021d4a16dd78afb41131bdd651357bd44f42cfee5d03fdfae087255d18a6a41c03aa6408b6097d8a6848cbbf05a7f20207d5673ea5e6dc849d5d3009c6e8a6c41285cd64f71b536d8345d61f404079278facde0d6e2264cbe655e877468bd3e76380d91f282f26ae17e41a1bac76c148c4c75dd22656816ab259e2c79920e27e6bcfa83732ac6e0a245dcd9cc82f69e45019cf53ac39bebca3ddea0f55ef97b6d8f7b7eadaae792fb1b55c73cf2ed644e651a22c60ed9c0bb063c50fadda6beccbf6c88c41ef1546bab5f21dbe4fbeeb11f3c5c40fa1cc3df2c11bfe7910d1d36a5ec6e66462c7e216481008931039299d23f2be4d838fb010b661a8541a8b7f7bf7d6c8032895e82133e24c835e5a3491249ec69f28e22cf9b0fab9be9ea17026fbadd470eee4676d7ac79976a1c6807e89b5dabab815ffa076caeaeb53f505a31129dac1e9f0b5d919f17aced63574c8524000022b6bc6cb9c8d6a06e44c72e055a1e2706e736af241ab3084fa56cf942aa139440f74e230be31cd8dd4bf0cbdd657f1
sage: E=0x10001

check:
sage: is_pseudoprime(P)
True
sage: gcd(N,P)
811194519730394220204949383061971492284209477134487451053533919242408334468793875483685418435472924384137737409878754330061341487239404629370463160720071782806016579636145456953095810661706004899017496722730291178259805745059054744795252171022091469940626116746608128441399036310378334222880519662696558703165249434265697658704322903051581598088400258377253583825209022558177374913570364047051007093402547387492492645729748176160840842076964161794363721255756097675823463557162877865622894488049720201680509519072521257128596878592149455958732762099800396648453225220977153025222265023206761554302369499402146842619059859650958489842850140873473393484632985863967898676228674751576699965523367097641503814266418957281198265955430221973482931544501209059788536033857660452959160612655542331433647351037413298986228798018950712662579341162832440884265576141868775326408627532047094505284395403786932363148262901839514736964209136867574532808481484592060405175685831168554790879720280778881035860464184791941816702480873202940903024652495084770128062224279875598826600084633389722629461385386069921483006677287847102371176994910369378323222717613076771700378608286670543729473076010314569999636269167049088093674649352610884381826740603
sage: N%P
0

>> P seems to be a prime, and is indeed a factor of N.

sage: is_pseudoprime(Q)
False
sage: gcd(N,Q)
1
sage: ecm(Q)
Found composite factor of 3 digits: 675
Composite cofactor ... has 1231 digits.
Q has a small factor.  The large cofactor
is way too large to be factorized (today).

>> Q must be wrong.

sage: pow(pow(2,E,N),D,N)
2
sage: pow(pow(3,E,N),D,N)
3
sage: pow(pow(5,E,N),D,N)
5
sage: pow(pow(7,E,N),D,N)
7
sage: pow(pow(11,E,N),D,N)
11
sage: pow(pow(1000,E,N),D,N)
1000

>> x^D mod N is indeed the inverse of x^E mod N
>> D seems to be correct.

>> now compute
sage: Qcorrect = N/P
sage: is_prime(Qcorrect)
False
sage: is_pseudoprime(Qcorrect)
True

>> surprise, this is a sage artefact.
>> is_prime is supposed to tell if Qcorrect
>> is a provable prime, but these numbers are
>> too large for a proof.

sage: help(Qcorrect)
class Rational
...

>> oops, it is of course not a rational number.

sage: Qcorrect = Integer(N/P)
class Integer
...

>> okay now it is an integer.

sage: is_prime(Qcorrect)
>> takes way too long: press CTRL-C
sage: is_pseudoprime(Qcorrect)
True

>> so the correct Q seems to be a prime.

sage: Q-Qcorrect
4468358315186607582623830645994123175323958284313904132666602205502546750542721902065776801908141680869902222733839989940221831332787838985874881107673910358472026239723185949529735314601712865712198736991916521419325287976337589177915143787138292689484229106140251936135768934015263941567159094923493376
sage: hex(Q-Qcorrect)
'1a10400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000'

>> interesting, now figure out the bits that are flipped in Q:

Q         ...20ddb67189f6dad...
Qcorrect  ...20dd9c6149f6dad...

$ openssl rsa -in rsa8192.pem -outform der -out rsa8192.der
writing RSA key
$ xxd -ps < rsa8192.der > rsa8192.hex
$ sed "s/20ddb67189f6dad/20dd9c6149f6dad/" < rsa8192.hex > rsa8192.out
$ diff rsa8192.hex rsa8192.out
100c100
< 10b8095f420ddb67189f6dad62f1257b0f46e353a90eacc145c7db74998a
---
> 10b8095f420dd9c6149f6dad62f1257b0f46e353a90eacc145c7db74998a

>> et voila

$ xxd -ps -r < rsa8192.out > rsa8192.der
$ openssl rsa -inform der -in rsa8192.der -out rsa8192.pem
writing RSA key
$ openssl rsa -check -noout -in rsa8192.pem
RSA key ok
$ git diff
diff --git a/apps/rsa8192.pem b/apps/rsa8192.pem
index 946a6e5..83d962f 100644
--- a/apps/rsa8192.pem
+++ b/apps/rsa8192.pem
@@ -1,5 +1,4 @@
 -----BEGIN RSA PRIVATE KEY-----
-
 MIISKAIBAAKCBAEAiQ2f1X6Bte1DKD0OoCBKEikzPW+5w3oXk3WwnE97Wxzy6wJZ
 ebbZC3CZKKBnJeBMrysPf+lK+9+fP6Vm8bp1wvbcSIA59BDrX6irFSuM/bdnkbuF
 MFlDjt+uVrxwoyqfPi2IPot1HQg3l5mdyBqcTWvbOnU2L9HZxJfPUCjfzdTMPrMY
@@ -62,7 +61,7 @@ JH1/Qx7C/mTAMRsN5SkOthnGq0djCNWfPv/3JV0H67Uf5krFlnwLebrgfTYoPPdo
 yO7iBUNJzv6Qh22malLp4P8gzACkD7DGlSTnoB5cLwcjmDGg+i9WrUBbOiVTeQfZ
 kOj1o+Tz35ndpq/DDUVlqliB9krcxva+QHeJPH53EGI+YVg1nD+s/vUDZ3mQMGX9
 DQou2L8uU6RnWNv/BihGcL8QvS4Ty6QyPOUPpD3zc70JQAEcQk9BxQNaELgJX0IN
-22cYn22tYvElew9G41OpDqzBRcfbdJmKXQ2HcroShutYJQRGUpAXHk24fy6JVkIU
+2cYUn22tYvElew9G41OpDqzBRcfbdJmKXQ2HcroShutYJQRGUpAXHk24fy6JVkIU
 ojF5U6cwextMja1ZIIZgh9eugIRUeIE7319nQNDzuXWjRCcoBLA25P7wnpHWDRpz
 D9ovXCIvdja74lL5psqobV6L5+fbLPkSgXoImKR0LQKCAgAIC9Jk8kxumCyIVGCP
 PeM5Uby9M3GMuKrfYsn0Y5e97+kSJF1dpojTodBgR2KQar6eVrvXt+8uZCcIjfx8
@@ -98,4 +97,3 @@ TwEgE67iOb2iIoUpon/NyP4LesMzvdpsu2JFlfz13PmmQ34mFI7tWvOb3NA5DP3c
 rMlMLtKfp2w8HlMZpsUlToNCx6CI+tJrohzcs3BAVAbjFAXRKWGijB1rxwyDdHPv
 I+/wJTNaRNPQ1M0SwtEL/zJd21y3KSPn4eL+GP3efhlDSjtlDvZqkdAUsU8=
 -----END RSA PRIVATE KEY-----
-

>> DONE.

Fixes #11776

Reviewed-by: Paul Dale <paul.dale@oracle.com>
Reviewed-by: Matthias St. Pierre <Matthias.St.Pierre@ncp-e.com>
(Merged from https://github.com/openssl/openssl/pull/11783)

(cherry picked from commit 7ef43790617cb08b4bb4141df716dfb37385fe5c)