Codificar textos

Durante as aulas introduzimos as cadeias de caracteres. Elas são o modo natural de guardar textos. Uma tarefa relevante é a de codificar um texto de modo que possa ser transmitido com segurança. Vamos ver como a tarefa de encriptar um documento pode ser resolvida com facilidade em Python. Iremos usar três métodos diferentes, que naturalmente vão requerer algoritmos distintos. O primeiro, limita-se a separar o texto em duas partes em função da posição par ou ímpar do caractere no texto. Uma vez esta decomposição feita o texto é recomposto juntando as duas partes. O segundo método precisa conhecer o alfabeto usado e estabelece uma correspondência entre cada caractere do alfabeto e um outro caractere do mesmo alfabeto que se encontra n posições à sua frente. Finalmente o terceiro método usa uma correspondência entre caracteres não baseada num distância fixa mas antes definida estocasticamente. Vejamos então algumas soluções possíveis.

Separação pares ímpares

Comecemos com um pedaço de código que deixa claro qual a estratégia a seguir.

def encripta_0(texto):
    # selecciona pares
    # selecciona ímpares
    # junta pares e ímpares
    pass

Olhemos agora para cada um dos sub-problemas. Como extrair os caracteres que se encontram nas posições pares do texto. Não é preciso pensar muito para decidir que podemos recorrer ao modelo baseado na ideia de ciclo + acumulador:

def encripta_0(texto):
    # selecciona pares
    pares = ''
    for i in range(len(texto)):
        # índice par?
        if i%2 == 0:
            pares = pares + texto[i]
    # selecciona ímpares
    # junta pares e ímpares
    pass

Resolver o problema para os mares é semelhante, pelo que chegamos à nossa primeira solução.

def encripta_0(texto):
    # selecciona pares
    pares = ''
    for i in range(len(texto)):
        # índice par?
        if i%2 == 0:
            pares = pares + texto[i]
    # selecciona ímpares
    impares = ''
    for i in range(len(texto)):
        # índice ímpar?
        if i%2 != 0:
            impares = impares + texto[i]    
    # junta pares e ímpares
    novo_texto = pares + impares
    return novo_texto

Porque é que esta solução não nos agrada? Desde logo porque o texto é percorrido duas vezes. Isso decorre do facto de termos isolado a construção dos pares da dos ímpares. Mas é óbvio que podemos fazer a divisão par/ímpar percorrendo o texto uma só vez:

def encripta_1(texto):
    pares = ''
    impares = ''
    for i in range(len(texto)):
        if i % 2 == 0:
            pares = pares + texto[i]
        else:
            impares = impares + texto[i]
    return pares + impares

A solução pode ser ainda outra se usarmos o conhecimento que temos da operação de fatiamento:

def encripta_11(texto):
    pares = texto[0::2]
    impares = texto[1::2]
    return pares + impares

ou ainda, eliminando os nomes auxiliares:

def encripta_12(texto):
    return texto[0::2] + texto[1::2]

Distância Fixa

Nesta abordagem vamos necessitar conhecer o alfabeto, ou seja, os símbolos que podem aparecer no texto. Para simplificar vamos supor que o nosso alfabeto é formado pelas letras minúsculas mais o espaço em branco. O modelo ciclo - acumulador permite um primeiro esboço de solução:

def codifica(texto,n):
    alfabeto = 'abcdefghijklmnopqrstuvwxyz '
    novo_texto = ''
    for car in texto:
        # por cada caractere do texto procura o equivalente n posições “à frente”
        # junta ao acumulador
    return novo_texto

O sub-problema realmente diferente consiste em encontrar o novo caractere. Um ideia básica é usar o seu índice no alfabeto e somar-lhe n. O único problema que pode surgir é com os caracteres no final. Por exemplo, caso n=2 o equivalente a z deve ser o a. Podemos resolver esta questão usando a operação módulo:

def codifica(texto,n):
    alfabeto = 'abcdefghijklmnopqrstuvwxyz '
    novo_texto = ''
    for car in texto:
        novo_indice = (alfabeto.index(car) + n) % len(alfabeto)
        novo_car = alfabeto[novo_indice]
        novo_texto = novo_texto + novo_car
    return novo_texto

É claro que podemos chegar a outra solução. Por exemplo, podemos construir primeiro a correspondência e só depois encriptar.

def codifica_2(texto,n):
    alfabeto = 'abcdefghijklmnopqrstuvxyz '
    # constrói código
    cod_alfabeto = ''
    for car in alfabeto:
        indice = alfabeto.index(car)
        novo_indice = (indice + n) % len(alfabeto)
        cod_alfabeto = cod_alfabeto + alfabeto[novo_indice]
        
    # encripta
    novo_texto = ''
    for car in texto:
        ind = alfabeto.index(car)
        novo_texto = novo_texto + cod_alfabeto[ind]
    return novo_texto

Faz ainda sentido que o alfabeto seja um parâmetro do programa principal:

def codifica_3(texto,alfabeto, n):
    # define chave
    alfa_chave = chave(alfabeto,n)
    # encripta
    novo_texto = ''
    for car in texto:
        ind = alfabeto.index(car)
        novo_texto = novo_texto + alfa_chave[ind]
    return novo_texto

def chave(alfabeto,n):
    alfa_chave = ''
    for car in alfabeto:
        indice = alfabeto.index(car)
        novo_indice = (indice + n) % len(alfabeto)
        alfa_chave = alfa_chave + alfabeto[novo_indice] 
    return chave

Notar que criámos uma definição auxiliar para a construção da chave. Chave Aleatória

A ideia agora é estabelecer uma relação um para um entre o alfabeto e a chave de modo aleatório. Na linha do último exemplo vamos ver como podemos criar a chave. Em Python existem várias formas de o poder fazer, umas bem simples, mas vamos buscar uma solução à luz do que foi dados nas aulas. Vamos então caçar com gato…. A ideia é trivial: gerar uma permutação do alfabeto inicial recorrendo a uma cópia desse alfabeto ao qual vamos buscar aleatoriamente um símbolo para a chave. De seguida esse símbolo é retirado para garantir que geramos uma permutação.

import random

def define_chave(alfabeto):
    simbolos = alfabeto
    chave = ''
    for car in alfabeto:
        novo_simb = random.choice(simbolos)
        ind = simbolos.index(novo_simb)
        simbolos = simbolos[:ind] + simbolos[ind+1:]
        chave = chave + novo_simb    
    return chave

Tendo a chave, a encriptação é semelhante ao exemplo anterior.

def encrita_3(texto, alfabeto):
    chave = define_chave(alfabeto)
    novo_texto = ''
    for car in texto:
        ind = alfabeto.index(car)
        novo_texto = novo_texto + chave[ind]    
    return novo_texto