Forum de mathématiques - Bibm@th.net

Barbichu

Membre actif

Inscription : 15-12-2007

Messages : 405

[Python] déchiffrement "interactif" pour le secret de freddy et yoshi

Bonsoir,

Voici mon premier jet de code qui marche pour résoudre le problème énoncé ici : le secret de freddy et yoshi.
Ce programme se veut interactif : on entre une solution partielle, le programme la complète, on devine des lettres et ainsi de suite.

Toutefois, je n'ai pas fait de boucle d'interaction, je conseille l'usage de ipython.
Une fois ipython lancé dans le bon dossier, faites, par exemple,

run code.py
process(example, \"de freddy a yoshi\", range(2,100))
 

où code.py est le nom du fichier sous lequel vous aurez sauvé mon code.

Les deux fonctions principales sont decipher et process. La première donne la liste des tailles de clés possible et les solutions associée (mais sous formes numériques, donc illisibles). La deuxième ne donne que les solutions possibles.

debug_level = True

def debug (msg):
    if debug: print(msg)

example  = "HSELO CLTNT LANYR OVCRC LUTOU SDLOI QOCSE TLROO OOIET VOIRO ESSOT"
example += "SOAMT ENOIE AEMTU CLURE PQEIE AETAE ETEET NOOPN EBNSC RIFOR TEERT"
example += "UIIDN IMIIR DMETO EXIDO UDNYN ORFSN DLNUN RIOSA NEEEC EPIEI ETMIU"
example += "ESEIN SIFNI SINPE VOAER GTRAE PIEEA IPVBS SRCII LNIUI FOROS ALTAB"
example += "UNNRS NDENE NSOSE IEEEN RFBTN LSRST AT"

def dfs (init, next):
    """ dfs algorithm for *trees*
    init is the intial node
    next(x) returns the list of nodes that are the children of x and some selected nodes
    """
    stack = [init]
    # explored = set(init)
    result = []
    while len(stack) > 0:
        elt = stack.pop()
        (nexts, r) = next(elt)
        result += r
        for s in nexts:
            # if s not in explored:
            #     explored.add(s)
            stack.append(s)
    return result

ordA = lambda c: ord(c) - ord("A")
chrA = lambda i: chr(i + ord("A"))

def debug_letters (l):
    for i in range(26):
        if len(l[i]) > 0:
            debug("%s : %s" % (chrA(i), l[i]))

def decipher (ciphertext, message, defaultks = []):
    # pretreatment of the ciphertext
    ciphertext = "".join(ciphertext.upper().split())
    csize = len(ciphertext)
    # indexing letters of the ciphertext
    letter = []
    for _ in range(26): letter.append(set())
    for i in range(csize): letter[ordA(ciphertext[i])].add(i)

    debug_letters(letter)

    # pretreatment of message
    message = "".join(message.upper().split())
    message += "_" * (csize - len(message))
    message = message[0:csize]

    # we view the dicypherring as a dfs on the following tree:
    # each node is a state consisting of:
    # + the next position in the cleartext message
    # + the list of the indexes in the ciphertext of the first
    #   element of each row of the cleartext
    # + the set of possible key size
    # there is a vertext between A and B if B is a possible refinement of B

    ks = frozenset(range(2, csize + 1)) # possible key sizes
    if len(defaultks) > 0: ks = ks.intersection(defaultks)

    bounds = [(0,0)] # memoisation of rectangles bounds
    for k in range(1, csize + 1):
        bounds.append((csize / k, csize % k))
   
    debug ("bounds memo : %s" % bounds)

    def next (state):
        (p, prev_perm, prev_ks) = state

        if p >= csize:
            return ([], [state])

        c = message[p] # c is the next constraint
        if c == "_": # if c is unknown, do not perturb
            return ([(p+1, prev_perm + (-1,), prev_ks)], [])

        nextstates = []
        debug("retained keys : %s" % (prev_ks))
        debug("letter %s, position %s, with perm %s" % (c, p, prev_perm))
        for q in letter[ordA(c)]:
            debug("  (letter %s) at %s" % (c, q))
            if q in prev_perm: continue
            perm = prev_perm + (q,)
            ks = set(prev_ks)
            for k in prev_ks:
                (n, d) = bounds[k]
                (ip, jp) = (p / k, p % k)
                (u, v) = (0, 0)
                if jp <= d + 1: u = 1
                if jp == d + 1: v = 1

                # special case of first character: it must be on the first line of the cleartext
                if (q == 0 and ip != 0) or (jp == k - 1 and 0 not in perm):
                    ks.remove(k)
                    continue

                # kperm indexes (by its position in the ciphertext)
                # the first elements of each column of the cleartext
                kperm = list(perm)[0:k]
                conflict = False
                for r in range(p + 1):
                    (ir, jr) = (r / k, r % k)
                    if kperm[jr] >= 0:
                        if perm[r] >= 0 and kperm[jr] + ir != perm[r]:
                            conflict = True
                            break
                    else: kperm[jr] = perm[r] - ir
                if conflict:
                    ks.remove(k)
                    continue
               
                pos = filter(lambda x: x >= 0, kperm)
                pos.sort()
                if 0 not in pos: pos = [0] + pos
                holes = k - len(pos) # number of unknown positions left
                irreg = d # number of irregularities left

                pos.append(csize)
                for x in range(len(pos) - 1):
                    diff = pos[x + 1] - pos[x]
                    diffh = diff / n
                    diffi = diff % n
                    if diffh == 0:
                        ks.remove(k)
                        break
                    if pos[x] in kperm:
                        if kperm.index(pos[x]) < d:
                            if diffi == 0 or (jp >= d and diffi > 1):
                                ks.remove(k)
                                break
                    holes -= (diffh - 1)
                    irreg -= diffi
                    if holes < 0 or irreg < 0:
                        ks.remove(k)
                        break

            if len(ks) > 0:
                nextstates.append((p + 1, perm, (frozenset(ks))))

        return (nextstates, [])

    result = dfs((0, tuple(), ks), next)

    return result

def cleartext (state, ciphertext):
    # pretreatment of the ciphertext
    ciphertext = "".join(ciphertext.upper().split())
    csize = len(ciphertext)
    (p, perm, ks) = state
    results = []
    for k in ks:
        (n, d) = (csize / k, csize % k)
        result = ["_"] * csize
        ok = True
        for j in range(k):
            u = 0
            if j < d: u = 1
            kperm = list(perm)
            for i in range(n + u):
                if kperm[i * k + j] >= 0:
                    kperm[j] = kperm[i * k + j] - i
                    break
            if kperm[j] >= 0:
                for i in range(n + u):
                    result[i * k + j] = ciphertext[kperm[j] + i]
        if ok: results.append("".join(result))
    return results

def process (ciphertext, message, ks = []):
    result = decipher(ciphertext, message, ks)
    return map (lambda s: cleartext(s, example), result)

if __name__ == '__main__':
    debug("main")
    debug("for example, run method process on the example:")
    debug("process(example, \"de freddy a yoshi\", range(2,100))")
 

A+

Dernière modification par Barbichu (30-01-2013 20:05:58)