XKEA

Anonymous (nobody@replay.com)
Wed, 8 Jul 1998 05:49:55 +0200

• Next message: Chris Wedgwood: "Re: Random Data from Geiger Counter"
• Previous message: Peter Gutmann: "MS SQL server security == PPTP?"
• Next in thread: Paul Lambert: "Re: Elliptical Curve Encryption"

I wrote:
> > Elliptic curve variants of normal public-key cryptosystems -- ECDH, ECDSS,
> > and now ECKEA/XECKEA (said like "ecky/zecky") -- work by replacing the
> > standard algorithm's modular exponentiation with that operation.

Lewis wrote:
> What does the 'X' mean in the hypothetical "ECKEA/XECKEA"?

XKEA=Extended Key Exchange Algorithm, XECKEA=elliptic curve XKEA. For all
intents and purposes, XKEA is KEA, just longer key lengths.

In order to allow them, it replaces steps G through I of the specification
(checking the shared secrets and converting them into an 80-bit key) with
the check of step G, a conditional swap, and a hash. Also, as to
private/public key lengths, it specifies only that its exponents and
moduli must be longer than KEA's.

A sample session, lifted from the anonymous Cypherpunks post containing
the description and slightly altered:

Steps 1-8 are those of normal KEA.

1 A->B: Y[a]
2 B->A: Y[b]
3 A->B: R[a]
4 B->A: R[b]
5 A : (Y[b])^q mod p = 1? If not, stop; (R[b])^q mod p = 1? If not, stop;
         Are Y[b] and R[b] between 1 and p? If not, stop.
6 B : (Y[a])^q mod p = 1? If not, stop; (R[a])^q mod p = 1? If not, stop;
         Are Y[a] and R[a] between 1 and p? If not, stop.
7 A : t[ab]=(Y[b])^r[a] mod p; u[ab]=(R[b])^x[a] mod p
8 B : t[ab]=(R[a])^x[b] mod p; u[ab]=(Y[a])^r[b] mod p
9 A : t[ab]>u[ab]? If so, swap t and u.
10 B : t[ab]>u[ab]? If so, swap t and u.
11 A : (t[ab]+u[ab]) mod p = 0? If so, stop; if not, Key=h(t[ab]||u[ab])
12 B : (t[ab]+u[ab]) mod p = 0? If so, stop; if not, Key=h(t[ab]||u[ab])

Notation:

The devices are named A and B. Brackets here are what subscripts were in
the KEA spec, representing a value's "owner." ^ is exponentiation (not
XOR), || is concatenation (not whatever else || means).

Constants:
p: longer-than-1024-bit prime modulus
q: longer-than-160-bit prime divisor of p-1
g: longer-than-1024-bit base

Secret user-dependent values:
x: longer-than-160-bit random key
r: longer-than-160-bit random key

Public user-dependent values:
Y: g^x mod p
R: g^r mod p

The oddball hash function:
h(x): Hash of x (SHA-1 for shared-key lengths <160 bits)

• Next message: Chris Wedgwood: "Re: Random Data from Geiger Counter"
• Previous message: Peter Gutmann: "MS SQL server security == PPTP?"
• Next in thread: Paul Lambert: "Re: Elliptical Curve Encryption"