Standford Cryptography courses online - homeworks

week1.py

'''
    Question 1
    Many Time Pad 

Let us see what goes wrong when a stream cipher key is used more than once. Below are eleven 
hex-encoded ciphertexts  that are the result  of encrypting eleven plaintexts  with a stream 
cipher,  all  with the same stream cipher key.  Your goal is to decrypt  the last ciphertext, 
and submit the secret message within it as solution. 

Hint:   XOR the ciphertexts together,  and consider what happens  when a space is XORed with 
a character in [a-zA-Z]. 
'''

cts = [
'315c4eeaa8b5f8aaf9174145bf43e1784b8fa00dc71d885a804e5ee9fa40b16349c146fb778cdf2d3aff021dfff5b403b510d0d0455468aeb98622b137dae857553ccd8883a7bc37520e06e515d22c954eba5025b8cc57ee59418ce7dc6bc41556bdb36bbca3e8774301fbcaa3b83b220809560987815f65286764703de0f3d524400a19b159610b11ef3e',
'234c02ecbbfbafa3ed18510abd11fa724fcda2018a1a8342cf064bbde548b12b07df44ba7191d9606ef4081ffde5ad46a5069d9f7f543bedb9c861bf29c7e205132eda9382b0bc2c5c4b45f919cf3a9f1cb74151f6d551f4480c82b2cb24cc5b028aa76eb7b4ab24171ab3cdadb8356f',
'32510ba9a7b2bba9b8005d43a304b5714cc0bb0c8a34884dd91304b8ad40b62b07df44ba6e9d8a2368e51d04e0e7b207b70b9b8261112bacb6c866a232dfe257527dc29398f5f3251a0d47e503c66e935de81230b59b7afb5f41afa8d661cb',
'32510ba9aab2a8a4fd06414fb517b5605cc0aa0dc91a8908c2064ba8ad5ea06a029056f47a8ad3306ef5021eafe1ac01a81197847a5c68a1b78769a37bc8f4575432c198ccb4ef63590256e305cd3a9544ee4160ead45aef520489e7da7d835402bca670bda8eb775200b8dabbba246b130f040d8ec6447e2c767f3d30ed81ea2e4c1404e1315a1010e7229be6636aaa',
'3f561ba9adb4b6ebec54424ba317b564418fac0dd35f8c08d31a1fe9e24fe56808c213f17c81d9607cee021dafe1e001b21ade877a5e68bea88d61b93ac5ee0d562e8e9582f5ef375f0a4ae20ed86e935de81230b59b73fb4302cd95d770c65b40aaa065f2a5e33a5a0bb5dcaba43722130f042f8ec85b7c2070',
'32510bfbacfbb9befd54415da243e1695ecabd58c519cd4bd2061bbde24eb76a19d84aba34d8de287be84d07e7e9a30ee714979c7e1123a8bd9822a33ecaf512472e8e8f8db3f9635c1949e640c621854eba0d79eccf52ff111284b4cc61d11902aebc66f2b2e436434eacc0aba938220b084800c2ca4e693522643573b2c4ce35050b0cf774201f0fe52ac9f26d71b6cf61a711cc229f77ace7aa88a2f19983122b11be87a59c355d25f8e4',
'32510bfbacfbb9befd54415da243e1695ecabd58c519cd4bd90f1fa6ea5ba47b01c909ba7696cf606ef40c04afe1ac0aa8148dd066592ded9f8774b529c7ea125d298e8883f5e9305f4b44f915cb2bd05af51373fd9b4af511039fa2d96f83414aaaf261bda2e97b170fb5cce2a53e675c154c0d9681596934777e2275b381ce2e40582afe67650b13e72287ff2270abcf73bb028932836fbdecfecee0a3b894473c1bbeb6b4913a536ce4f9b13f1efff71ea313c8661dd9a4ce',
'315c4eeaa8b5f8bffd11155ea506b56041c6a00c8a08854dd21a4bbde54ce56801d943ba708b8a3574f40c00fff9e00fa1439fd0654327a3bfc860b92f89ee04132ecb9298f5fd2d5e4b45e40ecc3b9d59e9417df7c95bba410e9aa2ca24c5474da2f276baa3ac325918b2daada43d6712150441c2e04f6565517f317da9d3',
'271946f9bbb2aeadec111841a81abc300ecaa01bd8069d5cc91005e9fe4aad6e04d513e96d99de2569bc5e50eeeca709b50a8a987f4264edb6896fb537d0a716132ddc938fb0f836480e06ed0fcd6e9759f40462f9cf57f4564186a2c1778f1543efa270bda5e933421cbe88a4a52222190f471e9bd15f652b653b7071aec59a2705081ffe72651d08f822c9ed6d76e48b63ab15d0208573a7eef027',
'466d06ece998b7a2fb1d464fed2ced7641ddaa3cc31c9941cf110abbf409ed39598005b3399ccfafb61d0315fca0a314be138a9f32503bedac8067f03adbf3575c3b8edc9ba7f537530541ab0f9f3cd04ff50d66f1d559ba520e89a2cb2a83',
]

