Question

Please no Plagiarism

Kleptography:

Different type of algorithms, implementations, and write classic algorithms.

Answer 1

Solution)

Kleptography is the study of stealing information securely and subliminally and it was introduced by Adam Young and Moti Yung in the Proceedings of Advances in Cryptology—Crypto '96. Kleptography is a subfield of cryptovirology and is a natural extension of the theory of subliminal channels that was pioneered by Gus Simmons while at Sandia National Laboratory. A kleptographic backdoor is synonymously referred to as an asymmetric backdoor. Kleptography encompasses secure and covert communications through cryptosystems and cryptographic protocols. This is reminiscent of, but not the same as steganography that studies covert communications through graphics, video, digital audio data, and so forth. A kleptographic attack is an attack which uses asymmetric cryptography to implement a cryptographic backdoor. For example, one such attack could be to subtly modify how the public and private key pairs are generated by the cryptosystem so that the private key could be derived from the public key using the attacker's private key. In a well-designed attack, the outputs of the infected cryptosystem would be computationally indistinguishable from the outputs of the corresponding uninfected cryptosystem. If the infected cryptosystem is a black-box implementation such as a hardware security module, a smartcard, or a Trusted Platform Module, a successful attack could go completely unnoticed. A reverse engineer might be able to uncover a backdoor inserted by an attacker, and when it is a symmetric backdoor, even use it herself. However, by definition a kleptographic backdoor is asymmetric and the reverse-engineer cannot use it. A kleptographic attack (asymmetric backdoor) requires a private key known only to the attacker in order to use the backdoor. In this case, even if the reverse engineer was well-funded and gained complete knowledge of the backdoor, it would remain useless for her to extract the plaintext without the attacker's private key. Kleptographic attacks can be constructed as a cryptotrojan that infects a cryptosystem and opens a backdoor for the attacker, or can be implemented by the manufacturer of a cryptosystem. The attack does not necessarily have to reveal the entirety of the cryptosystem's output; a more complicated attack technique may alternate between producing uninfected output and insecure data with the backdoor present. Kleptographic attacks have been designed for RSA key generation, the Diffie–Hellman key exchange, the Digital Signature Algorithm, and other cryptographic algorithms and protocols. SSL, SSH, and IPsec protocols are vulnerable to kleptographic attacks. In each case, the attacker is able to compromise the particular cryptographic algorithm or protocol by inspecting the information that the backdoor information is encoded in (e.g., the public key, the digital signature, the key exchange messages, etc.) and then exploiting the logic of the asymmetric backdoor using their secret key (usually a private key). A. Juels and J. Guajardo proposed a method (KEGVER) through which a third party can verify RSA key generation. This is devised as a form of distributed key generation in which the secret key is only known to the black box itself. This assures that the key generation process was not modified and that the private key cannot be reproduced through a kleptographic attack.

Kleptographic attacks have been designed for RSA key generation, the Diffie–Hellman key exchange, the Digital Signature Algorithm, and other cryptographic algorithms and protocols.SSL, SSH, and IPsec protocols are vulnerable to kleptographic attacks.In each case, the attacker is able to compromise the particular cryptographic algorithm or protocol by inspecting the information that the backdoor information is encoded in (e.g., the public key, the digital signature, the key exchange messages, etc.) and then exploiting the logic of the asymmetric backdoor using their secret key (usually a private key).

A. Juels and J. Guajardo proposed a method (KEGVER) through which a third party can verify RSA key generation. This is devised as a form of distributed key generation in which the secret key is only known to the black box itself. This assures that the key generation process was not modified and that the private key cannot be reproduced through a kleptographic attack.

Implementation of Diffie-Hellman Algorithm:

Elliptic Curve Cryptography (ECC) is an approach to public-key cryptography, based on the algebraic structure of elliptic curves over finite fields. ECC requires a smaller key as compared to non-ECC cryptography to provide equivalent security (a 256-bit ECC security have an equivalent security attained by 3072-bit RSA cryptography).

For a better understanding of Elliptic Curve Cryptography, it is very important to understand the basics of Elliptic Curve. An elliptic curve is a planar algebraic curve defined by an equation of the form

where ‘a’ is the co-efficient of x and ‘b’ is the constant of the equation

