RSA-Basic

Posted on 2023-07-26 Edited on 2024-01-29 In CTF Views: Word count in article: 3.6k Reading time ≈ 13 mins.

RSA Basic

Have a lot waiting to be written, but just post them for convenience.

RSA is the first full public-key cryptosystem.

All operations in RSA involve modular exponentiation.

Modular exponentiation is exponentiation performed over a modulus.

Modular exponentiation is the remainder when an integer $b$ (the base) is raised to the power $e$ (the exponent), and divided by a positive integer $m$ (the modulus); that is, $c=b^e \mod m$. Form the definition of division, it follows that $0 \leq c < m$.

Modular exponentiation can be performed with a negative exponent $e$ by finding the modular multiplicative inverse $d$ of $b$ modulo $m$ using the extended Euclidean algorithm. \[ c=b^e \mod m=d^{-e} \mod m,where \space e<0 \space and \space b\cdot d \equiv 1\mod m \]

In RSA, modular exponentiation, together with the problem of prime factorisation, helps us to build a "trapdoor function". This is a function that is easy to compute in one direction, but hard to do in reverse unless you have the right information. It allows us to encrypt a message, and only the person with the key can perform the inverse operation to decrypt it.

Prerequisites:

Euler's Totient Function
Euler's Theorem
Multiplicative Inverse Theorem

Operation

Basic Principle

Find three large positive integers e,d and n, such that \[ (m^e)^d\equiv m\mod n \] and that knowing e and n, or even m will be extremely difficult to find d.

In addition, for some operations it is convenient that the order of the two exponentiations can be changed and that this relation also implies \[ (m^d)^e\equiv m\mod n \] RSA involves a public key and a private key.

Key Generation

Choose two large prime numbers p and q
- p and q should be chosen at random, be both large and have a large difference.
- p and q should keep secret
Compute n=pq
Compute$\space \space \varphi (n)\space$ ,where$\space \varphi(n)\space$is Euler's Totient Function.
Choose an integer e such that $2<e<\varphi(n)$ and $gcd(e,\varphi(n))=1$,that is e and $\varphi(n)$ is coprime.
Determined d as $ed\equiv 1 \mod n$. d is the modular multiplicative inverse of e modulo $\varphi(n)$

So, we get public key n and e , and private key n and d.

Encryption&Decryption

Encry: \[ c\equiv m^e \mod n \] Decry: \[ c^d\equiv (m^e) m\mod n \]

Sign Message

Suppose Alice uses Bob's public key to send him an encrypted message. In the message, she claimed to be Alice, but Bob has no way of verifying that the message was from Alice, since anyone can use Bob's public key to send him encrypted messages. So, we should sign the message.

Suppose message m,and n,e,d.

Suppose Alice want to send message m to Bob. She can use her own private key to do so. She produces a hash value of the message, and $S=H(M)^d \mod n$, and attaches it as a "signature" to the message. When Bob receives the signed message, he uses the same hash algorithm in conjunction with Alice's public key. He $H(M)=S^e\mod n$ (as he does when encrypting a message), and compares the resulting hash value with the message's hash value. If the two agree, he knows that the author of the message was in possession of Alice's private key and that the message has not been tampered with since being sent.

Why: \[ h(m)=hash(m) \]

\[ (h^e)^d=(h^d)^e\equiv h\mod n \]

Proof of correctness

(This part is not necessary to look.)

Using Fermat's little theorem

We want to show that \[ \space m^{ed}\equiv m \mod pq \] for every integer m when p and q are distinct prime numbers and e and d are positive integers satisfying $ed\equiv 1 \mod \varphi(pq)$

Since$\space \space \varphi(pq)=(p-1)(q-1)\space$so,we can write \[ ed-1=h(p-1)=k(q-1) \] To check whether two numbers, such as$\space m^{ed}\space$and m, are congruent mod pq , it suffices to check that they are congruent mod p and mod q separately.

To show$\space m^{ed}\equiv m \mod p\space$,we consider two cases:

If$\space m\equiv 0 \mod p\space$,m is a multiple of p. Thus $m^{ed}$ is a multiple of p. So $m^{ed}\equiv 0\equiv m \mod p$
If $m\equiv 0 \mod p$, \[ m^{ed}=m^{ed-1}m=m^{h(p-1)}m=(m^{p-1})^hm\equiv 1^h m\equiv m\mod p \] where we used Fermat's little theorem to replace $m^{p-1}\mod p$ with 1.

