~shreyasminocha/comp323

Implementations of stuff from COMP 323

62a9fbd Replace Int with Integer

6 months ago

fa361b7 Implement knapsack and GGH

7 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
#Quadratic Sieve
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

#License

See LICENSE.

The software is provided "as is", without warranty of any kind, express or implied, including but not limited to the warranties of merchantability, fitness for a particular purpose and noninfringement.