2 posts tagged with "cryptography"

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)

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 .