The verification that$\space m^{ed}\equiv m\mod q\space$proceeds in a completely analogous way.

So we can prove that \[ (m^e)^d\equiv m \mod pq \]

Attacks

Low exponents&small values of m

low exponents and small values of m has a judgment \[ m<n^{\frac{1}{e}} \] the result of $m^e$ is strictly less than modulus n.

we can just taking the eth root of the ciphertext over the integers.

Mathematica Basic

Euler's Totient Function

Euler's Totient function counts the positive integers up to a given integer $n$ that are relatively prime to $n$. also be called Euler's phi function.

It is the number of integers $k$ in the range(1,n) for which the greatest common divisor $gcd(n,k)=1$. The integers $k$ of this form are sometimes referred to as totatives of $n$.

Euler's totient function is a multiplicative function, meaning that if two numbers $m$ and $n$ are relatively prime, then $\varphi(mn)=\varphi(m)\varphi(n)$. The function gives the order of the multiplicative group of integers modulo n(the group of units of the ring $\mathbb Z/n\mathbb Z$).

Computing Euler's totient function

It states: \[ \varphi (n)=n \prod _{p|n}(1-\frac{1}{p}) \] where the product is over the distinct prime numbers dividing $n$.

An equivalent formulation is \[ \varphi(n)=p_1^{k_1-1}(p_1-1)p_2^{k_2-1}(p_2-1)\cdots p_r^{k_r-1}(p_r-1) \] where $n=p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}$ is the prime factorization of $n$ (this is ,$p_1,p_2,\cdots,p_r$ are distinct prime numbers)

Based on Phi is a multiplicative function and Value of phi for a prime power argument

IF $p$ is a prime and $k\ge 1$ then: \[ \varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)=p^k(1-\frac{1}{p}) \]

Proof: Since $p$ is a prime number, the only possible values of $gcd (p^k,m)$are $1, p, p^2, ..., p^k$, and the only way to have $gcd(p^k, m) > 1$ is if m is a multiple of p, that is, $m \in {p, 2p, 3p, ..., p^{k − 1}p = p^k}$, and there are $p^k − 1$ such multiples not greater than $p^k$. Therefore, the other $p^k − p^k − 1$ numbers are all relatively prime to $p^k$.

Fermat's Little Theorem

If $p$ is a prime number,then for any integer $a$, the number $a^p-a$ is an integer multiple of p. In the notation of modular arithmetic, this is expressed as: \[ a^p\equiv a\mod p \]

If $a$ is not divisible by $p$, that is if $a$ is coprime to $p$, Fermat's little theorem is equivalent to the statement that $a^{p-1}-1$ is an integer multiple of $p$, or in symbols: \[ a^{p-1}\equiv 1 \mod p \]

Euler's Theorem

Let $n$ be a positive integer, and let a be an integer that is relatively prime to n. Then \[ a^{\varphi(n)}\equiv 1 \mod n \] where ϕ(n) is Euler's totient function.

Modular multiplicative inverse

a modular multiplicative inverse of an integer a is an integer x such that \[ ax\equiv 1 \mod m \] which is the shorthand way of writing that$\space \space (ax-1)|m$.

$x\mod m$ exists if and only if$\space \space gcd(a,m)=1$,and$xm$is unique.

There is only one integer that$\space 0\le x\le m-1$.

Not every element of a complete residue system modulo m has a modular multiplicative inverse. After removing the elements of a complete residue system that are not relatively prime to m, what is left is called a areduced residue system, all of whose elements have modular multiplicative inverse. The number of element in a reduced residue system is$\space \space \varphi(m)$.

Quadratic Residues

An integer $q$ is called a quadratic residue modulo $n$ if it is congruent to a perfect square modulo $n$ \[ x^2\equiv q\mod n \] Otherwise,$q$ is called a quadratic non-residue modulo n.

Euler's criterion

A formula for determining whether an integer is a quadratic residue modulo a prime. Precisely,

Let $p$ be an odd prime and $a$ be an integer coprime to $p$. Then \[ (\frac{a}{p})=\begin{cases}\ 1 \mod p\quad &&if \space there \space is \space an \space integer \space x \space such \space that \space x^2\equiv a \mod p\\ -1 \mod p &&if \space there \space is \space no \space such \space integer \space \end{cases} \] Proof(may not important):

