These are some Sophie Germaine prime numbers that I've generated. I hereby release these numbers into the public domain - whatever that means.
These primes are well suited for use in Diffie-Hellman key exchange. i.e. not only are they prime, but the number (p - 1) / 2 is also prime. The numbers are encoded in hexadecimal (base 16). These take a little while to discover. Finding secure generators for these numbers is easy, as the prime factorization of (p - 1) is known. Some people involved in the standardization process of IPSec indicate that to ephemerally generate a 128-bit session key, a modulus of 2550 bits is of the appropriate minimum strength. This is when time is the constraint on a brute-force search. See the collected notes below for further details.
Mail the idiot in charge.
2048-bit secure Diffie-Hellman modulus #1
This is too small to protect a 128-bit generation at full strength.
9aebdbd054a6cfc9db5bcb8f3eaa82c9d8b925018b77954013e170025a7f420b
eb57b7b905869b53a24d08ce5cb76dc812e8081e4140704e0d3875dee731962f
56420f6eea5cd0810513fe9fcb0227852ec4fd289ced1b3e87b62f6ce5fcef95
5273d28e916db157e6ff7b1038db41608da42d701f83d9ed34a90c6047705a66
57bb75347718d17879be72f38296b13ddab9df4fc7cf2c6a0fb03e86efa18dc0
123ffba51a0afb6c8d977640faf1dfde83c96186524a02879e84e22503c3d95c
a66380889da78ea0ba8ba68c3b2167442a059fe13654ac75f422374e4648bfb6
d35dfde06ba961dee283e0cbb4fc682f32fea0813814c62806b433e9bb332cab
2048-bit secure Diffie-Hellman modulus #2
This is too small to protect a 128-bit generation at full strength.
fa6d3cb85ca608b967329e2b7514e976a9b5a707875f408e2b758bf6b20b57bd
8e5b7fa06033791f7e14716e18bdc1a5495e46034bfdcbb77fcbfaa570893d9c
7adec9a1a1309770501e8893e63aaa53b309cd0fdde38b1450e4c0c9984ea28d
1e0955e286f1ca33e3806e03bbf8e78eb893a8802a74c1deb411977817960e13
fb6fd33542319016dc01c0f9bca01f1c7d760916e60537185f385d888445ef27
da91dc1d4496cdf34766c82f74d1233c4c16a1701e9a802868c4610a2f3fcd8c
0e6b9345668e696a39e7962c6f1ba276c29182aa40c0dadc1f3b86dd396c9b0e
0453ab22008f3c01c6ec4889a4ff828e400938d31969db5e88fcfbf633817983
2048-bit secure Diffie-Hellman modulus #3
This is too small to protect a 128-bit generation at full strength.
942acc406c4f6c68f7d56f96b4efe8a314d624d11b0b7c9b5c0aca240406ba33
bc986676070bfe47007f65e92a0c825513d79ea1d81ce0fac5132846f847d4a9
bfc7f420cf293347d589b45269a062483acc84f7ab643d371d1546c84a3689c6
dab6313e1a461ca249dc24f49da1abc7089357fdd2f5f8cbdf323725fa64f8ee
e22de1dcb8ba25f2a410ae16d08ed5a4377a36175e20e56c14e29cfb3a4797f8
a123ff1ce04da33d3948cfd751929a373a9a3f1d2acf6620b917c0263ed3ea52
df585c64e6a3936937b2a2d900bf49cd6514d80a71cd6126f4519fb903d41d27
844f244446776282f313f36e679097d3f34d43c443141c9272ece204867f08c7
2560-bit secure Diffie-Hellman modulus #1
This is adequately-sized to support 128-bit genrations at full strength.
b8eb857df1eb89bc8c13ef777772d6f3d3716ecc671e5dfbb969c28ffc2c3383
283b54ca857ec4fff0cf45badd491e1203918b1d35ee197cafc039f65654e908
d0235537b280a605d902a3e273362cb21ba61423b926a57f41864195f785d8c2
8524345bfb89a05490ea1a56207db04a958590b1725ef2b538a05bb833ebbe0d
fb55f8195ae050ad216739970344c1423ac016cdc501dc6e51af56bfedb247e7
460530c6b5a73046b448818d85f19a5af50c19fa03143b108b71b18081b80e9a
8c5648cf8d2772f2e81c44f479fcf483db3b5e68d906833278de670cfdce7023
0c88beded782940e9724d1269412223f1bf70445288612b36fa67abf2f4dd391
1173c08793c42e51b2f469ac3455a894cb15dbc870c1252fca298a24cd5e507d
b637960f6eeb653d971075b73dfae5a60c51314313a6815438f1c6b4a6f3a2cf
3072-bit secure Diffie-Hellman modulus #1
Unknown strength greater than 128-bit, less than 192-bit.
c48f6e2843518c51000efb2aa67017951bca4b322b94c0ea1bb3f47444aa47a4
1b26ef9f4b0566c7c503ae38e53260127d1110c97c4d84746c49e74ddfcce99e
9dabe0588cdde430bacbce373da1adc4826fba83dc121798b4182d06398336ff
ed5149e893a22a17d341833693cc8c07b953a5f88abca6ce4ebbb33712406d37
0ae0dcbd55f3bd3b7fc1d15f2fa384cab5e10115aa342d00e04ff76d12c21059
35aa6867881384144d2affeaa9bec900e2ab7a24907c0129451531d5efca29d4
07bea207a4534ab45d5541fe5e248a9280b8e01e84d48570942c05137fc888ca
6b9b7e96be659352149ce05a0754cba3a22ce47da03deba945f2d5123a3fc02a
e46300ee8791ee6a6bba15d92f9ad0895811b277ac20becee88ea33a2e18ec3b
5ce8e913aa85c2912e214190eb6a1ceef052288c95fe94988b2e36c74b384d4e
26eb1e8fdb1c3898695c97ca1114207bd69fcf9ecbec36cae0092e20dcfbbbbd
6169970e2ec2309c178b0907d9bad5c0c9a41b9abfa997306404777836b22acf
3584-bit secure Diffie-Hellman modulus #1
Unknown strength greater than 128-bit, less than 192-bit.
a01cadf74b4d06569caad9b77c3451e75d1f9e898833c7ad6fe533a1be8f77b3
d20cf0507745151f8a8d5d79ac9dffca39e3a10768ca8b5d1a991450c03e5fd6
e1bb8cf302022695eb30d5f0d1822cb1cadea3297b2bb4244eb15c23a7add89f
27c4c9e6f8e0b53342d8767dc10632bdf0360c48e08f17758c2e1348b7363c5d
d7aaebfc2040aa1e6f697f7cd87f625475a144bcfefb7af752d77aa2f5b21664
d1e750160203baca07aba7c3c7541000808c42122a8173a4396fefbb5593f356
c3557fc1939ad39d6bbedb1fdc931ce6a3574fe4acb224291d36c6fae9e31fcf
883632bfc6e588dd7dca73c53312970b63702ee13381b74b03dae1d1e22e17a9
d865c2386615d89fdcff94e81629a85613754d9b10a9c79ffdfba2302ee80e35
f8162307f1d32dc837d7a9d0cc41fb0ade4d90e0e86d186b91d52f5c7d63ed55
5f6822fe4c7c0c0e0f6c35b03661e8d37b77e2bda25548aa4bd16b6780a268d9
e81975c989a737aa8ae9adb44dbfb0d4a607e355f4db36de3534c7d2c2c11c75
0f3febf92e6bf5be3e1033bca99d773f000feb762d87ab4c22c0642a694fc7d9
df026ca20497820ee4da94ffe2c93e3db34521f196bf524f3c3f0fe878f8ec2b
4096-bit secure Diffie-Hellman modulus #1
Whoah, Nellie!!! I consider myself lucky to have generated this one.
It only took a short time compared to 3072 #1.
ASCII-hexadecimal representations of this modulus and the session keys generated with it are 1024 bytes long.
That may be handy for you.
Unknown strength greater than 128-bit, less than 192-bit.
af0c858df6f08fdf9c65c46b862b8a49a89643bc8beb69d4fecad6dea6af8dc3
943812bc93789dba86113ad79abf48bf46098947e71e41a136533f60436f90b8
9d535dc354ebd9cb6cf57f5506d5b18bbcaa861998f4055b9ec3582fa6c2161f
75d05542ba4b2d5496b4113854c6d14fb8bb93370579bae0e1e6077fd6efe62e
d744f65a1912f730592e621ec7d4593c1ff41694acf61be27ba5d25edf5ebfe3
3334617a31b089aa8ac8b8f917f0d8185362574c7cdfaf64624149aec5c1a397
289614a9efdc529f4084b0978360ece10dd6eb9ad8be046fe7c935769a068af8
bf72569e6e5b454b58754f35892b918fa730fefa1ef4067d64f365db7253d49e
d9f09193c889b4a078e62bf56b9104f9acac2e2a3803dbbdf4d7696e1a26f8b4
7159af14f8550c70d0dc9b1c36353286a201e042474f2d466737bb35c3b6a754
413eaad190dd3d090817bc32f6e7ba413ff9f94bf65ba876545a4a1e0ce54430
84f704942224ee79f067d8518652b61d591aa1be7a35acd3d96b31443d3046b6
1c73d2a41305848acce64d830454f1a947604b57625990059b23a2c3f33ccacf
0a9185bf9e6bbf9ccc7ed05eccbee8eda9375a964fd1f0c4e0fb25e64af19089
fdb9a35abcb17e8c4bfdfd60294831942851cd227a0c0f405a84dbb437909190
181b3ef7791b4737020ff12a0def480b780840cede5f624cf8f3bef5fd44f573
8192-bit secure Diffie-Hellman modulus #1
Ew Dawggie!!!
This one took over 2 months of compute time on my 1.7 GHz P4.
Clearly I don't use an operating system from Washington, USA for this work.
Binary representations of this modulus and the session keys generated with it are 1024 bytes long.
That may be handy for you.
Unknown strength greater than 192-bit, less than 256-bit.
99134f625a7e28b61a2e610e1d55c5b1c01dc37f718c16116e482f500a046cca
650df4bea06121e842c16e3208548c51dbfe07a34fba510d61c5961d8920c41b
516e47ead343d0152f71ff692ccfd078b90323f0405ab12a0f5b1717236242b5
b4382b65bfeee7a8ed102a9fd8870b42a6b54a7667cfb0ac6a58de6b7ef1d7ca
db892d859ec9cd5feef5ca54127aa75aa84d20ea88d3085d3fab4ea71a82b4c0
ad0b9139d68d9521ca9ca4bef9f2221f96c7b3d93564e7735ea1514e318baa24
72e46a0f474fcfcafab662843d172ab0a5021e27fd8dd3c077f876350029679a
25de16eb0df0371d889f48d709ae68638dc2c82e797dccec72f8dec9842ba8a7
a9b9a047afc98769252b1c3db5805b7e7a91b4860eb785cd0eaa575f9313a876
2eca9929aed02f5fbd660a11c2a3bb70e2836a471928d283ab40fc470cf71331
eb51e6a09ad94b8f50f33af6c8af995fc943616467a6815e5d32cfb25a084ac6
386746dd5ab339283e643bf3ef7d488838769b2990776b728b1de7e605c8294f
cc7ecd9092a357d3286f7827bf921e4fb7239db2f5aa415ec53be0a5b26f7063
2191929b7dc9a8e17917b308884bb0745e8420fc6639a570ef45e3eae39a9444
cdcfc4509775d32f297a47025fd706fd6854a6a327981c4e4e56280ac590e63b
cd6dea98682a4c655de964ae0de75922b0f88a071950029de9f6ce673599ebb7
4bb122969b7c065a10ee2e6e60c41e8acae2ea6da0097810192d17198756dd22
bc1b533602e60dab38c0146b02394c7ba727da464bd7ab5bbd0b3c287522caf5
1f69db508fc5c603a7832bfbdba41f7467e3a565984368421e489cf04a44a0d4
fb5bd58237773506284131ea99c0c55545729d1b56473e2ee83e73c74fd19b5f
076115a85042370028e899c6cdaac1be1e9668518be1e48aecf40de573da2241
3e20a2d64d6ff935c5899f1c3c40eec8c33f9389aaff8ea6cab749199e09084f
94aa7dfe5257c09c601198ae84225cf1f995ce8610a1c21f79d767f177c75f6b
3a5575e3880b021e67f9c8bca52a6b8ce4ceec522fae129a08a23288f570403e
8acd8973b490fae5a6e669a5291afee18550b3d6e96100ee41b32b92e48056ad
626451d132c4676496776951eff8c672a480d297fb9d12aaa3faee456ea93953
b1ca94ceeaeb6e4091fd820df5d6bfc2fed4a2587a096f8b5267600a97c4b9eb
bfa91b5579dbe1cfaf7c6018bc4a1d679204c2e729c492eba06bd506f77b2403
d57730d1c73dcc861aabb2f3e90ffdb9a12bf3298eb34924c2be999bbcc6e4d7
dea62e98a1ea40943c998142a9947a13eef3e1531506a30b369b399bf22868cf
c79684e07e8dad0a936d8db81e876f3711dc1ea0c53fc19e234f00f826ccc2f8
8aa0e2ae60eebaff8a98977924c2054429454ca000c5c2aa22fccfc5e2fdd553
NOTES:
LOCATION: Neohapsis / Archives / Crypto / Message Index / Fwd: New Time and Space Based Key Size Equivalents for RSA and Diffie-Hellman
Subject: Fwd: New Time and Space Based Key Size Equivalents for RSA and Diffie-Hellman
From: Alex Alten (Alten@home.com)
Date: Thu Dec 14 2000 - 23:26:53 CST
Next message: 258bala3i@bigpond.com: "Free Mortgage Loan Analysis. No obligation! 8725"
Previous message: Damien Miller: "Re: analog encryption algorithms"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
I thought this might be of interest to the coderpunks community, it arrived
on several other security lists. The only thing that puzzles me is that
I would have thought a time-only RSA key could have been shorter than a
corresponding time-and-space RSA key (assuming that the time to crack is
equivalent to a key's strength).
- Alex
-----Original Message-----
From: FRousseau@chrysalis-its.com [mailto:FRousseau@chrysalis-its.com]
Sent: Wednesday, December 13, 2000 9:37 PM
To: IETF Transport Layer Security WG
Cc: ietf-pkix@imc.org
Subject: [ietf-tls] New Time and Space Based Key Size Equivalents for RSA
and Diffie- Hellman
I am sorry for the multiple postings, but I thought this particular
subject, although probably quite controversial, might be of interest to the
many peoples following these mailing lists, especially because of the
upcoming adoption of the AES algorithm by many IETF protocols.
As symmetric keys grow, they can be attacked by more processors without a
change in processor technology since the memory requirements for breaking
symmetric keys remain trivial. However, for the Number Field Sieve (NFS)
algorithm, which is currently the most efficient method to break RSA keys,
this is not true. Based on this premise, the "time and space" based RSA
key size equivalents previously published in the RSA Labs Bulletin #13 of
April 2000 by Robert Silverman (http://www.rsalabs.com/bulletins/) have
recently been extended to cover all the AES symmetric key sizes in the
latest draft of ANSI X9.44, which will eventually become the ANSI standard
for RSA key transport:
Time and Space
Symmetric Equivalent
Key Size RSA Key Size
(in bits) (in bits)
64 450
128 1620
192 2500
256 4200
These "time and space" based key sizes equivalents assume that both time
and memory are binding constraints in order to break RSA keys. This same
draft also indicates that beyond RSA key sizes of 768 bits one can no
longer effectively utilize 32-bit processors with the NFS algorithm because
the required memory exceeds what can be addressed in 32 bits; one is forced
to use 64-bit machines. Beyond RSA key sizes of about 2500 bits, the
memory requirements for the NFS algorithm exceed what can be addressed even
on 64 bit machines.
For your information, here are also the estimated "time" only based RSA key
size equivalents for solving the NFS problem from the same ANSI draft:
Time Only
Symmetric Equivalent
Key Size RSA Key Size
(in bits) (in bits)
64 512
128 2550
192 6700
256 13500
Note that either of these sets of RSA key size equivalents could be used
with Diffie-Hellman for solving the value of "p" since the NFS algorithm is
also the most efficient method to break Diffie-Hellman algorithm today.
Note also that these time only equivalents numbers are slightly smaller
than those from ANSI X9.42 for Diffie-Hellman (i.e. 2550 vs 3072 for 128
bits, 6700 vs 7680 for 192 bits and 13500 vs 15360 for 256 bits) and the
numbers in Hilarie Orman's Internet Draft (i.e.
draft-orman-public-key-lengths-01.txt).
Shouldn't IETF standards mention these new "time and space" based key size
equivalents in addition to existing "time" only based key size equivalents,
and possibly even suggest that "time and space" based key size equivalents
be used for RSA and Diffie-Hellman? Why mandate larger equivalent key
sizes when smaller equivalent key sizes can probably suffice?
Food for thought!
Cheers,
Francois
___________________________________
Francois Rousseau
Director of Standards and Conformance
Chrysalis-ITS
1688 Woodward Drive
Ottawa, Ontario, CANADA, K2C 3R7
frousseau@chrysalis-its.com Tel. (613) 723-5076 ext. 419
http://www.chrysalis-its.com Fax. (613) 723-5078
--
Alex Alten
Alten@Home.Com
--------------------------------------------------------------------
From: draft-ietf-ipsec-ciph-aes-cbc-01.html
+===========+=================+================+===============+
| Key Size | Exponent Size | Modulus Size | Group Type |
+===========+=================+================+===============+
| 128 | 256 | 3240 | MODP |
+-----------+-----------------+----------------+---------------+
| 128 | 248 | 248 | EC2N |
+-----------+-----------------+----------------+---------------+
| 192 | 384 | 7945 | MODP |
+-----------+-----------------+----------------+---------------+
| 192 | 376 | 376 | EC2N |
+-----------+-----------------+----------------+---------------+
| 256 | 512 | 15430 | MODP |
+-----------+-----------------+----------------+---------------+
| 256 | 504 | 504 | EC2N |
+-----------+-----------------+----------------+---------------+