$powmod » History » Revision 3
Revision 2 (Paul Janson, 10/03/2019 08:46 PM) → Revision 3/5 (Paul Janson, 10/03/2019 10:11 PM)
_Added in 3.6_
*$powmod(base, exponent, modulus)*
('base' raised to the 'exponent' power) modulo 'modulus'
'modulus' is another name for the 2nd parameter for the % operator. In this next example, the modulus is 1907.
//echo -a $powmod(2,111,1907) same as $calcint( (2^111) % 1907)
However, when 'exponent' becomes too large, it's very slow if not impossible to obtain the result using $calcint() directly. When N is approx 12 digits or longer, $calcint() returns 0 for 2^N. Somewhere just short of that, your client freezes for a long time while trying to calculate a number with more than a million digits.
All 3 parameters MUST be integers. If any parm has a fraction, result is as if that parameter were zero.
* 'base' should be an integer except 0 or 1, where the results are simplistic. If 'base' = 1, output is 1. If 'base' = 0, output is 0. If 'base' is negative N, then output is same as output for 'base' being $abs(N)
* 'exponent' 'exponsent' should be an integer 2 or greater. If 'exponent' = 1, result is the remainder from "base divided by modulus", which is always 'base' if it's less than 'modulus'. If exponent is 0 or negative, result is 1.
* 'modulus' should be non-zero to avoid divide by zero. If 'modulus' is 0, result is 0. If 'modulus' is negative, result is same as for modulus $abs(modulus)
In DH key exchange, powmod is the easy way to create the 'hard problem' that protects the shared secret when the prime is a sufficiently large "safe prime". In this example, Alice and Bob perform DH key exchange using safe prime 1907 to hide the shared secret from Eve the eavesdropper. All 'safe prime' divided by 24 have a remainder either 11 or 23. Private key MUST be chosen less than 'prime' and MUST be greater than 1. If 'safe prime' were divisible by 23, private key should be further limited to be no greater than q=(prime-1)/2. However, when 'safe prime' divided by 24 is 11, then the private key is an even number when $powmod(public_key,q,prime) is 1, otherwise the private key is odd. If 'exponent' is greater than 'modulus', it has an equivalent result to another 'exponents' which can be easily calculated. i.e. this is always the same: //var %prime 1907 , %n $rand(0,10) | echo -a $powmod(2,$calc( (%prime -1)* %n +321),%prime)
prime = 1907
a = Alice private key 456
A = Alice public key = $powmod(2,456,1907) = 1892
b = Bob private key 789
B = Bob public key = $powmod(2,789,1907) = 1193
Identical shared secret can be calculated 2 different ways:
$powmod(B,a,prime)
$powmod(A,b,prime)
//echo -a $powmod(1193,456,1907) same as $powmod(1862,789,1907) = same shared secret 719
Eve sees Alice and Bob sharing the 1892 and 1193 public keys, but must search to find $powmod(2, unknown exponent,1907) which results in 1892.
//var %i 2 | while (%i isnum 2-1906) { if ($powmod(2,%i,1907) = 1193) { echo -a bob private key is %i | halt } | inc %i } | echo -a private key somehow not found
Because 1907 % 24 is 11, Eve had a shortcut to test only half the private keys within the 2 thru prime-1 range, instead of all the keys in the 2 through (prime-1)/2 range if the result were 23:
//echo -a $powmod(1892,953,1907) is 1, so Eve knows that Alice's private key is even
//echo -a $powmod(1193,953,1907) is (prime-1), so Eve knows that Bob's private key is odd
This task is much harder in FiSH, where the 'safe prime' is 1080 bits in size. IN actual usage, the private key would be much larger than 20 digits:
//var %prime 12745216229761186769575009943944198619149164746831579719941140425076456621824834322853258804883232842877311723249782818608677050956745409379781245497526069657222703636504651898833151008222772087491045206203033063108075098874712912417029101508315117935752962862335062591404043092163187352352197487303798807791605274487594646923 , %private_key 12345678901234567890 | echo -a public key is $powmod(2,%private_key,%prime)
result: public key is 9096966601866802454683190856290401982846740225771867061600052568524959430855875148034766550337128449963518566421940946368033643297332206037516752463116368229254753990477791648737943826345055751194771858378452414281379237175301877700199154665816026591638021196652764283978525694745846158272612738555767737982450470691841483186
DH needs authentication, because Alice and Bob's communication can be intercepted by Mallory who can then send their own Fake-Alice-public-key to Bob and a Fake-Bob-public-key to Alice. When Bob and Alice generate their secret key, they are actually sharing a key with Mallory instead of with each other, and the secret Mallory shares with Alice is different than their secret shared with Bob, and is different than the secret that would've been shared if Alice and Bob had used each other's true public keys.
Mallory can then intercept Bob's messages to Alice using the Mallory/Bob secret, decrypt them, then re-encrypt them using the Mallory/Alice secret and send that altered message. Without authentication, Alice and Bob don't realize that Mallory has read all their messages, and possibly is editing them, until Mallory is no longer there to intercept and substitute messages.