Because the modulus is prime, Lagrange's theorem applies: a polynomial of degree $k$ can only have at most $k$ roots. In particular, $x^2\equiv a \mod p$ has at most 2 solutions for each $a$.

This implies that besides 0 there are at least $\frac{p-1}{2}$ distinct quadratic residues modulo $p$: each of the $p-1$ possible values of $x$ can only be accompanied by one other to give the same residue.

In fact, $(p-x)^2\equiv x^2 \mod p$.This is because $(p-x)^2\equiv p^2 -2px+x^2\equiv x^2 \mod p$. So the $\frac{p-1}{2}$ distinct quadratic residues are: $1^2,2^2,\cdots,(\frac{p-1}{2})^2\mod p$.

As $a$ is coprime to $p$ ,Fermat's little theorem says that: \[ a^{p-1}\equiv 1\mod p \] which can be written as \[ (a^{\frac{p-1}{2}}-1)(a^{\frac{p-1}{2}}+1)\equiv 0\mod p \] Since the integers mod $p$ from a field, for each $a$, one or the other of these factors must be zero.

Now if $a$ is a quadratic residue, $a\equiv x^2$, \[ a^{\frac{p-1}{2}}\equiv (x^2)^{\frac{p-1}{2}}\equiv x^{p-1}\equiv 1\mod p \] So every quadratic residue (mod $p$) makes the first factor zero.

Applying Lagrange's theorem again, we note that there can be no more than $\frac{p-1}{2}$ values of $a$ that make the first factor zero. But as we noted at the beginning, there are at least $\frac{p-1}{2}$ distinct quadratic residues (mod p) (besides 0).Therefore, they are precisely the residue classes that make the first factor zero. The other $\frac{p-1}{2}$ residue classes, the non-residues, must make the second factor zero, or they would not satisfy Fermat's little theorem.

Legendre Symbol

Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo of an odd prime number $p$: its value at a (nonzero) quadratic residue mod $p$ is 1 and at a non-quadratic residue (non-residue) is −1. Its value at zero is 0.

Definition:

Let $p$ be an odd prime number. An integer $a$ is a quadratic residue modulo $p$ if it is congruent to a perfect square modulo $p$ and is a quadratic non-residue modulo $p$ otherwise. The Legendre symbol is a function of $a$ and $p$ defined as: \[ (\frac{a}{p})=\begin{cases}\ 1 \quad &&if \space a \space is \space quadratic \space residue \space modulo \space p \space and \space a\not\equiv 0 \mod p\\ -1 \quad &&if \space a \space is \space quadratic \space nonresidue \space modulo \space p \space \\ 0 \quad &&if\space a\equiv 0 \mod p \end{cases} \]

Explicit Formula: \[ (\frac{a}{p})\equiv a^{\frac{p-1}{2}}\mod p \quad and \quad (\frac{a}{p})\in\{-1,0,1\} \]

Properties of the Legendre symbol

Given a generator $g\in \mathbb F_p^* ,if \space x=g^r$,then $x$ is a quadratic residue if and only if $r$ is even. This show that half of the nonzero elements in $\mathbb F^* _p$ are quadratic residues.
(Important)If $p\equiv 3 \mod 4$ then the fact that

$\frac{p+1}{4}+\frac{p+1}{4}=\frac{(p-1)+2}{2}$ givens us that $a=x^{\frac{p+1}{4}}$ is the square root of the quadratic residue $x$.
The Legendre symbol is periodic in its first( or top) argument :if $a\equiv b\mod p$,then \[ (\frac{a}{p})=(\frac{b}{p}) \]
The Legendre symbol is a completely multiplicative function of its top argument: \[ (\frac{ab}{p})=(\frac{a}{p})(\frac{b}{p}) \] make compute an easy job.
In particular, the product of two numbers that are both quadratic residues or quadratic non-residues modulo $p$ is a residue, whereas the product a residue with a non-residue is an non-residue.

Quadratic Residue * Quadratic Residue = Quadratic Residue Quadratic Residue * Quadratic Non-residue = Quadratic Non-residue Quadratic Non-residue * Quadratic Non-residue = Quadratic Residue

A special case is the Legendre symbol of a square:

