AdiIRC

_Added in 3.6_

*$powmod(base, exponent, modulus)*

('base' raised to the 'exponent' power) modulo 'modulus'

'modulus' is the name for the operand following the % operator. In this next example, the modulus is 1907.

<pre>//echo -a $powmod(2,111,1907) same as $calcint( (2^111) % 1907)</pre>

The most common use for $powmod is in public key encryption, though there are also some pseudo-random number generators which use the math of powmod to create random-looking output and to disguise future randoms from someone who knows prior randoms.

However, when 'exponent' becomes too large, it's very slow if not impossible to obtain the result using the above $calcint() method 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 $calcint(2^123456789012) tries to calculate a number with more than a million digits.

All 3 parameters MUST be integers. If any parameter 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' 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)

The rest of this explanation describes how $powmod() is used for the portion of the Diffie-Hellman key exchange described at https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange as it relates to the DH1080 key exchange performed by the FiSH dll. DH is not a way to simplify the choosing of encryption keys, it's a way to share them in a way which hides the key from an observer who can see all communications between the two people.

In the 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. Private key MUST be chosen less than 'prime' and MUST be greater than 1. All 'safe prime' divided by 24 have a remainder either 11 or 23. 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,99) | 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)

<pre>//echo -a $powmod(1193,456,1907) same as $powmod(1862,789,1907) = same shared secret 719</pre>

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.

<pre>//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</pre>

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:

<pre>

//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</pre>

This task is much harder in the math used by FiSH_10.dll, where the 'safe prime' is 1080 bits in size. In actual usage, the private key would be much larger than 20 digits:

<pre>//var %prime 12745216229761186769575009943944198619149164746831579719941140425076456621824834322853258804883232842877311723249782818608677050956745409379781245497526069657222703636504651898833151008222772087491045206203033063108075098874712912417029101508315117935752962862335062591404043092163187352352197487303798807791605274487594646923 , %private_key 12345678901234567890 | echo -a public key is $powmod(2,%private_key,%prime)

</pre>

result: public key is 9096966601866802454683190856290401982846740225771867061600052568524959430855875148034766550337128449963518566421940946368033643297332206037516752463116368229254753990477791648737943826345055751194771858378452414281379237175301877700199154665816026591638021196652764283978525694745846158272612738555767737982450470691841483186

DH needs authentication, a way to guarantee that the public keys Alice and Bob receive from each other are actually the public keys sent by the other person. Alice and Bob's communication can be intercepted by Mallory who can then send their own Fake-Alice-public-key to Bob and send 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 Mallory's 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 the messages, then re-encrypt the messages using the Mallory/Alice secret and send the messages to Alice. 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.