# CRYPTOGRAPHY

### Objectives of cryptography.
> - Data Privacy(confidentiality)
> - Data Authenticity(it came from from where it claims)
> - Data integrity(it has not been modified on the way) in the digital world

### Types of Cryptography
<br>1. **Symmetric Key Cryptography**: It is an encryption system where the sender and receiver of message use a single common key to encrypt and decrypt messages. Symmetric Key Systems are faster and simpler but the problem is that sender and receiver have to somehow exchange key in a secure manner. The most popular symmetric key cryptography system are Data Encryption System(DES) and Advanced Encryption System(AES).

<br>2. **Hash Functions**: There is no usage of any key in this algorithm. A hash value with fixed length is calculated as per the plain text which makes it impossible for contents of plain text to be recovered. Many operating systems use hash functions to encrypt passwords.

<br>3. **Asymmetric Key Cryptography**: Under this system a pair of keys is used to encrypt and decrypt information. A receiver’s public key is used for encryption and a receiver’s private key is used for decryption. Public key and Private Key are different. Even if the public key is known by everyone the intended receiver can only decode it because he alone know his private key. The most popular asymmetric key cryptography algorithm is RSA algorithm.

### RSA
<br>The Rivest-Shamir-Adleman (RSA) encryption algorithm is an asymmetric encryption algorithm that is widely used in many products and services. Asymmetric encryption uses a key pair that is mathematically linked to encrypt and decrypt data. A private and public key are created, with the public key being accessible to anyone and the private key being a secret known only by the key pair creator. ==With RSA, either the private or public key can encrypt the data, while the other key decrypts it==. This is one of the reasons RSA is the most used asymmetric encryption algorithm.

#### Generaation of Key
Steps:-

> 1. Select two large prime number, `p` and `q`.
> 2. Generate modulus of encryption `n = p * q`
> 3. Choose number `e` such that it 1 < e < n and gcd(e, $\phi$(n)) = 1, where $\phi$(n) = (p-1) * (q-1)
> 4. Now `<e, n>` becomes the public key.
> 5. to determine private key `d`, we use the following formula:
d = e^-1^(mod $\phi$)
> 6. `<d, n>` becomes the private key.
#### Encryption and Decryption

let message be denoted as `m` and ciphertext be denoted as `c`.
> 1. c = m^e^(mod n)
> 2. m = c^d^(mod n)

#### Uses of RSA in real life:
> 1. Web browser(https)
> 2. Email sevices
> 3. virtual Private connections (VPNs) etc.

## Lattice Based Cryptography
Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof. Lattice-based constructions are currently important candidates for post-quantum cryptography. Unlike more widely used and known public-key schemes such as the RSA cryptosystems — which could, theoretically, be defeated using Shor's algorithm on a quantum computer — some lattice-based constructions appear to be resistant to attack by both classical and quantum computers. Furthermore, many lattice-based constructions are considered to be secure under the assumption that certain well-studied computational lattice problems cannot be solved efficiently.

### What is Lattice in lattice based cryptosystem
A lattice in this context resembles a grid of graph paper - using a set of points located at the crossings of a lattice of straight lines. This grid is not finite in any way. Instead, a lattice describes a pattern that continues into the infinite.
<br>
<br>
Starting with a set of points, known as vectors, numbers are then added and subtracted in any integer multiples. The hard problem is finding points in the lattice that are close to 0 or close to some other point. These problems are quite simple in 2 dimensions, but they become extremely challenging in 400 dimensions, for example. Within the diagram above, an example would be that one set of points could be the private key and another set of points that are further away could be the public key.

### Elgamal Cryptosystem
ElGamal encryption is a public-key cryptosystem. It uses asymmetric key encryption for communicating between two parties and encrypting the message. This cryptosystem is based on the difficulty of finding discrete logarithm in a cyclic group that is even if we know g^a^ and g^k^, it is extremely difficult to compute g^ak^.

Suppose Alice wants to communicate with Bob.

1. Bob generates public and private keys:
> - Bob chooses a very large number q and a cyclic group Fq.
> - From the cyclic group Fq, he choose any element g and
an element a such that gcd(a, q) = 1.
> - Then he computes h = ga.
> - Bob publishes F, h = ga, q, and g as his public key and retains a as private key.
2. Alice encrypts data using Bob’s public key :
> - Alice selects an element k from cyclic group F
such that gcd(k, q) = 1.
> - Then she computes p = gk and s = hk = gak.
> - She multiples s with M.
> - Then she sends (p, M*s) = (gk, M*s).
3. Bob decrypts the message :
> - Bob calculates s′ = pa = gak.
> - He divides M*s by s′ to obtain M as s = s′.

#### This all cryptosystem RSA and elgamal is based of prime number so what is prime number.
> **Prime Numbers** : A prime number is a number greater than 1 and divisible by 1 and itself.
> Sieve of Eratosthenes algorithm is used for finding n digit prime number

from math import sqrt, pow
sz = 100005
isPrime = [True for i in range(sz + 1)]
 
# Function for Sieve of Eratosthenes
def sieve():
    isPrime[0] = isPrime[1] = False
 
    for i in range(2, int(sqrt(sz)) + 1, 1):
        if (isPrime[i]):
            for j in range(i * i, sz, i):
                isPrime[j] = False
 
# Function to print all the prime
# numbers with d digits
def findPrimesD(d):
     
    # Range to check integers
    left = int(pow(10, d - 1))
    right = int(pow(10, d) - 1)
 
    # For every integer in the range
    for i in range(left, right + 1, 1):
         
        # If the current integer is prime
        if (isPrime[i]):
            print(i, end = " ")
         
# Driver code
if __name__ == '__main__':
     
    # Generate primes
    sieve()
    d = 1
    findPrimesD(d)