Nash cryptosystem

Question

In 1955, Nash proposed a cryptosystem in a declassified handwritten letters sent to the National Security Agency. The letters also include a conjecture which is equivalent to the famous $P \ne NP$ conjecture. I am not an expert in cryptoghraphy and I want to know the encryption and decryption functions in modern language.

What is the formal description of Nash's cryptosystem according to modern cryptography? What is the implicit hardness assumption used to provide security?

Update: Shamir and Zinger published a paper that describes an efficient plaintext attack on Nash's cryptosystem (pointed out by @deviantfan).

Answer 1

Two things first:

• Even in 1955, Nash's encryption algorithm (I'll call it NEA) was rejected by the NSA because they deemed it not secure enough. So do not use it in real life.
• Like eg. AES, NEA is not based on any of the usual hard algorithms like factorization etc.

NEA is a symmetric stream cipher, ie. there's just one key for both encrypting and decrypting, and there's no minimum block size: One input bit becomes one output bit.

---

NEA needs one (possibly) public parameter, a key with several parts, and an IV (initilization vector) for each message.

The public parameter first:

• A natural number N, larger is better for security. 256 is a usual value.

A key consists of:

• Two random permutations P for N values. Ie. P[0][0] to P[0][N-1] are the numbers from 0 to N-1 but in some random order, and P[1][0] to P[1][N-1] too but in a completely different random order.
• Two random N-bit numbers, B[0][0] to B[0][N-1] and B[1][0] to B[1][N-1]

A IV is a random N-bit number just like B[0] or B[1] above.

---

Encrypting/Decrypting a message M with L bit to the ciphertext C, as pseudocode:

//N, P, B, and IV are given  
//S is a N-bit memory


Permut(X)
{
    R = S[P[X][N-1]]
    for all i from N-2 down to 0
    {
        S[P[X][i+1]] = S[P[X][i]] xor B[X][i];
    }
    S[P[X][0]] = X
    return R
}

Encrypt(M,L)
{
    S = IV  
    C[0] = M[0] xor Permut(0)  
    for all i from 1 to L
    {
        C[i] = M[i] xor Permut(C[i-1])
    }
    return C
}

Decrypt(C,L)
{
    return Encrypt(C,L)
}