The curve is non-singular; that is its graph has no cusps or self-intersections (when the characteristic of the
co-efficient field is equal to 2 or 3).
In general, an elliptic curve looks like as shown below. Elliptic curves could intersect atmost 3 points when a straight line is drawn intersecting the curve. As we can see that elliptic curve is symmetric about the x-axis, this property plays a key role in the algorithm.

Diffie-Hellman algorithm

The Diffie-Hellman algorithm is being used to establish a shared secret that can be used for secret
communications while exchanging data over a public network using the elliptic curve to generate points and get the secret key using the parameters.

• For the sake of simplicity and practical implementation of the algorithm, we will consider only 4 variables one prime P and G (a primitive root of P) and two private values a and b.
• P and G are both publicly available numbers. Users (say Alice and Bob) pick private values a and b and they generate a key and exchange it publicly, the opposite person received the key and from that generates a secret key after which they have the same secret key to encrypt.

Step by Step Explanation

ALICE	BOB
Public Keys available = P, G	Public Keys available = P, G
Private Key Selected = a	Private Key Selected = b
Key generated =	Key generated =
Exchange of generated keys takes place
Key received = y	key received = x
Generated Secret Key =	Generated Secret Key =
Algebraically it can be shown that
Users now have a symmetric secret key to encrypt

Example

Step 1: Alice and Bob get public numbers P = 23, G = 9

Step 2: Alice selected a private key a = 4 and
        Bob selected a private key b = 3

Step 3: Alice and Bob compute public values
Alice:    x =(9^4 mod 23) = (6561 mod 23) = 6
        Bob:    y = (9^3 mod 23) = (729 mod 23)  = 16

Step 4: Alice and Bob exchange public numbers

Step 5: Alice receives public key y =16 and
        Bob receives public key x = 6

Step 6: Alice and Bob compute symmetric keys
        Alice:  ka = y^a mod p = 65536 mod 23 = 9
        Bob:    kb = x^b mod p = 216 mod 23 = 9

Step 7: 9 is the shared secret.

Implementation:

/* This program calculates the Key for two persons using the Diffie-Hellman Key exchange algorithm */ #include<stdio.h> #include<math.h>    // Power function to return value of a ^ b mod P long long int power(long long int a, long long int b,                                      long long int P) {     if (b == 1)         return a;        else         return (((long long int)pow(a, b)) % P); }    //Driver program int main() {     long long int P, G, x, a, y, b, ka, kb;            // Both the persons will be agreed upon the         // public keys G and P     P = 23; // A prime number P is taken     printf("The value of P : %lld\n", P);        G = 9; // A primitve root for P, G is taken     printf("The value of G : %lld\n\n", G);        // Alice will choose the private key a     a = 4; // a is the chosen private key     printf("The private key a for Alice : %lld\n", a);     x = power(G, a, P); // gets the generated key            // Bob will choose the private key b     b = 3; // b is the chosen private key     printf("The private key b for Bob : %lld\n\n", b);     y = power(G, b, P); // gets the generated key        // Generating the secret key after the exchange         // of keys     ka = power(y, a, P); // Secret key for Alice     kb = power(x, b, P); // Secret key for Bob            printf("Secret key for the Alice is : %lld\n", ka);     printf("Secret Key for the Bob is : %lld\n", kb);            return 0; }

Output

The value of P : 23
The value of G : 9

The private key a for Alice : 4
The private key b for Bob : 3

Secret key for the Alice is : 9
Secret Key for the Bob is : 9

RSA Algorithm in Cryptography::

from decimal import Decimal    def gcd(a,b):     if b==0:         return a     else:         return gcd(b,a%b) p = int(input('Enter the value of p = ')) q = int(input('Enter the value of q = ')) no = int(input('Enter the value of text = ')) n = p*q t = (p-1)*(q-1)    for e in range(2,t):     if gcd(e,t)== 1:         break       for i in range(1,10):     x = 1 + i*t     if x % e == 0:         d = int(x/e)         break ctt = Decimal(0) ctt =pow(no,e) ct = ctt % n    dtt = Decimal(0) dtt = pow(ct,d) dt = dtt % n    print('n = '+str(n)+' e = '+str(e)+' t = '+str(t)+' d = '+str(d)+' cipher text = '+str(ct)+' decrypted text = '+str(dt))