target = '32510ba9babebbbefd001547a810e67149caee11d945cd7fc81a05e9f85aac650e9052ba6a8cd8257bf14d13e6f0a803b54fde9e77472dbff89d71b57bddef121336cb85ccb8f3315f4b52e301d16e9f52f904'

"""
The key is
'f9n\x89\xc9\xdb\xd8\xcc\x98t5*\xcdc\x95\x10.\xaf\xcex\xaa\x7f\xed(\xa0\x7fk\xc9\x8d)\xc5
\x0bi\xb03\x9a\x19\xf8\xaa@\x1a\x9cmp\x8f\x80\xc0f\xc7c\xfe\xf0\x121H\xcd\xd8\xe8\x02\xd0
[\xa9\x87w3]\xae\xfc\xec\xd5\x9cC:k&\x8b`\xbfN\xf0<\x9aa'

"""

def strxor(a, b):     # xor two strings of different lengths
    if len(a) > len(b):
        return "".join([chr(ord(x) ^ ord(y)) for (x, y) in zip(a[:len(b)], b)])
    else:
        return "".join([chr(ord(x) ^ ord(y)) for (x, y) in zip(a, b[:len(a)])])

def random(size=16):
    return open("/dev/urandom").read(size)

def encrypt(key, msg):
    c = strxor(key, msg)
    print
    print c.encode('hex')
    return c

def get_key_from_col(col):
    max_conflicts = 0
    suspected = '\x00'
    for c in col:
        conflicts = 0
        for cc in col:
            if 0x3f < (ord(c) ^ ord(cc)): # letters are nice to each other 
                conflicts += 1
        if conflicts > max_conflicts: 
            max_conflicts = conflicts
            suspected = c
    
    if max_conflicts < 6: return '\x00'
    return chr( 0x20 ^ ord(suspected) )

def get_col(cts, i):
    col = ''
    for c in cts: col += c[i*2 : (i+1)*2].decode('hex')
    return col

def get_key(cts, l):
    key = ''
    for i in range(l/2):
        col = get_col(cts, i)
        k = get_key_from_col(col)
        if k == '\x00': print '%ith seems not to be decoded' % i
        key += k
    return key

def decipher(s, k):
    return strxor(s.decode('hex'), k)

def correct_key(k, in_cts_num, at_pos, right_letter_is):
    def strsetat(s, pos, c):
        return s[0:pos] + c + s[pos+1:]
    
    col = get_col(cts, at_pos)
    corrected = ord(col[in_cts_num]) ^ ord(right_letter_is)

    return strsetat(k, at_pos, chr(corrected))

if __name__ == '__main__':
    pass

week2.py

import Crypto.Cipher.AES as AES


### Data
cbckey1 = '140b41b22a29beb4061bda66b6747e14'
cbcct1 = '4ca00ff4c898d61e1edbf1800618fb2828a226d160dad07883d04e008a7897ee2e4b7465d5290d0c0e6c6822236e1daafb94ffe0c5da05d9476be028ad7c1d81'

