Cryptography Terminology & NTRU Public Key Cryptosystem

Arunesh Ramalingam (M.S. CpE)

Encryption and Decryption:
Encryption is the process of converting unsecured information ("plaintext") into coded information ("ciphertext"). The transformation process is controlled by an algorithm and a key. The process must be reversible so that the intended recipient can decode the ciphertext to its original, plain text. But the decryption process should be impossible without the appropriate keyinformation.

Symmetric KeyCryptography:

In this a single key is used to perform both the encryption and decryption of data. Since the algorithms are open to the public, the security of the communication is determined by the level of protection provided to the key (i.e., ensuring that the key is known only to the parties involved in the communication).

Secrecy is provided, because if the message is intercepted, the intruder cannot transform the cipher text into its plaintext format, without knowledge of the key.

Assuming that only two users know the key, authentication is provided because only a user with thekey can generate cipher text that a recipient can decrypt the cipher text.

So the single key has to be exchanged between the two users. Thus key exchange is a very critical issue.

The main disadvantage of symmetrickey cryptography is the difficulty in distributing the secret keys. A key cannot be transmitted securely without encrypting over data channels. Encrypting the key, calls for another key. So, at some point, a plaintext key needs to be exchanged between the communicating partners. One solution is to manually distribute the secretkey (e.g., by registered mail). However, manual distribution, is costly, time consuming, and prone to errors.

The main idea of keeping the algorithms “open to public” is that many people can perform cryptanalysis and its security will be challenged by many. A good cryptographic algorithm is one which is not broken (or at least extremely hard/expensive to be broken) even though its working is well known and understood. A secret encryption algorithm, on the other hand, undergoes much lesser degree of cryptanalysis. So its security cannot be totally trusted and could be a mere illusion.

Many cryptosystems use a one-time key, that is, there is a key generation unit which produces a different key for the encryption of each block of plain text to its corresponding cipher text.

The entropy(H) of the key generator of the cryptosystem can give a measure of the data security. Each key can be considered to be a binary string . The probability of a key, which is a string w, being produced is given by Pw. This means that in a long series of keys generated by the key generator, the frequency with which a particular key ,w, will appear is Pw . Then , H = ∑ w [Pw * log (1/ Pw )] . The key can be guessed by an attacker with 2H guesses. This would give a measure of the level of message security .

Key Exchange:

When two users wish to communicate, they establish a logical (virtual circuit) connection. For the duration of the connection, all user data are encrypted with a one time session key. At the end of the session the keys are destroyed. These session keys must be known to both the users for proper encryption and subsequent decryption of messages to be successful. The exchange of these session keys is basically referred to as Key Exchange. An example is the Diffie/Hellman key exchangealgorithm.

Asymmetric Key Cryptography:

Asymmetric or public-key cryptography differs from conventional cryptography in that it involves two components:

  • A private key, which is private to the user ( only the user has access to it)
  • Apublic key, which may be published or distributed on request.

The relationship between the keys is such that given the public key, the private key cannot be derived easily.

The advantage of a public-key system is that two users can communicate securely without exchanging secret keys. It provides both secrecy and authentication.

The sender encrypts the message using the recipient's public key to. The Recipient uses his corresponding private key to decrypt the message. This ensures secrecy as the message can only be decrypted using the private key corresponding to the public key used for encryption.

The private key can also be used to encrypt messages, which can be decrypted by anyone with knowledge of the public key. The purpose of this is to provide authentication (digital signature), that is, verification of the origin of the message, since the message can be decrypted only with the corresponding public key. For example, the R.S.A algorithm is a publickey cryptographic algorithm.Disadvantage of a public-keysystem:

(1)The mathematical computations used to encrypt data are time consuming, and depending on the algorithm, the ciphertext may be much larger than the plaintext. Thus, it is not suitable to encrypt large messages.

(2)An encrypted message can only be sent to a single recipient. Since a recipient's public key must be used to encrypt the message, sending to a list of recipient's is not possible.

Message Authentication:

The authentication of messages using symmetric key works on the assumption that the sender and the receiver share a secret key. If an attacker stumbles upon a few correct decryptions, then he can spoil the authentication. In this case a sequence number or an error detection code might help to ensure authenticity. A timestamp included in the message could indicate if there has been some abnormal delay other than the expected delay through the network.

Other methods which could be used to ensure authenticity are:

(1) Message Authentication Code (MAC) – This method assumes that the two parties share a common secret key. The MAC of a message is calculated by using the secret key and the message in a MAC function which takes a variable sized input and produces a fixed size output, and is transmitted along with the message. After reception, the receiver recalculates the MAC and sees if it matches with the MAC received. If both the MACs match then the message is considered authentic. This method is good as long as the secret key remains a secret because the attacker can alter the message but cannot alter the MAC as he does not know the secret key.

(2) One-Way Hash Function – These are special functions used as checksum for a block of text. They accept a variable sized input and produce a fixed size output called the message digest. They have an important characteristic that is, given a text its Hash function can be determined but the reverse is not possible. Calculation of the inverse of the hash function is very difficult mathematically. Hence, they are said to be one-way. They are useful especially for digital signatures. The sender can encrypt the message digest with his private key. The receiver recalculates the message digest of the message, and also decrypts the received message digest with the public key of the sender. If both the message digests match then the message is authentic. Therefore, if someone signs a document by using public-key methods to sign its hash value, an attacker cannot generate a false document and claim that it was this document, having the same hash, which was signed instead. The Secure Hash Algorithm is used to produce one way hash functions.

