Tonelli shanks algorithm is used for finding modular square root of number n under mod p in minimal time

def is_quadratic_residue(n,p):
    '''check if the n is qudratic residue in mod p using legendre symbol'''
    if n%p==0:
        return True
    return pow(n,(p-1)//2,p)==1

def tonelli_shanks(n,p):
    '''find the modular square root of n in mod p if possible'''
    if n%p==0:
        # when n = o(mod p) square root of 0 is 0
        return 0
    if not is_quadratic_residue(n,p):
        print("square root does not exits")
        return None
    
    if p%3==4:
        return pow(n,(p+1)//4,p)
    
    # for all p%4==1 we will apply tonelli shanks algorithm
    # step 1
    # p-1 = 2^s.q
    q=p-1
    s=0
    while(q%2==0):
        s+=1
        q=q//2
    # step 2
    n_res = 2
    while is_quadratic_residue(n_res,p):
        n_res+=1
    print(n_res)
    # step 3
    m=s
    c=pow(n_res,q,p)
    t=pow(n,q,p)
    r=pow(n,(q+1)//2,p)
    
    # step 4
    while(t!=1):
        i=0
        temp=t
        while(temp!=1):
            i+=1
            temp = (temp*temp)%p
        pow2 = pow(2,m-i-1)
        b=pow(c,pow2,p)
        m=i
        c = (b**2)%p
        t = (t*b**2)%p
        r = (r*b)%p
    
    return r

x=tonelli_shanks(5,41)
print(x)

Carmichael lambda is the smallest positive integer $m$ such that

$a^m = 1(mod n)$ $\forall$ a coprime to n.

Definition​

For a number: $n = {p_1}^{r_1}.{p_2}^{r_2}....{p_k}^{r_k}$ Carmichael lambda function is defined as $\lambda(n) = lcm(\lambda({p_1}^{r_1}), \lambda({p_2}^{r_2}),....\lambda({p_k}^{r_k}))$ where $\lambda(p^r)$ is defined as:

$\lambda(p^r) = \begin{cases} \frac{1}{2} \phi(p^r) & \text{ if } p = 2 \text{ and } r \geq 3 \\ \phi(p^r) & \text{otherwise} \end{cases}$

where $\phi$ is Euler's totient function.and it is given by

${\phi(p^r) = p^{r-1}.(p-1)}$

Cryptography is an entire field dedicated to secure communication! It is a very deep and complex field, but we will cover some of the basics here.

Thousand years ago Julius Caesar simplest form of encyption Caesar Cipher.

Caesar Cipher​

In Caesar Cipher, each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet. For example, with a shift of 3, the message DOG will be replaced by GRJ.Since it is very easy to detect it by finding all possible shifts, it is not a very secure encryption algorithm.

Substitution Cipher​

Similar to the Caeser cipher, substitution ciphers encrypt messages by substituting each letter in the message with a different one, according to some alphabet.But we substitute each letter with a different one, not just shifted by a fixed number of positions. For example: A -> D B -> F C -> G Now the message ABC would be encrypted as DFG.

It is also not a very secure encryption algorithm, because it is very easy to detect the pattern and decrypt the message using frequency analysis since we know that in English alphabet, not all characters are distributed evenly.

Vigenere Cipher​

Vigenere cipher is a method of encrypting alphabetic text. It uses a simple form of polyalphabetic substitution. A polyalphabetic cipher is any cipher based on substitution, using multiple substitution alphabets .The encryption of the original text is done using the Vigenère square or Vigenère table. In this cipher we use a key for encrypting plaintext and the key is repeated as many times as necessary to encrypt the plaintext.And encryption is done by using the Vigenère square or Vigenère table.You can read more about it GFG or Wikipedia.

For advanced cipher visit the blog

It is of two types:

• ciphertext only attack: In this type of attack, the attacker has access to the ciphertext but not the plaintext. The attacker tries to find the plaintext or the key.
• known plaintext attack: In this type of attack, the attacker has access to the ciphertext and some of the plaintext. The attacker tries to find the key.

Cryptanalysis is of two forms:

• Linear Cryptanalysis: Linear cryptanalysis is a statistical attack technique used to analyze the linear relationship between the plaintext, ciphertext, and the key of a symmetric encryption algorithm. It exploits the linearity of the algorithm's components, such as substitution boxes (S-boxes) and linear transformations, to recover the key. This includes

  • contructing linear approximations
  • collecting ciphertext-plaintext pairs
  • finding key bits that can be exploited
  • expanding the key(deduce more bits of key)

• Differential Cryptanalysis: Differential cryptanalysis is statistical attack technique that aims to exploit the behavior of the differences between pairs of plaintexts, ciphertexts, and the corresponding subkeys in a symmetric encryption algorithm. It focuses on analyzing the differences rather than the linear relationships in the algorithm.This includes

  • creating differential characterstics
  • collect ciphertext plaintext pairs
  • find subkeys bits
  • recover complete key using knowledge of subkeys

Lattices are used as a fundamental tool for cryptanalysis of public key cryptosystems. There are hard computational problems on lattices that have been used as a building block for public key cryptosystems (e.g., the Goldreich-Goldwasser-Halevi (GGH) cryptosystem, the NTRU cryptosystem, the Ajtai-Dwork cryptosystem, and the LWE cryptosystem);

Lattice​

A lattice is a subset of the vector space Rm. We write all vectors as rows; be warned that many books and papers write lattice vectors as columns. We denote by kvk the Euclidean norm of a vector v ∈ Rm; though some statements also hold for other norms.

Definition: Let ${b_1 , . . . , b_n}$ be a linearly independent set of (row) vectors in $R_m$ (m ≥ n). The lattice generated by ${b_1 , . . . , b_n}$ is the set of integer linear combinations of the bi.

The vectors b1, . . . , bn are called a lattice basis.The lattice rank is n and the lattice dimension is m. If n = m then L is said to be a full rank lattice.

A basis matrix B of a lattice L is an n x m matrix formed by taking the rows to be basis vectors ${b_i}$. Thus ${B_{i,j}}$ is the j-th entry of the row ${b_i}$ and ${\textcolor{aqua}{L = \lbrace xB : x ∈ Z^n \rbrace}}$

By assumption the rows of a basis matrix are always linearly independent.

Lattice Reduction​

Lattices can also be used to build cryptographic protocols, whose security is based on two fundamental "hard" problems:

The Shortest Vector Problem (SVP): find the shortest non-zero vector in a lattice L. In other words, find the non-zero vector within v ∈ L such that ||v|| is minimised.

The Closest Vector Problem (CVP): Given a vector w ∈ Rm that is not in L, find the vector v ∈ L that is the closest to w, i.e. find the vector v ∈ L such that ||v - w|| is minimised.

Gauss developed his algorithm to find an optimal basis for a two-dimensional lattice given an arbitrary basis. Moreover, the output v1 of the algorithm is a shortest nonzero vector in L, and so solves the SVP.

L = matrix(ZZ, [[1, 1,3], [1, 2,-3], [1, 3,1]])
X = L.LLL()
# X will give is the reduced matrix

Gauss's algorithm roughly works by subtracting multiples of one basis vector from the other until it's no longer possible to make them any smaller. As this works in two-dimensions, it's nice to visualise. Here's a description of the algorithm from "An Introduction to Mathematical Cryptography", Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman:

Algorithm for Gaussian Lattice Reduction

Loop
   (a) If ||v2|| < ||v1||, swap v1, v2
   (b) Compute m = ⌊ v1∙v2 / v1∙v1 ⌉
   (c) If m = 0, return v1, v2
   (d) v2 = v2 - m*v1
Continue Loop

Note the similarity to Euclid's GCD algorithm with the "swap" and "reduction" steps, and that we have round the float, as on a lattice we may only use integer coefficients for our basis vectors.

lattices contain hard problems which can form trapdoor functions for cryptosystems. We also find that in cryptanalysis, lattices can break cryptographic protocols which seem at first to be unrelated to lattices.

You can read more about lattices in book Book .