Movatterモバイル変換

Diffie-Hellman in 2 lines of perl

#!/usr/local/bin/perl -- -export-a-crypto-system-sig Diffie-Hellman-2-lines($g,$e,$m)=@ARGV,$m||die"$0 gen exp mod\n";print`echo "16dio1[d2%Sa2/d0<X+d*La1=z\U$m%0]SX$e"[$g*]\EszlXx+p|dc`

Diffie-Hellman key exchange allows two parties who have not met toexchange keys securely on an unsecure communication path. TypicallyD-H is used to exchange a randomly generated conventional encryptionkey, the rest of the exchange is then encrypted with the conventionalcipher. It has been used with DES, 3DES, IDEA, RC4 though basicallythe approach of using D-H key exchange can be used for anyconventional stream or block cipher.

PGP itself operates in a similar fashion, except that PGP uses RSA forkey exchange, and IDEA as the conventional cipher.

The maths for Diffie-Hellman is quite simple.

Here is an example:

We are trying to exchange a random key for communication. Say that wewill be using the RC4 stream cipher as our conventional cipher.Here's the stages in the process.

You advertise your public generator g, and public prime modulus m asyour "public key" in the same way that you would advertise an RSApublic key, you give this to anyone you wish to exchange messageswith. This is no requirement for these numbers to be kept secret, allknowledge of these numbers gives is the ability to send you messages.
You do not tell anyone what your secret exponent x is.
You initiate a key exchange by calculating a:
```
     xa = g  mod m
```
and sending me the number a.
You can use the dh perl program to do this calculation. For thesake of argument we will choose some numbers. Say that your publicgenerator g = 3, your public prime modulus m = 10001 and your secretexponent x = 9a2e (all numbers in hex). Then you would run the perldh program like this to calculate a:
```
% dh g x m
```
You send me the following in email:
```
g = 3, m = 10001, a = c366
```
Now I choose a session key to use for RC4, using D-H key exchangeI can send this to you without an eavesdropper being able to get thekey.
I do not choose a session key directly but rather choose a randomnumber y from which I will calculate the session key.
Say that the random y = 4c20.
Now I calculate the session key s:
```
     ys = a  mod m
```
Or using the perl dh program:
```
% dh c366 4c20 10001
```
So the session key s = ded4
In order to send you the session s key I need only calculate:
```
     yb = g  mod m
```
Again using the perl dh program:
```
% dh 3 4c20 10001
```
So b = 6246
I send the number b to you in email, now you can recover the sessionkey:
```
     xs = b  mod m
```
So to obtain the session key, using the perl dh program you do:
```
% dh 6246 9a2e 10001
```
And sure enough out pops the session key as I calculated, s = ded4.
Now we both have the session key and commence exchanging messagesusing our agreed key as the key to a symmetric cipher such as rc4.
So now I can send you (or you can send me) rc4 messages encrypted withour negotiated session key s = ded4:
```
% cat msg | rc4 ded4 | uuencode r r | mail
```
A perl (and a C version) of rc4 suitable for the above can be foundhere.This works because of the mathematical property that:
```
  y           x x     yg   mod m = g   mod mand      xya = g  mod m,      b = g  mod m     y        x=>s = a  mod m = b  mod m
```
x and y never change hands, and yet s has changed hands. Further youcan't discover my y and I can't discover your x, and an eavesdropperhas neither x nor y and so cannot discover s.

Real example

You can try sending me some RC4 encrypted email, using a D-Hnegotiated session key.

For security (the above example is for clarity only 32 bit keys areutterly useless for security purposes) we will use 1024 bits. Here ismy Diffie-Helman public key, you can have a go at negotiating a D-H keyexchange and sending me some RC4 encrypted email.

I have chosen an x (which I won't be telling you this time for obviousreasons), and calculated the corresponding a as described above. Hereare my D-H public key numbers:

g = 3m = de9b707d4c5a4633c0290c95ff30a605aeb7ae864ff48370f13cf01d49adb9f23d19a439f753ee7703cf342d87f431105c843c78ca4df639931f3458fae8a94d1687e99a76ed99d0ba87189f42fd31ad8262c54a8cf5914ae6c28c540d714a5f6087a171fb74f4814c6f968d72386ef356a05180c3bec7ddd5ef6fe76b0531c3a =56C03667F3B50335AD532D0ADCAA2897A02C0878099D8E3AAB9D80B2B5C83E2F14C78CEE664BCE7D209E0FD8B73F7F6822FCDF6FFADE5AF2DDBB38FF3D2270CEBBED172D7C399F47EE9F1067F1B85CCBEC8F43B721B4F9802F3EA51A8ACD1F6FB526ECF4A56AD62B0AC17551727B6A7C7AADB9362394B410611A21A7711DCDE2

To send me some mail you will need to generate your choice of random yas described above, and then calculate the session key s:

% dh [a] [y] [m] > s

(where [a] and [m] are the large numbers above cut and pasted in, and[y] is your large random number.)and then calculate key exchange number b:

% dh [g] [y] [m] > b% mail adam@cypherspace.org< b

Then you compose your mail message as file "msg" and rc4 encrypt thatusing s as calculated above:

% cat msg | rc4 `cat s` | uuencode r r | mail adam@cypherspace.org

Comments, html bugs to me (Adam Back) at<adam@cypherspace.org>

[8]ページ先頭