The NTRU Public Key Cryptosystem (NTRU PKCS):

This Cryptosystem is based on ring theory. Its security depends on the fact that for most lattices it is very difficult to find extremely short vectors (as compared to moderately short). The basic collection of objects used by the NTRU PKCS is ring R consisting of truncated polynomials of degree (N-1) having integer coefficients.

a = a0 + a1x + a2x2 + a3x3+…+aN-2xN-2 +aN-1xN-1

The polynomials are added and multiplied in usual way except that xN is replaced by 1, xN+1 is replaced by x , xN+2 is replaced by x2 and so on. The multiplications involved are cyclic convolution product.

NTRU PKCS depends on 3 integer parameters and 4 sets of data.

N – The polynomials in the truncated polynomial ring have a degree of (N-1).

q – Large modulus; coefficients of truncated polynomials are reduced (mod q).

p - Small modulus; coefficients of message are reduced (mod p) in the final step of Decryption.

p and q are relatively prime, that is, gcd (p,q) =1.

Rf, Rg, Rr, Rm are sets of polynomials of degree (N-1) with integer coefficients.

Implementation of the NTRU PKCS:

1.Private Key: Choose “Small” Polynomials f, g є Rg. For a “small” polynomial the coefficients are much smaller than q). f must have inverses modulo q and modulo p, that is, there should be fp and fq such that,

f * fp = 1(mod p) and f * fq = 1(mod q). The private keys to be kept track of are f and fp.

2. Public Key: It is calculated ash = p * fq * g (mod q).

3. Encryption: Message is put in the form of polynomial m. The coefficients are chosen between –q/2 and q/2, that is, m is a “small” polynomial mod q. [m є Rm]. A small polynomial r is randomly chosen r є Rr. This is the “blinding value” used to obscure the message.

e = r * h + m (mod q)

4. Decryption: Compute polynomial a = f * e (mod q).Choose coefficient of a between –q/2 and q/2. Compute b = a (mod p), that is, each of the coefficient is reduced modulo p.

d = fp * b (mod p)

Workingof the NTRU PKCS:

a = f * e (mod q) = f *(r * h +m) (mod q) = [f * (r * (p* fq * g) + m)] (mod q) = [(r * p * g) + (f * m)] (mod q).

The coefficients of r, g, f, m and (r *g), (f * m)are small compared to q. Assuming properly chosen parameters, since p is also small compared to q, coefficients of polynomials prg+fm lies between –q/2 and q/2 . Hence, reduction by mod q has no effect. Therefore,a =[(r * p * g) + (f * m)].When b is calculated as:

b =[(r * p * g) + (f * m)] (mod p), we get b = f * m (mod p). In the last step of decryption, when we multiply b by inverse of f modulo p (fp), we get d = fp * f * m (mod p). Thus the message m is recovered, since fp* f=1.

Parameter choices to optimize performance:

1. The private key f is chosen as f = 1 + pF, where F is a small polynomial. This means fp=1. So it is not required to compute fp. Moreover, the second multiplication in decryption also is removed. Only fneeds to be stored as the private key.

2. The success of decryption depends on the coefficients of a being unchanged when they are reduced modulo q. The coefficients of a depends on f, g, m, andr. So if size of p is reduced, all the coefficients can be comfortably small. Since p and q have to be relatively prime p ≠ 2, but p can be a non integer. So p is chosen as p = 2 + x. Normally, the value chosen for p is 3. So trinary coefficients (+1, 0, -1) are used for the polynomials. Now binary polynomials can be used.

Some Facts of NTRU PKCS:

The NTRU Public-Key Cryptosystem features super fast key generation:

  • NTRU key generation 30-1000+ times faster than RSA, ECC
  • All NTRU keys are fully Independent.
  • NTRU sign/verify up to 100 times faster than RSA or ECC
  • Key generation is 1-3 orders of magnitude faster than RSA, ECC
  • NTRU encrypt/decrypt runs up to 475 times faster than RSA/ECC on servers.
  • Encrypts 40-50 times faster than hand-optimized (for speed) RSA, ECC.
  • Decrypts 333 times faster than hand-optimized (for speed) RSA.
  • Up to 2000 times faster than RSA on DSPs.

Reasons for the High Speed of NTRU PKCS:

System / Basic Operation / Number of Operations Required
Encrypt / Decrypt
NTRU / Convolution Product / 1 / 2
RSA / Modular Multiplication / 17 / ~1000
ECC / Elliptic Curve Addition / ~160 / ~160
NTRU and ECC basic operations take approximately the same time(basic operations for RSA are a little faster).

Advantages of the NTRU PKCS:

  • NTRU’s fast key creation enables new public key paradigms :

Message Integrity: Encrypt audio and video with a different key for every few seconds ofcontent.

Use independent keys for every transaction

E-mail: Master Key/Disposable Key Protocol saves storage and increasessecurity.

  • NTRU is:

– Easy to program

– Easy to build into hardware

– Ideal for Digital Signal Processors (DSPs)

  • NTRU Requires:

– Less memory (RAM) in software

– Less storage in software

– Fewer gates in hardware

  • NTRU easily fits into Low power smart cards, handheld devices, Cellular telephones.

References:

1. Cryptography FAQ:

2.

3.CRYPTOSYSTEMS AND KEYS, CERBERUS SYSTEMS, INC.

4. Security: Symmetric and Public Key Cryptography

Eduardo Magana - 11/1/2002

5.

6. NTRU PKCS

Page 1 of 4