Skip to content

Classical Cryptography ​

Monoalphabetic cipher ​

Caesar cipher ​

  • Replace each letter by an element of Z26, that is, an integer from 0 to 25 (A = 0, B = 1,... Z = 25)
  • Chose a key k < 26, we'll have a function f (encrypt) and g (decrypt):

INFO

f(p)=(p+k)mod26

INFO

g(p)=f−1(p)=(p−k)mod26

Affine cipher ​

  • We can generalize shift ciphers further to slightly enhance security by using a function of the form

INFO

f(p)=(ap+b)mod26

Where a and b are integers and f is the bijection.

Prove: f is a bijection iff gcd(a, 26) = 1

  • To find decrypt function g(p)=f−1(p), we assume that c=(ap+b)mod26, we'll show p in term of c
  • c≡(ap+b)mod26 => ap≡(c−b)mod26 (1)
  • We can see that to solve the congruence equation (1), the gcd(a, 26) = 1 to obtain its inverse (See 4_4)
  • (1) => p≡(a−1⋅(c−b))mod26

Affine decryption

g(p)=a−1⋅(c−b)(mod26)

Block cipher ​

  • Encryption methods of Caesar/Affine cipher are vulnerable to attacks based on the analysis of letter frequency in the ciphertext.
  • We can make it harder to successfully attack ciphertext by replacing blocks of letters with other blocks of letters instead of replacing individual characters with individual characters

Transposition cipher ​

  • A transposition cipher is a simple type of block cipher that encrypts a message by rearranging the positions of letters, rather than changing the letters themselves.

  • The key is a permutation σ of the set

{1,2,…,m}
  • A permutation is a one-to-one function
σ:{1,2,…,m}→{1,2,…,m}
  • Encryption
    • Split the plaintext into blocks of size m.
    • If the message length is not divisible by m, add random letters to complete the last block.
    • Rearrange letters using the permutation σ.

If the plaintext block is

p1p2…pm

then the ciphertext block is

c1c2…cm=pσ(1)pσ(2)…pσ(m)
  • Decryption
    • Use the inverse permutation σ−1.

Given ciphertext

c1c2…cm

we rearrange using σ−1 to recover

p1p2…pm

Cryptosystems ​

  • A cryptosystem provides a general framework for defining encryption methods.
  • A cryptosystem is a five-tuple
(P,C,K,E,D)

where

  • P : set of plaintext strings
  • C : set of ciphertext strings
  • K : keyspace (set of all possible keys)
  • E : set of encryption functions
  • D : set of decryption functions

For each key k∈K

  • encryption function: Ek∈E
  • decryption function: Dk∈D

They satisfy

Dk(Ek(p))=p

for every plaintext p.

This means decrypting an encrypted message returns the original plaintext.

Private Key Cryptography ​

INFO

All classical ciphers, including shift ciphers and affine ciphers, are examples of private key cryptosystems

The RSA Cryptosystem ​

Each user has an encryption key

INFO

(n,e)

Key Construction ​

  1. Choose two large primes
p,q
  1. Compute the modulus
n=pq

Typically:

  • p and q each have about 300 digits
  • n has about 600 digits
  1. Choose an exponent e such that
gcd(e,(p−1)(q−1))=1

This means e is relatively prime to (p−1)(q−1).

The RSA Encryption ​

Step 1: Convert letters to numbers ​

Each letter → two digits

A=00,B=01,…,Z=25

Step 2: Create blocks ​

Let

n=pq

Split the digit string into blocks of 2N digits such that

2525…25<n

This ensures each block

mi<n

Pad the last block with X if needed.


Step 3: Encrypt ​

Each block

mi

is encrypted using

ci=mie(modn)

(using fast modular exponentiation)


Result ​

Ciphertext:

c1,c2,…,ck

RSA encrypts blocks of characters → blocks of numbers, so it is a block cipher.

The RSA Decryption ​

m≡cd(modpq)

Cryptographic Protocols ​

Key exchange (Diffie–Hellman) ​

Diffie–Hellman là một a protocol that two parties can use to exchange a secret key over an insecure communications channel without having shared any information in the past

Public Parameters ​

Alice and Bob publicly choose:

  • prime p
  • primitive root a of p

The computations are done in

Zp

Protocol Steps ​

  1. Alice chooses a secret
k1

and sends

ak1modp

to Bob.

  1. Bob chooses a secret
k2

and sends

ak2modp

to Alice.

Compute Shared Key ​

Alice and Bob compute the shared key

(ak2)k1modp=(ak1)k2modp

Digital signature ​

Digital signatures allow a recipient to verify that a message really came from the claimed sender.

They provide:

  • Authentication (who sent the message)
  • Integrity (message was not altered)

Alice's RSA Keys ​

Alice has:

  • Public key: (n,e)

  • Private key: d

Signing a Message ​

Alice wants to send a message (M).

  1. Convert the message into numbers.
  2. Split it into blocks:
(m1,m2,...,mk)
  1. Alice signs each block using her private key:
(si=mid(modn))

She sends the signature blocks:

(s1,s2,...,sk)

Verifying the Signature ​

Anyone can verify the signature using Alice's public key.

They compute:

(mi=sie(modn))

If the result equals the original message block, the signature is valid.

Built with ❤️ and curiosity