cbckey2 = '140b41b22a29beb4061bda66b6747e14'
cbcct2 = '5b68629feb8606f9a6667670b75b38a5b4832d0f26e1ab7da33249de7d4afc48e713ac646ace36e872ad5fb8a512428a6e21364b0c374df45503473c5242a253'

ctrkey1 = '36f18357be4dbd77f050515c73fcf9f2'
ctrct1 = '69dda8455c7dd4254bf353b773304eec0ec7702330098ce7f7520d1cbbb20fc388d1b0adb5054dbd7370849dbf0b88d393f252e764f1f5f7ad97ef79d59ce29f5f51eeca32eabedd9afa9329'

ctrkey2 = '36f18357be4dbd77f050515c73fcf9f2'
ctrct2 = '770b80259ec33beb2561358a9f2dc617e46218c0a53cbeca695ae45faa8952aa0e311bde9d4e01726d3184c34451'

### Homework:

ckey1 = cbckey1.decode('hex')
ct1 = cbcct1.decode('hex')

ckey2 = cbckey2.decode('hex')
ct2 = cbcct2.decode('hex')

tk1 = ctrkey1.decode('hex')
tct1 = ctrct1.decode('hex')

tk2 = ctrkey2.decode('hex')
tct2 = ctrct2.decode('hex')

def strxor(s1, s2):
    return ''.join([ chr(ord(c1) ^ ord(c2)) for (c1, c2) in zip(s1, s2)])


class BlockAES:
    def __init__(self, key):
        self.key = key
        self.bs = 16
        self.aes = AES.new(key)
    
    def split_msg(self, msg):
        ms = [ msg[ self.bs*i : self.bs*(i+1) ] for i in range(len(msg)/self.bs + 1) ]
        while ms.count(''): ms.remove('')
        return ms

class CBC(BlockAES):
    def decrypt(self, msg):
        ms = self.split_msg(msg)
        pt = ''
        for i in xrange(len(ms) - 1, 0, -1):
            pt = strxor(ms[i - 1], self.aes.decrypt(ms[i])) + pt
        return pt

class CTR(BlockAES):
    def decrypt(self, msg):
        ms = self.split_msg(msg)
        pt = ''
        iv = ms[0]
        for b in ms[1:]:
            pt += strxor(self.aes.encrypt(iv), b)
            iv = iv[:-1] + chr(1 + ord(iv[-1]))
        return pt

if __name__ == '__main__':
    print CBC(ckey1).decrypt(ct1)
    print CBC(ckey2).decrypt(ct2)
    print CTR(tk1).decrypt(tct1)
    print CTR(tk2).decrypt(tct2)

week4.py

#! /usr/bin/env python

import urllib2
import sys
from time import sleep

def strxor(s1, s2):
    return "".join([ chr(ord(c2) ^ ord(c1)) for (c1, c2) in zip(s1, s2)])

def strrep(s, sub, pos):
    endpos = pos + len(sub)
    return s[:pos] + sub + s[endpos:]

TARGET = 'http://crypto-class.appspot.com/po?er='
#--------------------------------------------------------------
# padding oracle
#--------------------------------------------------------------
class PaddingOracle(object):
    def query(self, q):
        target = TARGET + urllib2.quote(q)    # Create query URL
        req = urllib2.Request(target)         # Send HTTP request to server
        try:
            f = urllib2.urlopen(req)          # Wait for response
        except urllib2.HTTPError, e:
            return e.code
        return 200

start_query='f20bdba6ff29eed7b046d1df9fb7000058b1ffb4210a580f748b4ac714c001bd4a61044426fb515dad3f21f18aa577c0bdf302936266926ff37dbf7035d5eeb4'.decode('hex')

