Post

Cryptography part 1

Posted Updated
By KVN
6 min read
Cryptography part 1

What is Cryptography?

Cryptography is a branch of cyber security focusing on encrypting and decrypting sensitive information

How I view Cryptography ?

Cryptography is an application of Mathematics where we use problems which are easy to create but logically impossible to solve to our advantage

Types of Cryptography

  • Symmetric Encryption
  • Asymmetric Encryption
  • Hashing

What is Hashing?

Hashing is the process of converting a input to an irreversible output using a function(hash function) confusion, diffusion and irreversibility are the main properties of good hashing algorithms

  • confusion: the input shows no clear relation to output
  • diffusion: the output length is always of the same size for all inputs, since it considers more than a single bit / byte for every output bit / byte

example of cipher with confusion but without diffusion abcd -> zyxw in diffusion changing one char will change the entire cipher but here only one output char is changing

  • irreversibility: What changes hashing from symmetric encryption is irreversibility

\(f(a) = b\) but \(f^-1(b )\) is not necessarily a, this situation happens because of hash collisions.

md5 and sha are commonly used hashing algorithms

Applications of hashing

  • hashes are commonly used to verify data integrity like a check sum for large files
  • passwords are hashed to preserve privacy of users
  • git uses SHA to make unique commit hashes
  • auth tokens like JWT use hashing algorithms with salt in their signatues, reading solutions for the chall jauth helped me understand jwt and need for good hash functions

Number Theory for Cryptography

Modular Arithmetic

  • Definition: Modular Arithmetic, also known as clock arithmetic, is a fundamental concept in number theory.

  • Operation: The result of a modular operation lies in a finite set of real numbers less than the modulus.

    \[a \mod b \equiv c\]

    where ( \(0 \leq c < b\) )

The Extended Eucledian Algorithm

The Extended Euclidean Algorithm is an extension of the Euclidean Algorithm, which is used to compute the greatest common divisor (GCD) of two integers. The Extended Euclidean Algorithm not only finds the GCD but also finds a way to express this GCD as a linear combination of the two integers. In other words, it finds integers ( x ) and ( y ) such that:

\[ax + by = \text{gcd}(a, b)\]

where a and b are the two integers.

1
2
3
4
5
6
7
8

def extended_euclidean(a, b):
    if b == 0:
        return a, 1, 0
    else:
        gcd, x1, y1 = extended_euclidean(b, a % b)
        x = y1
        y = x1 - (a // b) * y1
        return gcd, x, y

Totient function

  • Definition: It is a fundamental concept in number theory, the function is defined as the number of positive integers less than n which are coprime to n
  • totient function \(\phi(n) = (n-1)\) when n is an integer
  • when n is not a prime number we decompose n into multiples of its prime factors and apply totient function on each of those prime numbers, the product of all the totients of prime numbers is the totient of composite number
  • ie \(\phi(n) = \phi(p) _ \phi(q)\) when n = p _ q

Asymmetric Encryption

imagine you want to talk to someone but if you do it over an insecure protocol like http odds are that people who eavesdrop can not only read your messages but also forge fake messages

to avoid this we need a key kind of thing to encrypt and decrypt our messages

what if both reciever and sender agree that they will send the messages by incrementing their ASSCI value by a constant let us say 2 then a will be c and b will be d

this isn’t the best key but for simplicity let us assume this thing

now real question is how can I communicate with the other end and share my secret key in a secure channel where no one can decode what i send

that’s where asymetric encryption comes into picture

  • Definition: Asymmetric Encryption uses two keys: a public key for encryption and a private key for decryption.

  • RSA Encryption Algorithm

    • Encryption and Decryption:

      • Encryption: \(c = m^e \mod n\)

      • Decryption: \(m = c^d \mod n\)

        where c is the cipher text m is the plain text e is the encryption exponent d is the decryption exponent n is the product of primes p and q

    • Key Generation:

      • Choose two large prime numbers p and q
      • Compute n = p * q
      • Calculate the totient function \(\phi(n) = (p-1)(q-1)\)
      • Choose an encryption exponent e such that \((1 < e < \phi(n) )\) and \(gcd(e, \phi(n)) = 1\)
      • Compute the decryption exponent d such that \(d \equiv e^{-1} \mod \phi(n)\)
      1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

      from Crypto.Util import number
def generate_keypair(bits=1024):
    p = number.getPrime(bits)
    q = number.getPrime(bits)
    while q == p:
        q = number.getPrime(bits)
    n = p * q
    phi = (p - 1) * (q - 1)
    e = 65537
    d = number.inverse(e, phi)
    return ((e, n), (d, n))

def encrypt(public_key, plaintext):
    e, n = public_key
    plaintext_int = int.from_bytes(plaintext.encode('utf-8'), byteorder='big')
    if plaintext_int >= n:
        raise ValueError("Plaintext too large for the key size.")
    cipher_int = pow(plaintext_int, e, n)
    return cipher_int

def decrypt(private_key, ciphertext):
    d, n = private_key
    plain_int = pow(ciphertext, d, n)
    length = (plain_int.bit_length() + 7) // 8
    plaintext = plain_int.to_bytes(length, byteorder='big').decode('utf-8')
    return plaintext

This algorithm depends on the dificulty to prime factorize n for large values of p and q

RSA encryption algorithm is not quantum safe, with enough qbits shores algorithm can decompose the number to extract the primes in no time, fortunately our state of the art quantum computers dont have sufficient qbits yet

  • Deffie-Hellman Algorithm

    This algorithm depends on the discrete log problem

Discrete Log Problem

  • Definition: The discrete log problem is an NP-complete problem widely used in cryptographic applications.

  • Mathematical Representation

    If

    \[a^e \mod b \equiv c\]

    then

    \[e \equiv \log\_{a}{c} \mod b\]

    This problem is not feasible to solve but can be verified using the original equation.

The Deffie hellman key exchnage uses the discrete log problem to exhchange keys securely

In mechanism there are two public keys and a common private key

let a be the private exponent of A and b be the private exponent of B let g be the generator and p be a large prime agreed upon

\[Apub = g ^ a \mod p\] \[Bpub = g ^ b \mod p\] \[Apriv = Bpriv = Apub^b \mod p = Bpub ^ a \mod p\]

since Apub, Bpub, g,p are public but none of a or b can be computed because of the discrete log problem a secure channel is established

Deffie-Hellman is also not quantum safe, there are few quantum safe implementations of Deffie-Hellman but not yet adapted by people, shores algorithm can find a solution for the discrete log problem in reasonable amount of time

cryptography
hashing encryption
This post is licensed under CC BY 4.0 by the author.