I'll start right at Python code, without introducing mathematical equations.
First, pick a prime. I like 1009.
I'll use Wolfram Mathematica to find primitive root (I explained earlier) of 1009:
In[]:= PrimitiveRootList[1009]
Out[]= {11,17,22,26,31,33,34,38,46,51,52,53,55,65,66,76,78,79,83,85,86,88,89,91,92,94,95,97,99,102,106,107,114,115,118,124,130,133,138,146,153,154,156,158,159,161,163,165,166,172,176,178,181,188,190,193,194,195,198,208,214,215,220,228,233,234,235,237,238,239,244,248,249,257,258,262,263,264,265,267,272,273,277,279,281,282,285,291,293,297,298,301,304,305,307,308,310,311,318,319,321,325,326,329,340,342,358,364,366,367,368,372,377,385,389,390,395,399,401,408,413,415,416,419,422,424,430,434,439,445,446,458,462,466,468,470,474,475,477,483,489,493,495,498,511,514,516,520,526,532,534,535,539,541,543,547,551,563,564,570,575,579,585,587,590,593,594,596,601,608,610,614,619,620,624,632,637,641,642,643,645,651,667,669,680,683,684,688,690,691,698,699,701,702,704,705,708,711,712,716,718,724,727,728,730,732,736,737,742,744,745,746,747,751,752,760,761,765,770,771,772,774,775,776,781,789,794,795,801,811,814,815,816,819,821,828,831,833,837,843,844,846,848,850,851,853,855,856,863,871,876,879,885,891,894,895,902,903,907,910,912,914,915,917,918,920,921,923,924,926,930,931,933,943,944,954,956,957,958,963,971,975,976,978,983,987,992,998}
I like the smallest one -- 11.
So now $p=1009$ and $g=11$.
These two parameters is called 'Diffie Hellman Group'.
Run the following code (DH_prepare.py) twice:
#!/usr/bin/env python3
import random
p=1009
g=11
secret=random.randrange(1, p-1)
print ("secret=", secret)
public=pow(g, secret, p)
print ("public=", public)
The first result for Alice, the second for Bob:
% python3 DH_prepare.py secret= 315 public= 204 % python3 DH_prepare.py secret= 60 public= 668
Alice and Bob exchange 'public' keys and run another program (DH_receive.py):
#!/usr/bin/env python3
import sys
p=1009
g=11
my_secret=int(sys.argv[1])
received=int(sys.argv[2])
shared_secret=pow(received, my_secret, p)
print ("shared_secret=", shared_secret)
% python3 DH_receive.py 315 668 shared_secret= 540 % python3 DH_receive.py 60 204 shared_secret= 540
Now Alice and Bob have the shared secret: 540. Eve (eavesdropper) only knows two 'public' values and can't reconstruct shared secret.
Let's say this: you can reconstruct the 'shared secret' only using Alice's 'public' value and Bob's 'secret' value (or vice versa). But it's impossible to reconstruct it using two 'public' values. Both Alice and Bob have enough information for that.
In fact, you can view the function $g^{secret} \equiv public \mod p$ as a hash function. It's easy to compute, but hard to compute the inverse function (which is discrete logarithm).
By the way, these two functions are bijective with each other, if $secret \lt p$ and $g$ is a primitive root of $p$. So for each $public$ value, there is a single $secret$ corresponding to it. The problem is to find it.
Why it works anyway?
Because:
$public\_alice = g^{secret\_alice} \mod p$
$public\_bob = g^{secret\_bob} \mod p$
Bob will compute:
$public\_alice^{secret\_bob} \mod p$
... can be rewritten:
$(g^{secret\_alice} \mod p) ^{secret\_bob} \mod p$
... again:
$(g^{secret\_alice}) ^{secret\_bob} \mod p$... again:
$g^{secret\_alice \cdot secret\_bob} \mod p$
So, the shared_secret is basically: $g^{secret\_alice \cdot secret\_bob}$, but it's 'limited' or 'cut' by $p$. This expression can be computed by both Alice and Bob.
Without modular arithmetics, sharing just $g^{secret\_alice}$ would be senseless -- can be broken much easier.
Wolfram Mathematica can find inverse for small values: finding discrete logarithms for some modulo. Let's revese back Alice's 'public' value:
In[]:= MultiplicativeOrder[11,1009,204] Out[]= 315
Bob's 'public' value:
In[]:= MultiplicativeOrder[11, 1009, 668] Out[]= 60
Using SageMath:
sage: p=1009 sage: g=11 sage: x=668 sage: discrete_log(Mod(x,p), Mod(g,p), p-1) 60
Both can 'reverse' small values, but not the big one, used in cryptography.
With Mathematica 12 I can only able to find exponents for $p \approx 2^{32}$
People say that SageMath can do this better. Let's see.
My CPU is 6-core AMD Ryzen 5 3600, but SageMath's discrete_log() function uses only a single thread.
I've found that SageMath can reliably find discrete logarithms for $p \approx 2^{64}$ -- almost instantly.
But for larger $p$, like $p \approx 2^{80}$, sometimes it can do it, sometimes it can eat all your RAM and crash. In my case, 52GB RAM wasn't enough.
But sometimes, given enough luck, it can find a logarithm for $p \approx 2^{128}$.
Before experimenting, it's advised to set a RAM limit (Ubuntu Linux), 52GB in my case:
ulimit -Sv 52000000
(The 'ulimit' command is to be executed before SageMath.)
Otherwise your computer may freeze due to swapping/memory paging.
You can use arbitrary number for $g$. But this will reduce a number of all possible 'secret' values. See again my previous post. This imply that attacker would have smaller space for brute-force.
Even more -- $p$ may not be a prime number:
There is no obvious reason to restrict the size of the finite field to a prime number. So, from now on the size of the field can be any prime power q=p^e (see Theorem B. 16 or Theorem B.20). In [Lune87], Chapter XIII, efficient algorithms to find primitive elements in finite fields are described. See also Problem B.6 and Problem B. 10.
( Henk C.A. van Tilborg -- FUNDAMENTALS OF CRYPTOLOGY (2002) )
This is a real case. While I've been writing this blog post, I prepared various $p$ numbers for SageMath to gauge its discrete_log() function's performance. SageMath correctly 'reversed' and found the exponent, and once it showed different exponent, but still correct. But mine exponent was also correct. (I checked both.) How this can be? Didn't I state already that there is a bijective mapping between two functions. Ouch, I forgot to reset $g$, which was set to 2, aligning with OpenSSL parameters, I previously worked with. But my random prime numbers I generated with Wolfram Mathematica required different $g$ as primitive root to be working good in this scheme. In other words, my mistake could shorten keyspace for attacker, however, everything would work correctly.
Let's now use 2048-bit $p$. I'll take a recommended constant from RFC 7919, that is based on Euler constant.
Despite the fact, that these constants are all well-known, no problems at all. Even having $p$ and $g$, discrete logarithm problem is still hard.
DH_prepare_2.py:
#!/usr/bin/env python3
import random
p=0xFFFFFFFFFFFFFFFFADF85458A2BB4A9AAFDC5620273D3CF1D8B9C583CE2D3695A9E13641146433FBCC939DCE249B3EF97D2FE363630C75D8F681B202AEC4617AD3DF1ED5D5FD65612433F51F5F066ED0856365553DED1AF3B557135E7F57C935984F0C70E0E68B77E2A689DAF3EFE8721DF158A136ADE73530ACCA4F483A797ABC0AB182B324FB61D108A94BB2C8E3FBB96ADAB760D7F4681D4F42A3DE394DF4AE56EDE76372BB190B07A7C8EE0A6D709E02FCE1CDF7E2ECC03404CD28342F619172FE9CE98583FF8E4F1232EEF28183C3FE3B1B4C6FAD733BB5FCBC2EC22005C58EF1837D1683B2C6F34A26C1B2EFFA886B423861285C97FFFFFFFFFFFFFFFF
g=2
secret=random.randrange(1, p-1)
print ("secret=", secret)
public=pow(g, secret, p)
print ("public=", public)
DH_receive_2.py:
#!/usr/bin/env python3
import sys
p=0xFFFFFFFFFFFFFFFFADF85458A2BB4A9AAFDC5620273D3CF1D8B9C583CE2D3695A9E13641146433FBCC939DCE249B3EF97D2FE363630C75D8F681B202AEC4617AD3DF1ED5D5FD65612433F51F5F066ED0856365553DED1AF3B557135E7F57C935984F0C70E0E68B77E2A689DAF3EFE8721DF158A136ADE73530ACCA4F483A797ABC0AB182B324FB61D108A94BB2C8E3FBB96ADAB760D7F4681D4F42A3DE394DF4AE56EDE76372BB190B07A7C8EE0A6D709E02FCE1CDF7E2ECC03404CD28342F619172FE9CE98583FF8E4F1232EEF28183C3FE3B1B4C6FAD733BB5FCBC2EC22005C58EF1837D1683B2C6F34A26C1B2EFFA886B423861285C97FFFFFFFFFFFFFFFF
g=2
my_secret=int(sys.argv[1])
received=int(sys.argv[2])
shared_secret=pow(received, my_secret, p)
print ("shared_secret=", shared_secret)
Run DH_prepare_2.py twice:
% python3 DH_prepare_2.py secret= 13398249543775387671653288988935976350849077618344786160010229385740479997961409219497692489438705135146781463507619443743516182409077070833836981454105128863615667537528211364960356967997691337320923884414825012423575766085878368524086137326908007843544929192170545819108317884909616739404223364281785418937490344751620023254960336104186873790540873868716628844507413346952719789331150148111302925779469262243973801639011161561417866816488583496218626170668516999541932909643237774322165010010677431109650429451091232399942951477478568241517002396366950991356568250889209331817040399392142563909291941247954418747254 public= 22283721717219209737396435546886881160465582836860750128349243177226635935345066595208044363861638182685876962736088865327596794745596901065779695009118978857910650991653418211147709561328066523003893739980594470881575261350702829074527680188272616866544230081871238203277100826622551815636660109509230422538824027534902465223268071724010616338640146336528514370110721396332932408936718128515818680933735242858955024880835966623623476500287900214425042350874460534897460884477009989397518403747839271928301487058825079977226081607136891585142309184845019803638074909244498717200654407671986268642396118164749665911580 % python3 DH_prepare_2.py secret= 8057800931498322290778482564400977998338900779977414044809785856806619726705111501037775481819833531193405303151579280775893615733753611526130767827386642376909237633986806520109750467220161309029242483221735139892186548575311731412073672910444226075279785633868877710196100001107932120498947144010937702586322272385525152293450381725695204725624505979591436928771097798686811411415275891508487100678691637399873361444880233168261103713885687067807312453050563997436148913473397638779026662590874571879072831631874241524736941797897962583238880706695994237413163107244022310379171154708173552302094482911953439174971 public= 10880775340675814592719931421669682295699031931090466476023055033561172917209945042126408557036513534551774685870053664637863204812478321548563751258604900618312786706521392405867822701699319692179709956025624557145955897493362603432208690437636481567312986225698302464785482572143787239300612938720204195695995451801934716259669354462996360503895153023013781865123187025969009737877043972996661565763244153502442574791476139742672805421996951510639024588280464682909546356361753378191219652827946374691604837831710973477657137709375355106777710975869639094671426271544546331995729884803638515742013385971223419205077
Generate 'shared secret' for both parties:
% python3 DH_receive_2.py 13398249543775387671653288988935976350849077618344786160010229385740479997961409219497692489438705135146781463507619443743516182409077070833836981454105128863615667537528211364960356967997691337320923884414825012423575766085878368524086137326908007843544929192170545819108317884909616739404223364281785418937490344751620023254960336104186873790540873868716628844507413346952719789331150148111302925779469262243973801639011161561417866816488583496218626170668516999541932909643237774322165010010677431109650429451091232399942951477478568241517002396366950991356568250889209331817040399392142563909291941247954418747254 10880775340675814592719931421669682295699031931090466476023055033561172917209945042126408557036513534551774685870053664637863204812478321548563751258604900618312786706521392405867822701699319692179709956025624557145955897493362603432208690437636481567312986225698302464785482572143787239300612938720204195695995451801934716259669354462996360503895153023013781865123187025969009737877043972996661565763244153502442574791476139742672805421996951510639024588280464682909546356361753378191219652827946374691604837831710973477657137709375355106777710975869639094671426271544546331995729884803638515742013385971223419205077 shared_secret= 7601389475506658369589877614349435024528828523616570077451544241473768648277556709385895655963655366588664470214221763334249504211754873250341542121357567422194445291381892003315645976625399570009323513559210749050616927506475362182406664651606783083024179240975613038094153626248964051913753705832550150126073283123938303937011111938795437847434786053813333007893902867685446613361757645664621237521097149542489068567954517306675165564691480001270201344122370403435829793572198063007384266620320163135355399753238287905687132090846682978668580275059453281478835952093190515644109612342118714961229218400332129947075 % python3 DH_receive_2.py 8057800931498322290778482564400977998338900779977414044809785856806619726705111501037775481819833531193405303151579280775893615733753611526130767827386642376909237633986806520109750467220161309029242483221735139892186548575311731412073672910444226075279785633868877710196100001107932120498947144010937702586322272385525152293450381725695204725624505979591436928771097798686811411415275891508487100678691637399873361444880233168261103713885687067807312453050563997436148913473397638779026662590874571879072831631874241524736941797897962583238880706695994237413163107244022310379171154708173552302094482911953439174971 22283721717219209737396435546886881160465582836860750128349243177226635935345066595208044363861638182685876962736088865327596794745596901065779695009118978857910650991653418211147709561328066523003893739980594470881575261350702829074527680188272616866544230081871238203277100826622551815636660109509230422538824027534902465223268071724010616338640146336528514370110721396332932408936718128515818680933735242858955024880835966623623476500287900214425042350874460534897460884477009989397518403747839271928301487058825079977226081607136891585142309184845019803638074909244498717200654407671986268642396118164749665911580 shared_secret= 7601389475506658369589877614349435024528828523616570077451544241473768648277556709385895655963655366588664470214221763334249504211754873250341542121357567422194445291381892003315645976625399570009323513559210749050616927506475362182406664651606783083024179240975613038094153626248964051913753705832550150126073283123938303937011111938795437847434786053813333007893902867685446613361757645664621237521097149542489068567954517306675165564691480001270201344122370403435829793572198063007384266620320163135355399753238287905687132090846682978668580275059453281478835952093190515644109612342118714961229218400332129947075
Now that shared secret can be used as a key for symmetrical cryptography like AES, etc. This is 'serious-grade' cryptography.
As of 2022, it's unbreakable. Even given the fact that $g$ and $p$ are known. 'Secret' values cannot be recovered even if you have both 'public' values and $g$ and $p$.
The exponentiation operation modulo $p$ (pow() in Python and PowerMod[] in Wolfram Mathematica) is so fast you can create 'shared secrets' for each session, or even more frequently.
This implies that all past 'shared secrets' are not recoverable (if not saved somewhere), meaning, all the previous traffic wouldn't be possible to decrypt. See also: Forward secrecy
These additions to the "Supported Groups Registry" are described in
detail in Appendix A. They are all safe primes derived from the base
of the natural logarithm ("e"), with the high and low 64 bits set to
1 for efficient Montgomery or Barrett reduction.
The use of the base of the natural logarithm here is as a "nothing-
up-my-sleeve" number. The goal is to guarantee that the bits in the
middle of the modulus are effectively random, while avoiding any
suspicion that the primes have secretly been selected to be weak
according to some secret criteria. [RFC3526] used pi for this value.
See Section 8.5 for reasons that this document does not reuse pi.
( RFC 7919 )
Yes, indeed. $p$ based on $e$: RFC 7919; $p$ based on $\pi$: RFC 3526
Using such a 'famous' mathematical constants has some benefits. Do you remember how IBM sent DES S-Boxes to NSA and they returned in slightly modified form? But as with $e$ or $\pi$, no one can tamper these constants.
These constants are recommended by OpenSSL developers.
MD2 also used $\pi$: "This step uses a 256-byte "random" permutation constructed from the digits of pi."
As well as MD5: see RFC1321 3.4 and this answer.
'Logjam' attack authors found that the most popular $p$ constant for DH-512 in 2015 is: 9fdb8b8a004544f0045f1737d0ba2e0b274cdf1a9f588218fb435316a16e374171fd19d8d8f37c39bf863fd60e3e300680a3030c6e4c3757d08f70e6aa871033
(Hardcoded in Apache webserver.)
Second is: d4bcd52406f69b35994b88de5db89682c8157f62d8f33633ee5772f11f05ab22d6b5145b9f241e5acc31ff090a4bc71148976f76795094e71e7903529f5a824b
(Supplied with OpenSSL.)
( From their paper )
But you may want to find your own DH parameters.
I can manage this with OpenSSL:
% openssl dhparam -out dhparams.pem 4096
(But generation is slow, even on a fast computer. (Because finding a big safe prime is slow.) This is why you have to precompute these parameters, or use well-known ones. You can't generate them for each TLS session, for example.)
I ran this openssl command on 6-core AMD Ryzen 5 3600. It took ~300 seconds or ~5 minutes.
Of course, as a sysadmin, preparing DH parameters for whatever service you have on server, you can wait ~5 minutes. But this is unrealistic to prepare these for each TLS session.
% cat dhparams.pem
-----BEGIN DH PARAMETERS-----
MIICCAKCAgEA/UNNEpl9ltVSw2udvOSVH6Za/LcluZ3snQzOrLZYRdNOV48HrsvO
ukapgGGTO+/iQm3crJw6P0+AKZhSrq3D4skwDBWYPHcwmzCbMSC/Pd1rpMODrq1S
Lhnoc4kt3T091Af0EB1UriP0Tsx4+M3dD3uu/0+C2p8n7ZFck79pYxyqfRiqXylm
aSxz6gQOxp5n+VB52+IhdystDGKBD5gJ0oiWIIA0QfNLmhrYzwSe1TlSQC9J4FTE
fbU1rFDlj4gyA/LhFu0ckmJM6iuv3EpeOBAK9p8yqymq3M0zCuxQHR72G6CD+u/l
dIV42/DLXgBnSgAJ3cdlT1TkAvoZ2r3IBR5Wtr2JdsiPA+MosV+D9Z8+THxDDxm3
ZrUCiQWGgqZsW4GF+CcEJb2MUty9syZ3ChZS97KEexBsgDzsAVICrDdsWzs+QYxW
VCXEepZGmfnAVZt3JlOF81S5r+P90xEO0R/T3ueHYJApi7+E8aw/ji+ikrhsNWps
2TE2059HZbMLQLSXQC9Bzp1x65i/Sb0bI6hJ/CFnPIY0gypdxhGZdrO2GtOsYgp1
rEZIh/5hYYU3Ujz9/NHWq64Y6Bpbhcy5o4DN2cVfq71nj+ROzW/+d2U7AJg8xWng
ar3iMt+DgNkJ/zQfU3ZrmT57L/PvDyDY9D4BhZkvMYeqjpZeIFSvBssCAQI=
-----END DH PARAMETERS-----
% openssl asn1parse < dhparams.pem
0:d=0 hl=4 l= 520 cons: SEQUENCE
4:d=1 hl=4 l= 513 prim: INTEGER :FD434D12997D96D552C36B9DBCE4951FA65AFCB725B99DEC9D0CCEACB65845D34E578F07AECBCEBA46A98061933BEFE2426DDCAC9C3A3F4F80299852AEADC3E2C9300C15983C77309B309B3120BF3DDD6BA4C383AEAD522E19E873892DDD3D3DD407F4101D54AE23F44ECC78F8CDDD0F7BAEFF4F82DA9F27ED915C93BF69631CAA7D18AA5F2966692C73EA040EC69E67F95079DBE221772B2D0C62810F9809D2889620803441F34B9A1AD8CF049ED53952402F49E054C47DB535AC50E58F883203F2E116ED1C92624CEA2BAFDC4A5E38100AF69F32AB29AADCCD330AEC501D1EF61BA083FAEFE5748578DBF0CB5E00674A0009DDC7654F54E402FA19DABDC8051E56B6BD8976C88F03E328B15F83F59F3E4C7C430F19B766B50289058682A66C5B8185F8270425BD8C52DCBDB326770A1652F7B2847B106C803CEC015202AC376C5B3B3E418C565425C47A964699F9C0559B77265385F354B9AFE3FDD3110ED11FD3DEE7876090298BBF84F1AC3F8E2FA292B86C356A6CD93136D39F4765B30B40B497402F41CE9D71EB98BF49BD1B23A849FC21673C8634832A5DC6119976B3B61AD3AC620A75AC464887FE61618537523CFDFCD1D6ABAE18E81A5B85CCB9A380CDD9C55FABBD678FE44ECD6FFE77653B00983CC569E06ABDE232DF8380D909FF341F53766B993E7B2FF3EF0F20D8F43E0185992F3187AA8E965E2054AF06CB
521:d=1 hl=2 l= 1 prim: INTEGER :02
You can use these constants -- $p$ and $g$, right away. Right in the Python code I offered earlier.
By curiosity, I tried to generate DH parameters for key sizes 256..4096 bits, and found that $g$ is always 2. Why 2?
Such a generator is called a "primitive root" (which is trivial to find when p is "safe"). ... It is recommended to use 2 as generator, because it improves efficiency in multiplication performance. It is usable even when it is not a primitive root, as it still covers half of the space of possible residues. ... It is important to employ only safe primes as moduli, as they allow us to find a generator g so that the order of the generated subgroup does not factor into small primes, that is, with p = 2q + 1, the order has to be either q or p - 1. If the order is p - 1, then the exponents generate all possible public values, evenly distributed throughout the range of the modulus p, without cycling through a smaller subset. Van Oorshot and Wiener note that using short private exponents with a random prime modulus p makes the computation of the discrete logarithm easy [VAN-OORSCHOT]. However, they also state that this problem does not apply to safe primes.
( RFC 4419 )
Safe prime is a prime in form $p=2q+1$ where both $p$ and $q$ are primes. These are used in all DH implementatoins, but it's important to note that this is not a strict requirement. It's just makes several algorithms to work better/faster/simpler.
MITM is possible for DH in general. Of course, you can pretend you're Bob for Alice. And you're Alice for Bob, at the same moment.
There will be two shared secrets, but Mallory (in the middle) would know both. He can read and modify traffic. But this is a general problem for DH.
Another problem: DH_prepare*.py uses random.randrange(1, p-1). I don't know how Python's library do this.But in general, getting 2048 or 4096 bits of entropy is a task far from trivial. See RFC 4086. Care is to be taken when using (C)PRNG.
If your random() function use 32-bit seed, for example, it would be a piece of cake for an attacker to enumerate them all. That would imply that both 'secret' and 'public' values only have 32 bits of entropy, no matter how big these numbers are.
A classic bug: using a 32-bit seed for PRNG, and then calling rand() function many times in serie to get enough bits for your long 'secret' key. Of course, an attacker only needs to bruteforce that 32-bit seed value.
Let's now use heavy machinery.
Generate DH-256:
% openssl dhparam -out dhparams.pem 256
% cat dhparams.pem
-----BEGIN DH PARAMETERS-----
MCYCIQDoFpe1cB/4o5fP9I1ZZOQr32QGqhO7o6OiS+rrUZc0ewIBAg==
-----END DH PARAMETERS-----
% openssl asn1parse < dhparams.pem
0:d=0 hl=2 l= 38 cons: SEQUENCE
2:d=1 hl=2 l= 33 prim: INTEGER :E81697B5701FF8A397CFF48D5964E42BDF6406AA13BBA3A3A24BEAEB5197347B
37:d=1 hl=2 l= 1 prim: INTEGER :02
Using Wolfram Mathematica, I will also find the $ell$ parameter for CADO-NFS. See README.dlp. Remember safe primes? $ell$ is $q$. Finding it is trivial: just factor $p$ or divide $p-1$ by 2.
In[133]:= p=16^^E81697B5701FF8A397CFF48D5964E42BDF6406AA13BBA3A3A24BEAEB5197347B;
In[134]:= g=2;
In[135]:= (*Or use this: FactorInteger[p-1]*)
In[136]:= ell=(p-1)/2;
In[137]:= secret=Random[Integer,{1,ell}]
Out[137]= 7934140645160489087289656956441415697281962880349867745619770353314420891184
In[139]:= public=PowerMod[g,secret,p]
Out[139]= 88040204463577827248022472790210266970490684840632186604213471839237284800973
In[140]:= CommandLine="./cado-nfs.py -dlp -ell "<>ToString[ell]<>" target=" <>ToString[public]<>" "<>ToString[p]
Out[140]= ./cado-nfs.py -dlp -ell 52488249280999883780991186966113904727034251326410736142720734204350276803133 target=88040204463577827248022472790210266970490684840632186604213471839237284800973 104976498561999767561982373932227809454068502652821472285441468408700553606267
CADO-NFS installation instruction you can find here.
Running it on 6-core AMD Ryzen 5 3600 (~4 minutes):
Info:root: CADO_DEBUG is on, data kept in /tmp/cado.7i4pmpu8 Info:root: Checking that log(2) and log(3) are consistent... Info:root: p = 104976498561999767561982373932227809454068502652821472285441468408700553606267 Info:root: ell = 52488249280999883780991186966113904727034251326410736142720734204350276803133 Info:root: log2 = 20850424008160966946484149043838897061775211265562183011766205305702305660178 Info:root: log3 = 40578452624252825221154573150317370440373148459717096864909955822438343370101 Info:root: Also check log(target) vs log(2) ... Info:root: target = 88040204463577827248022472790210266970490684840632186604213471839237284800973 Info:root: log(target) = 28153509009254853143733272656017027349752145111918347033278047853598428730789 28153509009254853143733272656017027349752145111918347033278047853598428730789 Info:root: If you want to compute a new target, run ./cado-nfs.py /tmp/cado.7i4pmpu8/p80.parameters_snapshot.0 target=<target>
Ouch! CADO-NFS doesn't print the 'secret' value.
It solves diophantine equation: $x^y=target \mod p$ But without telling you $x$.
But it's easy to find $x$ if you can run CADO-NFS several times and know some theory behind logarithms.
Run it for target=2 ($g$ value):
% ./cado-nfs.py /tmp/cado.7i4pmpu8/p80.parameters_snapshot.0 target=2 ... Info:root: Checking that log(2) and log(3) are consistent... Info:root: p = 104976498561999767561982373932227809454068502652821472285441468408700553606267 Info:root: ell = 52488249280999883780991186966113904727034251326410736142720734204350276803133 Info:root: log2 = 20850424008160966946484149043838897061775211265562183011766205305702305660178 Info:root: log3 = 40578452624252825221154573150317370440373148459717096864909955822438343370101 Info:root: Also check log(target) vs log(2) ... Info:root: target = 2 Info:root: log(target) = 20850424008160966946484149043838897061775211265562183011766205305702305660178 20850424008160966946484149043838897061775211265562183011766205305702305660178
Now we see: this value was printed by CADO-NFS at first place: "log2 = ...", so no need to run CADO-NFS second time.
You may know that $log_b(x) = \frac{log(b)}{log(x)}$ -- the last two logarithms can be of arbitrary base. But things are different for diophantine equations in modular arithmetics. This rule becomes slightly different. (The first output of CADO-NFS I'll name 'logtarget', the second 'logg': $log(g)$)
$logg^{-1} \mod ell$ -- this is modular inverse, to be used if you want to replace division by multiplication.
$secret = logtarget \cdot (logg^{-1} \mod ell) \mod ell$
( Some of the theory is explained in my other collection of mathematical notes. )
Reconstruct the 'secret' using Wolfram Mathematica:
In[148]:= logtarget=28153509009254853143733272656017027349752145111918347033278047853598428730789; In[149]:= logg=20850424008160966946484149043838897061775211265562183011766205305702305660178; In[150]:= Mod[logtarget*PowerMod[logg,-1,ell],ell] Out[150]= 7934140645160489087289656956441415697281962880349867745619770353314420891184
Indeed, it is the same as been generated using Random[Integer,{1,ell}].
At this point, astute reader may ask, why using $ell$ instead of $p$? Because $p$ is a safe prime (as generated by OpenSSL) and effectively, it's all limited by modulo $ell$, not $p$.
But the difference is not significant, just one bit:
In[191]:= Log[2, p] // N Out[191]= 255.859 In[193]:= Log[2, ell] // N Out[193]= 254.859
% openssl dhparam -out dhparams.pem 320
% cat dhparams.pem
-----BEGIN DH PARAMETERS-----
MC4CKQCijY12yObAyUj0ngneSu0/Uh/gXyrdqLZbQvCDsGeBOXI/WAIElKQ7AgEC
-----END DH PARAMETERS-----
% openssl asn1parse < dhparams.pem
0:d=0 hl=2 l= 46 cons: SEQUENCE
2:d=1 hl=2 l= 41 prim: INTEGER :A28D8D76C8E6C0C948F49E09DE4AED3F521FE05F2ADDA8B65B42F083B0678139723F58020494A43B
45:d=1 hl=2 l= 1 prim: INTEGER :02
In[173]:= p=16^^A28D8D76C8E6C0C948F49E09DE4AED3F521FE05F2ADDA8B65B42F083B0678139723F58020494A43B;
In[174]:= g=2;
In[175]:= ell=(p-1)/2;
In[176]:= secret=Random[Integer,{1,ell}]
Out[176]= 99837042807986311247572608007098848566328141427417511605593944555864084325327113900468311574143
In[177]:= public=PowerMod[g,secret,p]
Out[177]= 819618795633092843285347415170336766767285128694229555031956983036482041505543873094481309660535
In[178]:= CommandLine="./cado-nfs.py -dlp -ell "<>ToString[ell]<>" target=" <>ToString[public]<>" "<>ToString[p]
Out[178]= ./cado-nfs.py -dlp -ell 678146429892639857943832012678609269511473848641350284807442986004063774729456205444611014545949 target=819618795633092843285347415170336766767285128694229555031956983036482041505543873094481309660535 1356292859785279715887664025357218539022947697282700569614885972008127549458912410889222029091899
28 minutes on the same CPU:
Info:root: CADO_DEBUG is on, data kept in /tmp/cado.49m3wqzt Info:root: Checking that log(2) and log(3) are consistent... Info:root: p = 1356292859785279715887664025357218539022947697282700569614885972008127549458912410889222029091899 Info:root: ell = 678146429892639857943832012678609269511473848641350284807442986004063774729456205444611014545949 Info:root: log2 = 656618540354879254188108390458420241701156229077512078870022747843189480967860864990167289830481 Info:root: log3 = 21090163601429749780531272128570957412543080143027196514836751563768934683700030454141298669455 Info:root: Also check log(target) vs log(2) ... Info:root: target = 819618795633092843285347415170336766767285128694229555031956983036482041505543873094481309660535 Info:root: log(target) = 670735019053674797324830824531427959320316228040470255274377749683368397840930117461255881594272 670735019053674797324830824531427959320316228040470255274377749683368397840930117461255881594272 Info:root: If you want to compute a new target, run ./cado-nfs.py /tmp/cado.49m3wqzt/p95.parameters_snapshot.0 target=<target>
BTW, did you notice the last line? "If you want to compute a new target, run ./cado-nfs.py /tmp/cado.49m3wqzt/p95.parameters_snapshot.0 target=<target>"
Plug these values:
In[201]:= logtarget=670735019053674797324830824531427959320316228040470255274377749683368397840930117461255881594272; In[202]:= logg=656618540354879254188108390458420241701156229077512078870022747843189480967860864990167289830481; In[203]:= Mod[logtarget*PowerMod[logg,-1,ell],ell] Out[203]= 99837042807986311247572608007098848566328141427417511605593944555864084325327113900468311574143
This is the correct value, same as 'secret' we used.
Interestingly, can we try another 'secret' value now?
In[204]:= secret2 = Random[Integer, {1, ell}]
Out[204]= 415811153047574077839411211302321097841230130891095315432045532418232041491290051605042781367275
In[205]:= public2 = PowerMod[g, secret2, p]
Out[205]= 664255839736621977190522961479727626903967447275991742426954600753838362487628485498432916466721
% ./cado-nfs.py /tmp/cado.49m3wqzt/p95.parameters_snapshot.0 target=664255839736621977190522961479727626903967447275991742426954600753838362487628485498432916466721
Only 20 seconds!
Info:root: Checking that log(2) and log(3) are consistent... Info:root: p = 1356292859785279715887664025357218539022947697282700569614885972008127549458912410889222029091899 Info:root: ell = 678146429892639857943832012678609269511473848641350284807442986004063774729456205444611014545949 Info:root: log2 = 656618540354879254188108390458420241701156229077512078870022747843189480967860864990167289830481 Info:root: log3 = 21090163601429749780531272128570957412543080143027196514836751563768934683700030454141298669455 Info:root: Also check log(target) vs log(2) ... Info:root: target = 664255839736621977190522961479727626903967447275991742426954600753838362487628485498432916466721 Info:root: log(target) = 356079054472052472482550319790341660230527146396110892146025747944050211494822867568164229566748 356079054472052472482550319790341660230527146396110892146025747944050211494822867568164229566748
Check:
In[206]:= logtarget2=356079054472052472482550319790341660230527146396110892146025747944050211494822867568164229566748; In[207]:= Mod[logtarget2*PowerMod[logg,-1,ell],ell] Out[207]= 415811153047574077839411211302321097841230130891095315432045532418232041491290051605042781367275
CADO-NFS works that fast now because it cached some data for your $ell$ and $p$ and now can reuse this information.
Wow, not a small piece of data:
% du -sh /tmp/cado.49m3wqzt 1.7G /tmp/cado.49m3wqzt
Of course, it would be bigger for bigger values.
I also tried 512-bit keys.
CADO-NFS predicts that it will process the data 2-4 months, on the same Ryzen CPU. I haven't run it. But of course, it's all doable, on off-the-shelf hardware, just be patient enough.
In February 2022, CADO-NFS has been updated to print discrete logarithm given $g=2$.
Info:root: CADO_DEBUG is on, data kept in /tmp/cado.kdiz2kdp Info:root: p = 104976498561999767561982373932227809454068502652821472285441468408700553606267 Info:root: ell = 52488249280999883780991186966113904727034251326410736142720734204350276803133 Info:root: Checking that log(2) and log(3) are consistent... Info:root: unscaled_log2 = 20850424008160966946484149043838897061775211265562183011766205305702305660178 mod ell Info:root: unscaled_log3 = 40578452624252825221154573150317370440373148459717096864909955822438343370101 mod ell Info:root: Checking that log(2) and log(3) are consistent... passed! Info:root: Also check log(target) vs log(2) ... Info:root: target = 88040204463577827248022472790210266970490684840632186604213471839237284800973 Info:root: unscaled_log(target) = 28153509009254853143733272656017027349752145111918347033278047853598428730789 mod ell Info:root: Also check log(target) vs log(2) ... passed! Info:root: Using g=2 as a generator Info:root: log2 = 1 mod ell Info:root: log3 = 21740896517265330765147904861772161197398290270049688221140686652820410005729 mod ell Info:root: target = 88040204463577827248022472790210266970490684840632186604213471839237284800973 Info:root: log(target) = 7934140645160489087289656956441415697281962880349867745619770353314420891184 mod ell 7934140645160489087289656956441415697281962880349867745619770353314420891184 Info:root: If you want to compute a new target, run ./cado-nfs.py /tmp/cado.kdiz2kdp/p80.parameters_snapshot.0 target=<target>
So now you don't need to recover it by additional steps. The final log(target) value is the exponent you want, for base=2.
But I left instructions for older CADO-NFS anyway. They can help a bit in understanding discrete logarithms and modular arithmetics.
Also, when you'll google for CADO-NFS blog/forum posts, you'll find 'old-style' printouts (generated before Feb-2022). So I think it's better to use both 'styles' here in this blog post.
This is the essence of 'Logjam' attack: 1, 2.
An attacker can use a huge power to cache all the data beforehand, for specific, well-known $p$ and then use it when they need to reverse back a 'shared secret', relatively fast. He can use the same CADO-NFS tool I've shown.
(Remember these two most used $p$ for DH-512 in 2015?)
It's speculated NSA may have enough power to break DH-512, maybe even DH-1024 and wiretap SSL/TLS traffic.
Protection for sysadmins: generate DH parameters with $p$ of at least 2048 bits. Recommendations from Logjam authors.
Alas, well-known $p$ values (such as based on $\pi$, $e$) are not to be used. Not because they are 'bad' or 'insecure', but because an attacker can get prepared for these beforehand.
This blog post also helped me.
And the CADO-NFS mailing list: 1, 2, 3.
How to crack RSA-512 on off-the-shelf hardware in 4 days using CADO-NFS.
UPD: as seen at reddit.
Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.