def try_byte(query, byte_at, pad):
    po = PaddingOracle()
    g200 = None

    def try_guess(g):
        sleep(0.1)
        g200 = 0
        last = query[byte_at]
        last = chr(ord(last) ^ pad ^ g)
        q = strrep(query, last, byte_at)
        http_status = po.query(q.encode('hex'))
        if http_status == 404:
            print "Good padding found: 0x%02x" % g
            return g
        if http_status == 200:
            g200 = g
        # if http_status not in (200, 403):
        print "  0x%02x failed (%d)..." % (g, http_status)
        return g200

    if try_guess(0x09): return 0x09
    if try_guess(0x20): return 0x20

    for i in xrange(0x7f, 0x00, -1):
        if try_guess(i): return i

    for i in xrange(0x80, 0xFF):
        if try_guess(i): return i

    if g200: print "Assuming: 0x%02x" % g200
    else: print 'Failed to guess query[%d]' % byte_at
    return g200

def oracle_byte_s(query, guess, start, end):
    for i in xrange(end - 1 - len(guess), start - 1, -1):
        print 'Guessing query[%d]' % i
        padlen = end - i
        subst = strxor(strxor(query[i+1:end], guess), chr(padlen) * padlen)
        q = strrep(query, subst, i+1)
        g = try_byte(q, i, padlen)
        if g is None:
            print '  Failed.'
            return None
        guess = chr(g) + guess
    return guess

def oracle_bytes(query, start, end):
    return oracle_byte_s(query, '', start, end)

if __name__ == "__main__":
    s3 = oracle_bytes(start_query, 32, 48)
    s2 = oracle_bytes(start_query[:48], 16, 32)
    s1 = oracle_bytes(start_query[:32], 0, 16)
    print s1 + s2 + s3

week5a.hs

module Main where

import qualified Data.Map as M
import qualified Algebra.IntegralDomain as AID
import Math.NumberTheory.Moduli as Mod
-- import Number.Modulo
import Data.Maybe (isJust, fromMaybe)
import System.Environment (getArgs)

{-
 - The task is to find x (in [0..2^40]) such that h = g ^ x in a ring with base p
 -  Here Meet-in-the-Middle computation is used (b = 2^20):
 -  Since
 -      x = x0 * b + x1
 -      h / g ^ x0 = (g ^ b) ^ x1
 -  where we build a hashmap for left 2^20 values and then lookup right value for the x1
 -
 -  Note: Do not use (`modulo` p) operations from Number.Modulo, they're as slow as hell
 -}

p, g, h :: Integer

p = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171
g = 11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568
h = 3239475104050450443565264378728065788649097520952449527834792452971981976143292558073856937958553180532878928001494706097394108577585732452307673444020333

b, gB :: Integer
b = 2 ^ 20

gB = Mod.powerMod g b p

buildMap :: Integer -> M.Map Integer Integer
buildMap b = M.fromList $ label toRight [0..b]

label :: (a -> b) -> [a] -> [(b, a)]
label f = map (\x -> (f x, x))

toRight :: Integer -> Integer
toRight x0 = Mod.powerMod gB x0 p

toLeft :: Integer -> Integer
toLeft x1 = let gx = Mod.powerMod g x1 p in
            (AID.div (fromInteger h :: Mod Integer)
                     (fromInteger gx :: Mod Integer)) `modulo` p


isJustInteger :: Maybe Integer -> Bool
isJustInteger = isJust

fst3 :: (a, b, c) -> a
fst3 (a, _, _) = a

getMatch' :: M.Map Integer Integer -> (Integer, Integer) -> [(Bool, Integer, Integer)]
getMatch' m (a, b) =
    filter fst3 $ flip map [a..b] (\x1 ->
        let x0 = M.lookup (toLeft x1) m in
        ((isJustInteger x0), (fromMaybe 0 x0), x1))

getMatch :: Integer -> Maybe (Integer, Integer)
getMatch b = let theMap = buildMap b in
             case getMatch' theMap (0, b) of
                [] -> Nothing
                ((True, x0, x1):_) -> Just (x0, x1)
                ((False, _, _):_) -> error "WTF?"

main :: IO ()
main = forkedMain

