CSc 8370 fall '02


Perfect Secrecy




An Important Result from Information Theory.


A cipher system consisting of messages, ciphers, and keys has perfect secrecy if and only if the probability of any message given any cipher is constant. (in other words any key will decode a cipher to some message that has the same probability of being correct as every other message in the system).


With messages M, ciphers C

P(M | C) = P(M) or P( C | M ) = P(C)

This is met when M, C are uncorrelated random variables.


The only perfect systems have at least as many keys as messages.

Proof

let there be n possible messages (M(0), ... , M(n-1)), then any given key, K, must map each message into a unique cipher text (C(0), ..., C(n-1)) (if it doesn't it's not a useful system because messages get mixed up). Assume K < n, then the number of mappings is less than the number of messages (or ciphers) and some combination of M,C will occur with different probability than other combinations.


Therefore given a source of random numbers a cipher that uses those random numbers in the form


C = MIK where I is an additive operation like XOR or addition mod n will be perfect provided K is a random vector that is of the same size as C or M.


Imperfect Secrecy


The requirement for perfect secrecy is that the key stream be truly random. If it is not, and is produced by some algorithmic process, then that process can be broken.


  1. Vernam/Vigenere Ciphers

    One of the oldest approaches to using multiple keys is the Vigenere cipher. In this case a table of monosubstitution alphabets is chosen and each substitution is used sequentially. When all of them have been used the process starts from the beginning again. Weaker variants of this use a table of Caesar ciphers. Vernam ciphers do the same kind of substitution, but use a larger table and the XOR operation. These were among the first machine ciphers.

    a

    b

    c

    d

    e

    f

    g

    h

    i

    j

    k

    l

    m

    n

    o

    p

    q

    r

    s

    t

    u

    v

    w

    x

    y

    z

    1

    a

    d

    e

    c

    f

    o

    r

    u

    g

    b

    p

    n

    t

    i

    m

    k

    q

    h

    w

    v

    l

    z

    s

    y

    x

    j

    2

    b

    c

    a

    f

    o

    r

    u

    g

    m

    n

    z

    i

    k

    t

    e

    q

    d

    w

    l

    v

    h

    j

    s

    x

    y

    p

    3

    n

    f

    c

    u

    o

    a

    g

    l

    m

    b

    i

    k

    r

    e

    t

    d

    x

    j

    q

    v

    w

    z

    s

    h

    p

    y

    4

    f

    h

    o

    l

    c

    u

    g

    m

    a

    i

    x

    r

    k

    b

    d

    t

    j

    q

    v

    n

    e

    w

    s

    p

    z

    y

    5

    h

    f

    o

    l

    m

    u

    i

    c

    b

    n

    x

    g

    a

    d

    k

    j

    t

    r

    v

    e

    w

    q

    p

    z

    y

    s

    6

    x

    o

    h

    f

    m

    b

    i

    n

    a

    c

    l

    u

    d

    k

    j

    g

    r

    t

    v

    w

    e

    p

    z

    q

    y

    s

    7

    o

    v

    f

    m

    i

    b

    h

    x

    n

    d

    a

    c

    l

    j

    t

    k

    g

    z

    e

    u

    p

    w

    q

    y

    s

    r

    8

    m

    o

    v

    i

    x

    f

    d

    b

    d

    t

    n

    h

    y

    j

    c

    a

    u

    e

    p

    g

    w

    q

    k

    s

    r

    l

    9

    v

    m

    o

    x

    d

    z

    f

    b

    t

    j

    n

    y

    i

    j

    u

    h

    c

    w

    p

    q

    e

    a

    g

    r

    l

    s


    x

    v

    d

    m

    i

    o

    z

    t

    j

    b

    y

    n

    h

    u

    f

    l

    q

    p

    c

    k

    w

    r

    e

    a

    g

    s


    n

    d

    x

    v

    t

    m

    i

    o

    j

    b

    h

    y

    u

    z

    l

    q

    p

    f

    w

    a

    c

    r

    k

    s

    e

    g


    d

    n

    y

    x

    v

    t

    h

    j

    i

    o

    u

    b

    l

    q

    a

    p

    f

    r

    k

    m

    z

    s

    c

    e

    g

    w


    z

    y

    n

    x

    j

    w

    u

    t

    r

    q

    l

    b

    a

    o

    i

    f

    p

    k

    h

    m

    s

    e

    g

    v

    c

    d


    y

    c

    w

    a

    j

    u

    r

    n

    k

    l

    q

    z

    f

    b

    t

    o

    p

    h

    i

    s

    v

    g

    x

    m

    d

    e


    w

    u

    k

    r

    a

    h

    n

    l

    c

    j

    q

    f

    g

    b

    o

    p

    t

    v

    e

    s

    i

    x

    y

    d

    z

    m


    q

    k

    h

    r

    c

    u

    a

    w

    l

    x

    f

    z

    g

    p

    o

    b

    j

    t

    s

    n

    e

    v

    d

    y

    i

    m


    z

    q

    r

    k

    x

    l

    g

    u

    w

    f

    a

    p

    h

    o

    c

    b

    v

    s

    t

    j

    n

    d

    e

    y

    m

    i


    l

    k

    q

    r

    c

    g

    u

    x

    f

    w

    p

    h

    y

    a

    v

    o

    z

    b

    d

    t

    e

    s

    m

    j

    i

    n


    z

    l

    y

    q

    g

    u

    r

    f

    x

    p

    h

    w

    k

    v

    c

    e

    d

    b

    s

    o

    t

    a

    i

    n

    m

    j


    z

    y

    c

    g

    q

    u

    f

    p

    k

    h

    r

    w

    x

    l

    v

    d

    e

    s

    o

    b

    a

    i

    m

    t

    j

    n


    y

    z

    g

    u

    k

    q

    p

    h

    f

    c

    r

    l

    n

    d

    s

    e

    o

    m

    a

    b

    i

    t

    j

    v

    w

    x


    z

    g

    y

    u

    s

    c

    h

    p

    l

    q

    f

    n

    d

    r

    o

    m

    e

    i

    t

    x

    j

    b

    v

    k

    w

    a


    z

    u

    g

    s

    c

    p

    h

    t

    q

    l

    n

    d

    f

    o

    m

    r

    i

    x

    e

    j

    v

    b

    k

    y

    a

    w


    u

    t

    p

    c

    g

    s

    y

    q

    h

    n

    d

    o

    i

    f

    a

    l

    m

    j

    r

    v

    x

    e

    k

    b

    w

    z


    t

    p

    c

    u

    s

    g

    q

    n

    d

    i

    h

    o

    m

    a

    f

    y

    j

    v

    z

    r

    l

    e

    s

    b

    w

    k


    p

    c

    t

    s

    q

    n

    g

    d

    i

    a

    o

    m

    h

    u

    l

    j

    f

    v

    e

    y

    k

    z

    r

    w

    x

    b

  2. "autokey" and book ciphers

    A variation of this approach is to use another message as the key, either by shifting over (autokey) or taking a section of text (book). These both suffer from the problem that the key is not really random.

  3. Pseudo-random number generators.

