Forum de mathématiques - Bibm@th.net

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))")