forkedMain = do
    (a1:ai:an:_) <- getArgs
    bp <- return ( (read a1) :: Integer )    -- power of 2 of the space
    i <- return ( (read ai) :: Integer )        -- number of instance
    n <- return ( (read an) :: Integer )        -- general count of processors 
    b <- return $ 2^bp
    start <- return $ (b * i) `div` n
    end <- return $ (b * (i + 1)) `div` n
    case getMatch' (buildMap b) (start, end) of
        [] -> print "Nothing"
        ((True, x0, x1):_) -> print $ "Just " ++ show x0 ++ ", " ++ show x1
        ((False, _, _):_) -> error "WTF?"

singleMain = do
    (a1:_) <- getArgs
    b <- return ( (read a1) :: Integer )
    print b
    print $ getMatch (2^b)

week6.hs

import Math.NumberTheory.Powers as NP
import Math.NumberTheory.Moduli as NM
import Algebra.IntegralDomain as AID
import Number.Modulo
import Data.Maybe
import Data.List
import Data.Bits
import Data.Char

n1, n2, n3 :: Integer

n1 = 179769313486231590772930519078902473361797697894230657273430081157732675805505620686985379449212982959585501387537164015710139858647833778606925583497541085196591615128057575940752635007475935288710823649949940771895617054361149474865046711015101563940680527540071584560878577663743040086340742855278549092581

n2 = 648455842808071669662824265346772278726343720706976263060439070378797308618081116462714015276061417569195587321840254520655424906719892428844841839353281972988531310511738648965962582821502504990264452100885281673303711142296421027840289307657458645233683357077834689715838646088239640236866252211790085787877

n3 = 720062263747350425279564435525583738338084451473999841826653057981916355690188337790423408664187663938485175264994017897083524079135686877441155132015188279331812309091996246361896836573643119174094961348524639707885238799396839230364676670221627018353299443241192173812729276147530748597302192751375739387929

ct = 22096451867410381776306561134883418017410069787892831071731839143676135600120538004282329650473509424343946219751512256465839967942889460764542040581564748988013734864120452325229320176487916666402997509188729971690526083222067771600019329260870009579993724077458967773697817571267229951148662959627934791540
e = 65537

factorWithA :: Integer -> Integer -> Maybe (Integer, Integer)
factorWithA n a = do
    x <- NP.exactSquareRoot( a * a - n )
    return (a - x, a + x)

-- |p-q| < 2N^0.25 =>  A - sqrt(N) < 1 => the single value of x
factorIfLT2NtoFth :: Integer -> Maybe (Integer, Integer)
factorIfLT2NtoFth n = factorWithA n (1 + NP.integerSquareRoot n)

sqr x = x * x
dec x = x - 1

-- listToMaybe :: [a] -> Maybe a
-- listToMaybe []      = Nothing
-- listToMaybe (x:_)   = Just x

toString :: Integer -> String
toString n = map (chr.fromInteger) $ reverse $ map (.&. 0xff) $ takeWhile (/= 0) $ iterate (`shiftR` 8) n

-- |p-q| < 2^11 N^0.25 => A - sqrt(N) < 2^20, scan for A upwards from sqrt(N), until factoring succeed
factorIfLT2to11byNto4th :: Integer -> Maybe (Integer, Integer)
factorIfLT2to11byNto4th n =
    listToMaybe $ catMaybes $ map (factorWithA n) [as..ae]
    where as = (1 + NP.integerSquareRoot n)
          ae = as + 2 ^ 20

decipherRSA :: (Integer, Integer) -> Integer -> Integer -> String
decipherRSA (p, q) e ct =
    let n = p * q
        phi = (p-1) * (q-1)
        d = AID.div (fromInteger 1) (fromInteger e) `modulo` phi
    in toString (NM.powerMod ct d n)

main :: IO()
main = do
    let (p,q) = fromJust $ factorIfLT2NtoFth n1
    print p
    let (p1, _) = fromJust $ factorIfLT2to11byNto4th n2
    print p1
    let pt = decipherRSA (p,q) e ct
    print pt

I used http://www.codeskulptor.org/ to code but it has problem in random(1024)

hellp me