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).

  • $\begingroup$ Did you read the letters? $\endgroup$
    – deviantfan
    Jan 13, 2017 at 23:47
  • $\begingroup$ @deviantfan the letter predates modern cryptography and hence understanding it is very hard for me. $\endgroup$ Jan 13, 2017 at 23:58
  • $\begingroup$ ... So binary numbers, addition, and the concept of permutation is hard? Well ... I find Nashs system much easier than any modern cipher. $\endgroup$
    – deviantfan
    Jan 14, 2017 at 0:15
  • 3
    $\begingroup$ @deviantfan Please go ahead and post an answer. As I said this is not my area of expertise. $\endgroup$ Jan 14, 2017 at 0:20

1 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

    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

    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

    return Encrypt(C,L)
  • $\begingroup$ Nice. Can you comment on possible weaknesses against attacks? $\endgroup$ Jan 14, 2017 at 11:43
  • 1
    $\begingroup$ @MohammadAl-Turkistany Eg. a chosen plaintext attack in O(N^2 log^3 N): eprint.iacr.org/2012/339.pdf $\endgroup$
    – deviantfan
    Jan 14, 2017 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.