# Crypto



## RSA Attacks


### Wiener Attack


>$\phi(n)$  = (p - 1) (q - 1) <br>
 $\phi(n)$  = pq - (p + q) + 1 <br> 
 $\phi(n)$  $\cong$  n  <br><br>
 ed = k * $\phi(n)$ + n <br>
 ed - k * $\phi(n)$  = 1 <br><br><br> 
 $\frac{e}{\phi(n))}$ - $\frac{k}{d}$ = $\frac1{d * \phi(n)}$ <br><br>
 Now $\frac1{ d * phi(n)}$ is very small <br>
 $\therefore \frac{e}{n}$  $\cong$ $\frac{d}{n}$ <br>
 We use continued fractions to get approx of $\frac{k}{d}$ <br>

<br>
<br>


<b>Few Observations:</b>
1. As ed = 1 mod $\phi$(n) , and $\phi$(n) is even, Therefore e and d must be odd
2. $\phi$(n) is a whole number. Therefore (ed - 1) / k must be a whole number
3. If we get $\phi$(n) as a whole number,  we can check if it is indeed the correct $\phi$(n) by: \
$\phi$(n) = (p - 1) * (q - 1) = n - (p + q) + 1 \
p + q = n - $\phi$(n) + 1 \
Consider a quadratic equation : 
    (x - p) (x - q) = 0 <br>
    ${x}^2$ - (p + q) + pq = 0 <br> 
    ${x}^2$ - (n - $\phi$(n) + 1) + n = 0 <br> 
If this equation has integral roots, then the $\phi$(n) is correct.<br>

Ref : https://www.youtube.com/watch?v=OpPrrndyYNU

### Fermat factoring algorithm


The algorithm is based upon the being able to factor the difference of 2 squares


>n = ${x}^2$ - ${y}^2$  <br>
 n = (x - y) / (x + y)  <br>
 And we know that every positive odd integer can be written as the difference of two squares.<br><br>
For n = pq <br>
    n = ${(\frac{p + q}{2})} ^2$  - ${(\frac{p - q}{2})} ^2$ <br><br>
Let k be the smallest positive integer so that k > $\sqrt n$ \
Consider ${k}^2$ - n, <br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
if it is a perfect square i.e. <br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
   n = (k + h) * (k - h) <br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
else: <br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
      k = k + 1 <br>
Eventually we will find an h such that ${k + h}^2$ - n can be factored because: <br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
    ${\frac{n + 1}{2}^2}$ - n = ${\frac{n - 1}{2}^2}$	 <br><br>
Fermat’s factorization algorithm works well if the factors are roughly the ${\bf same \ size.}$ (p and q are close together) 


### Hastads Broadcasting Attack



>c_1 = $m^{e}$ mod N1 <br>
c_2 = $m^{e}$ mod N2 <br>
c_3 = $m^{e}$ mod N3 <br><br>
Given GCD(N_i, N_j) = 1   <br>
c = c1 mod N1 <br>
c = c2 mod N2 <br>
c = c3 mod N3 <br><br>
Using CRT, we can find c <br>
c = $m^e$ mod n1 * n2 * n3 <br><br>
$\therefore$  m =  $\sqrt[e]{c}$ 


Ref: https://www.youtube.com/watch?v=DKWnvyCsh9A

## Number Theory

### Fermat Little Theorem

if gcd(a, p) = 1, p is a prime number and a is an integer <br> 
        ${a}^{p - 1}$ = 1 mod p

We considering the first p - 1 positive multiples of a <br>

        a , 2a , 3a , ... , (p - l)a  <br>

None of these numbers is congruent modulo p to any other nor is any congruent to zero. Because it it happened, <br>			
ra $\cong$ sa mod(p)   where 1 <= r < s <= p - 1

then a could be canceled to give r = s (mod p), which is impossible. <br>
    
        ra - sa = kp
        a(r - s) = kp   
        and p is prime.
    
