9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Did you read the letters? $\endgroup$ – deviantfan Jan 13 '17 at 23:47
  • $\begingroup$ @deviantfan the letter predates modern cryptography and hence understanding it is very hard for me. $\endgroup$ – Mohammad Al-Turkistany Jan 13 '17 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 '17 at 0:15
  • 3
    $\begingroup$ @deviantfan Please go ahead and post an answer. As I said this is not my area of expertise. $\endgroup$ – Mohammad Al-Turkistany Jan 14 '17 at 0:20
10
$\begingroup$

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)
}
$\endgroup$
  • $\begingroup$ Nice. Can you comment on possible weaknesses against attacks? $\endgroup$ – Mohammad Al-Turkistany Jan 14 '17 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 '17 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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