Pseudo-random number generators are a common approximation to random numbers.

Unfortunately, it is somewhat tricky to generate a random number stream that cannot be inverted.

a) Multiplication mod n.

The ring where a, b, m are constants (a,b < m) and a is relatively prime to m, will generate a sequence of numbers, r, that "look" random. They aren't. (Knuth Vol 2 has a great discussion of this). Most generic random numbers on UNIX and Windows machines use some variation of this algorithm.


b) Shift register.

Random "looking" sequences of numbers that are relatively uncorrelated can be generated via a shift register algorithm. The companion matrices to the shift register can be written in the form:

and the iterate Akx will have a period of 2k-1 if the polynomial is irreducible.


c) RC4 (see the initial handout for details).

d) DES in OFB,CFB modes.

e) Blum, Blum and Shub

calculate the least significant bit of where n is a special integer. n is chosen to be the product of two large primes, each of which is congruent to 3 mod 4. X0 is defined by choosing a random number or "seed" between 0 and n-1 that is relatively prime with respect to n and using that as the start. The random "seed" is squared mod n to generate X0.

The security of this algorithm rests on the difficulty of factoring n (i.e. the two primes have to be kept secret) so that number theoretical algorithms like the Chinese remainder theorem cannot be used to predict the sequence of numbers.


Problems (Real problems due 9/12/02)

All stream ciphers are vulnerable to known plaintext attack. If you know part of the message, the equivalent part of the keystream can be recovered.


  1. Assuming that the random numbers came from a multiplicative generator mod n:

    a) how many symbols would need to be known if a,b,m are known?













b) how many symbols would need to be know if a,b,m were not known?














c) The sequence 443, 15598, 52575, 51469, 12759 is the output of one such generator. What are a,b,m ? These are all representable with C int data types.