Wei Dai: Lucas Sequences in Cryptography

1996 Aug 1 See all posts

Author

Wei Dai

Email

satoshinakamotonetwork@proton.me

Site

https://satoshinakamoto.network

This is a short note on the practical usefulness of Lucas sequences in applied cryptography. A Lucas sequence is a sequence of integers characterized by two parameters, P and Q. In practice Q is always 1 and the sequence is taken modulo a large integer. Calculating an element of a Lucas sequence is very similar to exponentiation. It may be helpful to think of P as the base and the index as the exponent. The following algorithm calculates V_e(p, 1) mod n, i.e., the e-th element of the Lucas sequence mod n characterized by P=p and Q=1. It uses m modular multiplies and m modular squarings, where m is the bit length of e. Therefore, it's about twice as slow as a modular exponentiation to the power e mod n.

Integer Lucas(const Integer &e, const Integer &p, const Integer &n)
{
        unsigned i = e.BitCount();

        if (i==0)
                return 2;

        Integer v=p, v1=(p*p-2)%n;
        i--;
        while (i--)
        {
                if (e[i])       // if i-th bit of e is 1
                {
                        v = (v*v1 - p) % n;
                        v1 = (v1*v1 - 2) % n;
                }
                else
                {
                        v1 = (v*v1 - p) % n;
                        v = (v*v - 2) % n;
                }
        }
        return v;
}

One application for Lucas sequences is primality testing. A theorem similar to Fermat's Little Theorem states that if n is prime and Jacobi(P^2-4, n)==-1, then V_n+1(P, 1) mod n == 2. The following algorithm uses this theorem as a probable primality test. A combination of this test and the strong probable prime test to the base 2 is extremely fast and reliable. In fact no composite number is known to pass both tests, and the total amount of time for the combined test is no more than 3 modular exponentiations.

boolean IsStrongLucasProbablePrime(const Integer &n)
{
        assert(n>1);
        if (n[0]==0)
                return n==2;
        Integer b=1, d;
        unsigned int i=0;
        int j;
        do
        {
                if (++i==64 && n.IsSquare())    // avoid infinite loop if n is a square
                        return FALSE;
                ++b; ++b;
                d = (b.Square()-4)%n;
        }
        while ((j=Jacobi(d,n)) == 1);
        if (j==0)
                return FALSE;
        Integer n1 = n-j;
        unsigned int a;
        // calculate a = largest power of 2 that divides n1
        for (a=0; ; a++)
                if (n1[a])
                        break;
        Integer m = n1>>a;
        Integer z = Lucas(m, b, n);
        if (z==2 || z==n-2)
                return TRUE;
        for (i=1; i<a; i++)
        {
                z = (z.Square()-2)%n;
                if (z==n-2)
                        return TRUE;
                if (z==2)
                        return FALSE;
        }
        return FALSE;
}

Lucas sequences can also be used for public key crypto and signature systems in a manner similar to RSA, but using Lucas sequences modulo a composite number instead of exponentiation. It has roughly the same security as RSA for the same size key, but is about twice as slow. Lucas sequence analogues of Diffie-Hellman and ElGamal can also be constructed. Compared to DH and ElGamal, for the same level of security they only require modulus half the size because their security is based on discrete log in GF(p^2) rather than GF(p). Because of the smaller modulus used and depending on your modular multiplication algorithm, they are also 50 to 100 percent faster. For more details, see the Crypto 95 paper "Some Remarks on Lucas-Based Cryptosystems" by Bleichenbacher, Bosman, and Lenstra.

In summary, Lucas sequences are very useful for fast and reliable primality testing. The Lucas sequence analogue of RSA is relatively less efficient, but the Lucas sequence analogues of Diffie-Hellman and ElGamal is relatively more efficient. However, Lucas sequence based cryptosystems have not received as much scrutiny as the more popular exponentiation based ones, so they should be used with caution.

Wei Dai

P.S. C++ implementations of the above mentioned algorithms and cryptosystems can be found in Crypto++.