\[ (\frac{x^2}{p})=\begin{cases} 1 &&\quad if\space p \not\mid x\\ 0 &&\quad if \space p\mid x \end{cases} \]

Tonelli–Shanks algorithm

(maybe you can block this part, you just need to know its function,and when to use it)

The Tonelli–Shanks algorithm is used in modular arithmetic to solve for $r$ in a congruence of the form $r^2 \equiv n \mod p$, where $p$ is a prime: that is, to find a square root of $n$ modulo $p$.

Tonelli–Shanks cannot be used for composite moduli: finding square roots modulo composite numbers is a computational problem equivalent to integer factorization.

Algorithm:

Inputs:

$p$ ,a prime
$n$, an element of $\mathbb Z/p\mathbb Z$ such that solutions to the congruence $r^2=n$ exist;when this is so we say that $n$ is quadratic residue mod p

Outputs:

$r$ in $\mathbb Z /p\mathbb Z$ such that $r^2=n$

Algorithm:

By factoring out powers of 2, find Q and S such that $p-1=Q2^S$ with Q odd

If S=1, output $r=\pm a^{\frac{p+1}{4}}$ Time spend $O(ln(p)^3)$
Search for a $z$ in $\mathbb Z/p\mathbb Z$ which is a quadratic non-residue
- Half of the elements in the set will be quadratic non-residues
- Candidates can be tested with Euler's criterion
- So we can randomly choose integer $u \in \mathbb Z/p\mathbb Z$ , until we find a $z$ such that $(\frac{z}{p})=-1$, the time spend is $O(ln(p)^2)$
Let \[ M\leftarrow S\\ c\leftarrow z^Q\\ t \leftarrow n^Q\\ R \leftarrow n^{\frac{Q+1}{2}} \]
Loop:
- If $t=0$, return $r=0$
- If $t=1$ ,return $r=R$
- Otherwise, use repeated squaring to find the least $i,0<i<M$ such that $t^{2^i}=1$
- Let \[ b \leftarrow c^{2^{M-i-1}}\\ M \leftarrow i\\ c \leftarrow b^2\\ t \leftarrow tb^2\\ R \leftarrow Rb \]

Once you have solved the congruence with $r$ the second solution is $-r\mod p$ . If the least $i$ such that $t^{2^i}=1$ is M,then no solution to the congruence exists , i.e. $n$ is not a quadratic residue.

Example:

Solving the congruence $r^2\equiv 5\mod 41$, 41 is prime as required and $41\equiv 1\mod 4$, 5 is quadratic residue by Euler's criterion: $5^\frac{41-1}{2}=5^{20}\equiv 1\mod p$

$p-1=40=5\cdot 2^3$ so $Q\leftarrow5,S\leftarrow 3$
Find a value for z:
- $2^\frac{41-1}{2}=1$, so 2 is a quadratic residue by Euler's criterion
- $3^\frac{41-1}{2}=40=-1$, so 3 is a quadratic non-residue: set$z \leftarrow3$
Let:
- $M\leftarrow S=3$
- $c\leftarrow z^Q=3^5=38$
- $t\leftarrow n^Q=5^5=9$
- $R\leftarrow n^\frac{Q+1}{2}=5^\frac{5+1}{2}=2$
Loop:
- First iteration:
  - $t\neq 1$, so we're not finished
  - $t^{2^1}=40.t^{2^2}=1$ ,so $i\leftarrow2$
  - $b\leftarrow c^{2^{M-i-1}}=38^{2^{3-2-1}}=38$
  - $M\leftarrow i=2$
  - $c\leftarrow b^2=38^2=9$
  - $t\leftarrow tb^2=9\cdot 9=40$
  - $R\leftarrow Rb=2\cdot 38=35$
- Second iteration:
  - $t\neq 1$, so we're still not finished
  - $t^{2^1}=1$, so $i\leftarrow1$
  - $b\leftarrow c^{2^{M-i-1}}=9^{2^{2-1-1}}=9$
  - $M\leftarrow i=1$
  - $c \leftarrow b^2=9^2=40$
  - $t\leftarrow tb^2=40\cdot 40 =1$
  - $R \leftarrow Rb=35 \cdot 9=28$
- Third iteration:
  - $t=1$, and we are finished;return $r=R=28$

Algorithm implementation

a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161

