## ~shreyasminocha/comp323

Implementations of stuff from COMP 323

62a9fbd `Replace Int with Integer`

1 year, 4 months ago

fa361b7 `Implement knapsack and GGH`

1 year, 4 months ago

## #COMP 323 (Intro to Math Cryptography)

Disclaimer: Something something educational purposes only. Don't use these for anything serious lol.

### #Elementary Ciphers

#### #Caesar

```echo 'Foo' | ./caesar 5
echo 'Foo' | ./caesar 5 | ./caesar -5
./caesar 13 < caesar.hs
```

#### #Atbash

```echo 'Foo' | ./atbash
echo 'Foo' | ./atbash | ./atbash
./atbash < atbash.hs
```

#### #Vigenère

```echo 'Yellow' | ./vigenere 'dog'
./vigenere 'foo' < vigenere.hs
```

#### #Playfair

```echo 'meet me at noon' | ./playfair 'abcdefghiklmnopqrstuvwxyz'
```

Where `abcdefghiklmnopqrstuvwxyz` corresponds to the key:

``````abcde
fghik
lmnop
qrstu
vwxyz
``````

Caveats:

• Strips all non-alpha characters
• Works only with lowercase letters and keys

#### #Autokey

```echo 'theautokeycipheriscool' | ./autokey 'random'
```

Caveats:

• Strips all non-alpha characters

### #Math

#### #Extended Euclidean Algorithm

```egcd 10 15 -- (5,-1,1)
```

#### #Linear Congruences

```inverse 2035800 103 -- 810367
baseSolution 7 1 5 -- 3
solutions 98 60 34 -- [45,94]
```

#### #Chinese Remainder Theorem

```crt [(2, 3), (3, 5), (2, 7)] -- 23
```

### #Public-Key Cryptography

#### #RSA

```(p, q) = (1301, 1567)
(n, e) = (p * q, 103)

m = 892383
c = rsaEncrypt (n, e) m

m' = rsaDecrypt (n, inverse ((p - 1) * (q - 1)) e) c
m == m' -- True
```

#### #Diffie-Hellman

```(p, g) = (941, 627)

a = 347
a' = dhPersonalPublic (p, g) a

b = 781
b' = dhPersonalPublic (p, g) b

dhSharedSecret (p, g) a b' == dhSharedSecret (p, g) b a' -- True
```

### #Code Breaking

#### #Pohlig-Hellman

```pohligHellman 746497 10 243278 -- 223755
powMod 746497 10 223755 -- 243278
```

#### #Shanks' Algorithm

```python shanks.py 650 2213 3571 # 319
```

#### #Factorization

##### #Miller-Rabin
```isWitness 561 2 -- True
```
##### #Difference of Squares
```factorize 53357 -- (233,229)
factorizeWithK 1226987 3 36 -- (653,1879)
```
##### #Pollard's `p - 1` method
```factorize 220459 2 -- 449
```
##### #Smooth Numbers
```isSmooth 10 84 -- True
isPowerSmooth 10 84 -- True
```
```quadraticSieve 493 11 [23..38] -- [(23,36),(25,132)]
```

### #Elliptic Curves

```ecdlpBruteforce (73, (8, 7)) (32, 53) (39, 17) -- 11
scalePoint (3623, (14, 19)) (6, 730) 947 -- (3492,60)
```
```pc = (3851, (324, 1287))
p = (920, 303)

ecdhPersonalPublic pc p 1194 -- (2067,2178)
ecdhPersonalPublic pc p 1759 -- (3684,3125)

ecdhSharedSecret pc 1194 (3684, 3125) -- (3347,1242)
ecdhSharedSecret pc 1759 (2067, 2178) -- (3347,1242)
```

### #Miscellaneous

#### #Fast Powering

```pow 2 10 -- 1024
powMod 43 2 10 -- 35
```