RSA algorithm is asymmetric cryptography algorithm. Asymmetric actually means that it works on two different keys i.e. Public Key and Private Key. As the name describes that the Public Key is given to everyone and Private key is kept private.

An example of asymmetric cryptography :

1. A client (for example browser) sends its public key to the server and requests for some data.
2. The server encrypts the data using client’s public key and sends the encrypted data.
3. Client receives this data and decrypts it.

Since this is asymmetric, nobody else except browser can decrypt the data even if a third party has public key of browser.

The idea! The idea of RSA is based on the fact that it is difficult to factorize a large integer. The public key consists of two numbers where one number is multiplication of two large prime numbers. And private key is also derived from the same two prime numbers. So if somebody can factorize the large number, the private key is compromised. Therefore encryption strength totally lies on the key size and if we double or triple the key size, the strength of encryption increases exponentially. RSA keys can be typically 1024 or 2048 bits long, but experts believe that 1024 bit keys could be broken in the near future. But till now it seems to be an infeasible task.

Let us learn the mechanism behind RSA algorithm :

• >> Generating Public Key :
  • Select two prime no's. Suppose P = 53 and Q = 59. Now First part of the Public key : n = P*Q = 3127.
  • We also need a small exponent say e : But e Must be
    • An integer.
    • Not be a factor of n.
    • 1 < e < Φ(n) [Φ(n) is discussed below], Let us now consider it to be equal to 3.
  • Our Public Key is made of n and e

  >> Generating Private Key :

  • We need to calculate Φ(n) : Such that Φ(n) = (P-1)(Q-1) so, Φ(n) = 3016
  • Now calculate Private Key, d : d = (k*Φ(n) + 1) / e for some integer k For k = 2, value of d is 2011.

  Now we are ready with our – Public Key ( n = 3127 and e = 3) and Private Key(d = 2011)

  Now we will encrypt “HI” :

  • Convert letters to numbers : H = 8 and I = 9
  • Thus Encrypted Data c = 89^e mod n. Thus our Encrypted Data comes out to be 1394
  • Now we will decrypt 1394 :
  • Decrypted Data = c^d mod n. Thus our Encrypted Data comes out to be 89
  • 8 = H and I = 9 i.e. "HI".

    Below is C implementation of RSA algorithm for small values:

    // C program for RSA asymmetric cryptographic // algorithm. For demonstration values are // relatively small compared to practical // application #include<stdio.h> #include<math.h>    // Returns gcd of a and b int gcd(int a, int h) {     int temp;     while (1)     {         temp = a%h;         if (temp == 0)           return h;         a = h;         h = temp;     } }    // Code to demonstrate RSA algorithm int main() {     // Two random prime numbers     double p = 3;     double q = 7;        // First part of public key:     double n = p*q;        // Finding other part of public key.     // e stands for encrypt     double e = 2;     double phi = (p-1)*(q-1);     while (e < phi)     {         // e must be co-prime to phi and         // smaller than phi.         if (gcd(e, phi)==1)             break;         else             e++;     }        // Private key (d stands for decrypt)     // choosing d such that it satisfies     // d*e = 1 + k * totient     int k = 2; // A constant value     double d = (1 + (k*phi))/e;        // Message to be encrypted     double msg = 20;        printf("Message data = %lf", msg);        // Encryption c = (msg ^ e) % n     double c = pow(msg, e);     c = fmod(c, n);     printf("\nEncrypted data = %lf", c);        // Decryption m = (c ^ d) % n     double m = pow(c, d);     m = fmod(m, n);     printf("\nOriginal Message Sent = %lf", m);        return 0; } // This code is contributed by Akash Sharan.

    Output :

    Message data = 12.000000
    Encrypted data = 3.000000
    Original Message Sent = 12.000000

Digital Signatures and Certificates

Encryption – Process of converting electronic data into another form, called cipher text, which cannot be easily understood by anyone except the authorized parties.This assures data security.
Decryption– Process of translating code to data.

• Message is encrypted at the sender's side using various encryption algorithms and decrypted at the receiver's end with the help of the decryption algorithms.
• When some message is to be kept secure like username, password, etc., encryption and decryption techniques are used to assure data security.

Types of Encryption