def Legendre(a,p):
    return pow(a,(p-1)//2,p)

def Tonelli(n,p):
    assert Legendre(n,p)==1
    if p%4==3:
        return pow(n,(p+1)//4,p)
    q=p-1
    s=0
    while q%2 ==0:
        q = q// 2
        s += 1
    for z in range(2,p):
        if Legendre(z,p)==p-1:
            c=pow(z,q,p)
            break
    r = pow(n,(q+1)//2,p)
    t = pow(n,q,p)
    m=s
    if t%p ==1:
        return r
    else :
        i=0
        while t%p !=1:
            temp=pow(t,2**(i+1),p)
            i+=1
            if temp%p==1:
                b=pow(c,2**(m-i-1),p)
                r=(r*b)%p
                c=(b*b)%p
                t=(t*c)%p
                m=i
                i=0
    return r
print(Tonelli(a,p))

中国剩余定理 (Chinese remainder theorem)

(中国剩余定理肯定是要用中文的)

关于一元线性同余方程组的定理，说明了一元线性同余方程组有解的准则以及求解方法.

对于以下一元线性方程组 \[ \begin{cases} x \equiv a_1 \mod m_1\\ x\equiv a_2 \mod m_2\\ \vdots\\ x\equiv a_n \mod m_n \end{cases} \] 且 $m_1,m_2,\cdots,m_n$ 其中任意两数互质，则对任意的整数 $a_1,a_2,\cdots,a_n$, 方程组有解，并且通解可以用如下方式构造得到:

设 $M=m_1\times m_2\times \cdots \times m_n=\prod _{i=1}^n m_i$ 是整数 $m_1,m_2,\cdots,m_n$ 的乘积，并设 $M_i=M/m_i,\forall i\in\{1,2,\cdots,n\}$, 即 $M_i$ 是除了 $m_i$ 以外的 $n-1$ 个整数的乘积.
设 $t_i=M_i^{-1} 为 $$M_i$ 模 $m_i$ 的数论倒数:$t_iM_i\equiv 1\mod m_i,\forall i\in \{1,2,\cdots,n\}$
方程组的通解形式为:$x=a_1t_1M_1+a_2t_2M_2+\cdots+a_nt_nM_n+kM=kM+\sum_{i=1}^n a_it_iM_i,k\in \mathbb Z$. 在模 $M$ 的意义下，方程组只有一个解 $\sum_{i=1}^n a_it_iM_i$

脚本如下:

import gmpy2
a=[2,3,5]
m=[5,11,17]

def gcd(a,b):
    return gcd(b,a%b) if b else a

def Crt(a,m):
    for i in range(len(m)):
        for j in range(i+1,len(m)):
            if gcd(m[i],m[j])!=1:
                print("not coprime")
                return -1
    M=1
    #Calculate the product of m
    for i in m:
        M=M*i
    Mm=[]
    #Calculate each M//m
    for i in m:
        Mm.append(M//i)
    t=[]
    for i in range(len(m)):
        t.append(gmpy2.invert(Mm[i],m[i]))
    #Calculate the answer
    x=0
    for i in range(len(m)):
        print(Mm[i]*t[i]*a[i])
        x+=Mm[i]*t[i]*a[i]
    x=x%M
    return x

print(Crt(a,m))

实现 2:

import math

def  merge(a1,n1,a2,n2):
    d = math.gcd(n1,n2)
    c = a2-a1
    if c%d!=0:
        return 0
    c = (c%n2+n2)%n2
    c = c//d
    n1 = n1//d
    n2 = n2//d
    c *= gmpy2.invert(n1,n2)
    c %= n2
    c *= n1*d
    c += a1
    global n3
    global a3
    n3 = n1*n2*d
    a3 = (c%n3+n3)%n3
    return 1
def exCRT(a,n):
    a1=a[0]
    n1=n[0]
    le= len(a)
    for i in range(1,le):
        a2 = a[i]
        n2=n[i]
        if not merge(a1,n1,a2,n2):
            return -1
        a1 = a3
        n1 = n3
    global mod
    mod=n1
    return (a1%n1+n1)%n1
def exCRT_getequation(a,n):
    a1=a[0]
    n1=n[0]
    le= len(a)
    for i in range(1,le):
        a2 = a[i]
        n2=n[i]
        if not merge(a1,n1,a2,n2):
            return -1
        a1 = a3
        n1 = n3
    return (a1,n1)
#a为余数列表
#n为模数列表