$\therefore$ the previous set of integers must be congruent modulo 1, 2 , 3 , ... , p - 1

Multiplying,
    a· 2a · 3a · · · (p - l)a = 1 · 2 · 3 · · · (p - 1) (mod p) <br>
    ${a}^{p - 1}$ = 1 mod p 


### Chinese Remainder Theorem

    Let n1, n2, ... , nr be positive integers such that gcd(ni, nj) = 1 for i != j
		
        x = a1 (mod n1)
		x = a2 (mod n2)
		...
		...
		x = ar (mod nr)

	Then this has a simultaneous solution, which is unique modulo the integer n1n2...nr

	Proof(Intuition):
		Let N = n1*n2....*nr

		And Nk = N / nk

		Then  x = a1*N1*x1 + a2*N2*x2 .......... + ar*Nr*xr
		 is a simultaneous solution for this system.

		 Observe: Ni = 0 mod(nk) because nk divides Ni (As Ni = N/ni )

### Euler Theorem


if n > 1 and gcd(a, n) = 1 
\begin{equation}
a^{\phi (n)} = 1 \ mod \ n
\end{equation}



    

### Extended Euclidean Algorithm:

    Extended Euclidean algorithm also finds integer coefficients x and y such that:
    ax + by = gcd(a, b) 
    ...

### Other
1. Let p, q be prime and p != q
    
    if a $\cong$ M mod(p) and a $\cong$ M mod(q)
    
    then a $\cong$ M mod(p $\times$ q)


2. If p and q are distinct primes with $a^p$ = a mod(p) and $a^q$ = a mod(p) 
    
    then $a^{pq}$ = a (mod pq)


3. The linear congruence ax $\cong$ b (mod n) has a solution if and only if d divides b,

   where d = gcd(a, n). If d divides b, then it has d mutually incongruent solutions modulo n.


4. Wilson Theorem: 

    If p is a prime, then (p - 1)! $\cong$ -1 (mod p ).

## PRNG

 ### Linear Congruential Generators
 Link : https://tailcall.net/blog/cracking-randomness-lcgs/


```python
### Implementation

class prng_lcg:
    m = 672257317069504227  # the "multiplier"
    c = 7382843889490547368  # the "increment"
    n = 9223372036854775783  # the "modulus"

    def __init__(self, seed):
        self.state = seed  # the "seed"

    def next(self):
        self.state = (self.state * self.m + self.c) % self.n
        return self.state


def test():
    gen = prng_lcg(123)  # seed = 123
    print (gen.next())  # generate first value
    print (gen.next())  # generate second value
    print (gen.next())  # generate third value


```


```python
# Attacks
## unknown increment 

def crack_unknown_increment(states, modulus, multiplier):
    increment = (states[1] - states[0]*multiplier) % modulus
    return modulus, multiplier, increment

## unknown increment and multiplier

def crack_unknown_multiplier(states, modulus):
    multiplier = (states[2] - states[1]) * modinv(states[1] - states[0], modulus) % modulus
    return crack_unknown_increment(states, modulus, multiplier)

## crack_unknown_modulus

def crack_unknown_modulus(states):
    diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
    zeroes = [t2*t0 - t1*t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
    modulus = abs(reduce(gcd, zeroes))
    return crack_unknown_multiplier(states, modulus)
```

0fd27d3793234e76331b41a57caa0230a65c1964
ipynb
Jupyter Notebook
Crypto.ipynb
Shreyansh7499/MyCrypto
4577b6d2c3136a0e9820cf0f0973ee2a56121834
MIT
Crypto.ipynb
Shreyansh7499/MyCrypto
4577b6d2c3136a0e9820cf0f0973ee2a56121834
MIT
Crypto.ipynb
Shreyansh7499/MyCrypto
4577b6d2c3136a0e9820cf0f0973ee2a56121834
MIT
Qwen/Qwen-72B
1. YES
2. YES