1. Symmetric Encryption– Data is encrypted using a key and the decryption is also done using the same key.
2. Asymmetric Encryption-Asymmetric Cryptography is also known as public key cryptography. It uses public and private keys to encrypt and decrypt data. One key in the pair which can be shared with everyone is called the public key. The other key in the pair which is kept secret and is only known by the owner is called the private key. Either of the keys can be used to encrypt a message; the opposite key from the one used to encrypt the message is used for decryption.

Public key– Key which is known to everyone. Ex-public key of A is 7, this information is known to everyone.
Private key– Key which is only known to the person who's private key it is.

Authentication-Authentication is any process by which a system verifies the identity of a user who wishes to access it.
Non- repudiation– Non-repudiation means to ensure that a transferred message has been sent and received by the parties claiming to have sent and received the message. Non-repudiation is a way to guarantee that the sender of a message cannot later deny having sent the message and that the recipient cannot deny having received the message.
Integrity– to ensure that the message was not altered during the transmission.
Message digest -The representation of text in the form of a single string of digits, created using a formula called a one way hash function. Encrypting a message digest with a private key creates a digital signature which is an electronic means of authentication..

Digital Signature

A digital signature is a mathematical technique used to validate the authenticity and integrity of a message, software or digital document.

1. Key Generation Algorithms : Digital signature are electronic signatures, which assures that the message was sent by a particular sender. While performing digital transactions authenticity and integrity should be assured, otherwise the data can be altered or someone can also act as if he was the sender and expect a reply.
2. Signing Algorithms: To create a digital signature, signing algorithms like email programs create a one-way hash of the electronic data which is to be signed. The signing algorithm then encrypts the hash value using the private key (signature key). This encrypted hash along with other information like the hashing algorithm is the digital signature. This digital signature is appended with the data and sent to the verifier. The reason for encrypting the hash instead of the entire message or document is that a hash function converts any arbitrary input into a much shorter fixed length value. This saves time as now instead of signing a long message a shorter hash value has to be signed and moreover hashing is much faster than signing.
3. Signature Verification Algorithms : Verifier receives Digital Signature along with the data. It then uses Verification algorithm to process on the digital signature and the public key (verification key) and generates some value. It also applies the same hash function on the received data and generates a hash value. Then the hash value and the output of the verification algorithm are compared. If they both are equal, then the digital signature is valid else it is invalid.

The steps followed in creating digital signature are :

1. Message digest is computed by applying hash function on the message and then message digest is encrypted using private key of sender to form the digital signature. (digital signature = encryption (private key of sender, message digest) and message digest = message digest algorithm(message)).
2. Digital signature is then transmitted with the message.(message + digital signature is transmitted)
3. Receiver decrypts the digital signature using the public key of sender.(This assures authenticity,as only sender has his private key so only sender can encrypt using his private key which can thus be decrypted by sender’s public key).
4. The receiver now has the message digest.
5. The receiver can compute the message digest from the message (actual message is sent with the digital signature).
6. The message digest computed by receiver and the message digest (got by decryption on digital signature) need to be same for ensuring integrity.

Message digest is computed using one-way hash function, i.e. a hash fucntion in which computation of hash value of a is easy but computation of a from hash value of a is very difficult.

Digital Certificate

Digital certificate is issued by a trusted third party which proves sender's identity to the receiver and receiver’s identity to the sender.
A digital certificate is a certificate issued by a Certificate Authority (CA) to verify the identity of the certificate holder. The CA issues an encrypted digital certificate containing the applicant’s public key and a variety of other identification information. Digital signature is used to attach public key with a particular individual or an entity.
Digital certificate contains:-

1. Name of certificate holder.
2. Serial number which is used to uniquely identify a certificate, the individual or the entity identified by the certificate
3. Expiration dates.
4. Copy of certificate holder's public key.(used for encrypting messages and digital signatures)
5. Digital Signature of the certificate issuing authority.

Digital ceritifcate is also sent with the digital signature and the message.

Digital certificate vs digital signature :
Digital signature is used to verify authenticity, integrity, non-repudiation ,i.e. it is assuring that the message is sent by the known user and not modified, while digital certificate is used to verify the identity of the user, maybe sender or receiver. Thus, digital signature and certificate are different kind of things but both are used for security. Most websites use digital certificate to enhance trust of their users.