Chiffrement par substitution

Version imprimable

Bonjour,

Je réalise un TP actuellement sur la substitution par chiffrement, évolution du chiffrement par décalage de César. La substitution fonctionne ainsi: on possède un fichier .txt où se trouve "la clé" qui est composé dans une colonne de l'alphabet dans l'ordre, puis dans l'autre colonne, la lettre qui substitue celle de l'alphabet.
En général, on a ça: AEBKCUDP.... où "A" sera substituté par "E", "B" par "K" et ainsi de suite.

Ensuite, on a un chaîne de caractères stockée dans un string, et le but est d'appliquer la substitution à la chaîne de caractères. Mon intérêt est de passer par un foncteur et des itérateurs, puis plus tard par des algorithmes. Mon code actuel est le suivant, et je bloque clairement sur la substitution, alors que je n'ai pas eu ce problème pour le chiffrement par décalage (même si le dernier est plus simple).
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 #include <iostream> #include <string> #include <iterator> #include <fstream> using namespace std; int main() { // Le message a crypter string texte("TEXTE A TESTER"); // Demande de la cle a l'utilisateur cout << "Quel fichier contenant la cle voulez-vous utiliser ? "; string nomFichier; cin >> nomFichier; ifstream fichier(nomFichier); istream_iterator<char> it(fichier); istream_iterator<char> end; string a; while (it != end) { a.push_back(*it); ++it; } for (int i =0; i < a.size(); i++) { if (i%2 == 0) { a[i] = a[i+1]; } cout << a[i]; } return 0; }
Déjà, j'ai un petit problème aussi avec

Code:

ifstream fichier(nomFichier);

qui n'accepte pas mon string nomFichier. Je comprends pas pourquoi, quand je remplace par le nom du fichier "cle.txt", il n'y a pas de problème, et ifstream est censé recevoir du type string.

Ensuite, ce que j'effectue dans ma boucle for, j'aimerai l'effectuer dans ma boucle while, c'est à dire que je ne souhaite pas passer par du string pour parcourir la chaîne via les index, mais par la boucle while avec l'itérateur.

Dans l'attente de toutes vos réponses, je reste à l'écoute!

21/08/2016, 17h01
Bousk

Hello,

Citation:

Envoyé par alexandrempg

Déjà, j'ai un petit problème aussi avec

Code:

ifstream fichier(nomFichier);

qui n'accepte pas mon string nomFichier.

parce que comme l'indique la doc, le constructeur de ifstream prend un const char*, ce qu'est "cle.txt" et non un std::string.

Pour un tel exercice, j'opterais pour un std::map<char, char> et std::for_each, std::transform ou std::replace.
Il y a aussi une autre méthode dont j'oublie toujours le nom qui permet de faire du push_back à la volée
21/08/2016, 17h12
alexandrempg

Citation:

Envoyé par Bousk

Hello,

parce que comme l'indique la doc, le constructeur de ifstream prend un const char*, ce qu'est "cle.txt" et non un std::string.

J'avais vu ça dans mes erreurs mais je comprenais pas qu'au final le "cle.txt" était de type const char*. Du coup, ce problème ce pallie par cette solution:

Code:

ifstream fichier(nomFichier.c_str());

Citation:

Envoyé par Bousk

Pour un tel exercice, j'opterais pour un std::map<char, char> et std::for_each, std::transform ou std::replace.
Il y a aussi une autre méthode dont j'oublie toujours le nom qui permet de faire du push_back à la volée

Je vais m'intéresser à la map puis je reviendrai si j'ai d'autres éventuelles questions, j'avais hésité à passer par là. Pour ce qui est des algorithmes, c'est bien ceux que j'avais en tête, notamment std::transform().
21/08/2016, 17h32
jo_link_noir
Depuis la norme C++11 (5ans maintenant), ifstream peut prendre un std::string.

@Bousk: emplace_back, également depuis C++11.

@alexandrempg: Utiliser une boucle for pour le parcours d'itérateur est plus idiomatique qu'une boucle while et le risque d'oublier l'incrémentation y est moins fort. l'utilisation d'algorithme simplifie aussi pas mal (cf: std::copy + std::back_inserter), mais dans l'absolu, std::string peut s'initialiser avec 2 itérateurs, un simple
Code:

1 2 3 4 std::string a{ std::istreambuf_iterator<char>{fichier}, std::istreambuf_iterator<char>{} };
est beaucoup plus simple.
21/08/2016, 17h42
Bousk

Citation:

Envoyé par jo_link_noir

@Bousk: emplace_back, également depuis C++11.

Non, je parlais de back_inserter.
21/08/2016, 21h21
zobal
Salut

Je ne vois pas trop l'intérêt de lire le fichier avec un itérateur puisqu'il faut faire un traitement non homogène sur les données. Personnellement, j'aurais écrit :
Code:

1 2 3 4 ifstream fichier("cle.txt"); map<char,char> lut; char cle, valeur; while (fichier >> cle) { if (fichier >> valeur) lut[cle] = valeur; }
Le map est effectivement une bonne idée (ne pas oublier de tester si le caractère est bien dans la map lors de la substitution...). Pour l'algorithme de substitution, je pense que for_each sera le plus simple et le plus efficace.

Bon courage
21/08/2016, 21h55
JolyLoic

La map ne me semble pas une si bonne idée, puisqu'elle va effectuer des recherches en O(ln N) alors qu'en utilisant directement un indice dans un tableau, on est en O(1), en plus d'être compact en mémoire...
21/08/2016, 22h49
zobal

@JolyLoic: tu as raison cependant si on considère les lettres de l'alphabet (N=26) on a une map de profondeur 5 (au mieux; 26 au pire); le gain n'est donc pas très important. Par contre, le tableau rend le code moins lisible (genre lut[int(c-'a')]) et surtout moins polyvalent (par exemple, si on veut mettre des chiffres ou des signes de ponctuation dans la clé).
22/08/2016, 02h26
alexandrempg
Bonsoir à tous!

Je vous remercie tous pour vos différentes réponses que j'ai bien pris le temps de lire, diverses solutions toutes autant intéressantes que les autres, j'ai actuellement réussi à effectuer la substitution, cependant cette dernière n'est pas optimisée encore à 100% avec un itérateur manquant, ainsi que les foncteurs et algorithmes que je n'ai pas encore appliqué à mon foncteur. Je prendrai le temps de revenir ici afin de vous poster ce que j'ai effectué.

Pour utiliser la substitution, je suis déjà parti sur l'idée de zobal qui donne une certaine version pour "affecter" la clé et la valeur.
Citation:
Envoyé par zobal

Salut

Je ne vois pas trop l'intérêt de lire le fichier avec un itérateur puisqu'il faut faire un traitement non homogène sur les données. Personnellement, j'aurais écrit :

Code:

1 2 3 4 ifstream fichier("cle.txt"); map<char,char> lut; char cle, valeur; while (fichier >> cle) { if (fichier >> valeur) lut[cle] = valeur; }
J'aurai cependant une petite question pour toi zobal, si tu me lis encore, ou bien les autres éventuellement qui auraient la réponse. Comment cette ligne:

Code:

while (fichier >> cle) { if (fichier >> valeur) lut[cle] = valeur; }

arrive-t'elle à déterminer qui est la clé et qui est la valeur dans mon fichier .txt? Car c'est la première utilisation que je vois de map pour affecter des valeurs d'un fichier. Pour moi la map, si je ne lis pas un fichier, je passe directement par les déclarations du genre:
Code:

1 2 3 lut['A'] = 'E'; lut['B'] = 'K'; lut['C'] = 'O';
qui me permettent de définir qui est la clé et qui est la valeur. Mais dans le fichier .txt, on ne le sait pas à priori, donc, comment la boucle while et if arrive à le déterminer? Car ça m'éclairerait sur un point noir du côté du conteneur map qui m'aiderait grandement, et via la doc sur C++reference je n'ai pas trouvé d'éventuels exemples qui permettraient de comprendre tout ça.

Pour ce qui est de l'algorithme, je ne l'ai pas précisé au début, mais j'utiliserai à coup sûr std::transform() sur ma chaîne de caractère en lui appliquant le foncteur, et en stockant le résultat sur une autre chaîne de caractère qui sera

Code:

string texte_crypte;

afin de ne pas modifier la première chaîne de caractère contenant le texte original.

Je ne pensais pas à un tableau où l'on ne mettrait que les lettres, mais à un tableau où l'on mettrait tous les chars.
Un truc genre (code écrit à la volée, non testé):
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 using Conversion = std::array<char, std::numeric_limit<unsigned char>::max()>; Conversion createConversion() { Conversion conversion; static_assert(sizeof(char)<sizeof(int)); for (int c = 0; c<std::numeric_limit<unsigned char>::max() ; ++c) { conversion[c] = static_cast<char>(c); } // On modifie alors les valeurs qui n'ont pas une conversion standard... return conversion; } // Pour définir le cryptage d'un caractère : void setConv(Conversion &conv, char normalChar, char cryptedChar) { conv[static_cast<unsigned_char>(normalChar)] = cryptedChar; } // Pour crypter : char encrypt(Conversion const &conv, char normalChar) { return conv[static_cast<unsigned_char>(normalChar)]; }
Le seul truc pas hyper évident là dedans, c'est la conversion en unsigned_char pour le cas où char serait signé. Mais de toute façon, point de vue lisibilité, tout le but du jeu est d'encapsuler ça.

Et du point de vue performance, une profondeur de 5, c'est toujours 5 branchements à faire, et 5 possibilités de cache miss. Je n'ai pas le temps de faire les mesures, mais il y a des chances que pour des données en mémoire, ça se traduise par un taux de caractères cryptés par seconde 5 fois plus faible au moins. Je ne trouve pas ça forcément négligeable. Pour des données sur disque ou sur réseau, je n'ai aucune idée de ce que ça donnerait :)
Certes, il ne s'agit là que d'un exercice, mais le but d'un exercice n'est-il pas aussi de prendre les bons réflexes ?

@JolyLoic: oui bien vu, avec le mapping complet on gère tous les caractères. Par contre, je continue à croire que le map est plus lisible et que le gain n'est pas très important : il s'agit de la complexité par rapport à la taille de la clé (qui est bornée) mais ce qui risque d'être couteux, c'est la complexité par rapport à la taille du texte à chiffrer et dans ce cas, on est en linéaire dans les deux solutions. Le choix dépend plutôt de l'application visée, sachant aussi que "early optimisation is the root of all evil"...

@alexandrempg: j'ai compris que le fichier cle.txt contient un caractère non chiffré (cle dans la map) puis son caractère chiffré (valeur dans la map) et ainsi de suite pour les autres caractères. Du coup, la ligne while (fichier >> cle) { if (fichier >> valeur) lut[cle] = valeur; } lit tout simplement deux caractères, les place dans la map puis recommence pour les suivants. Les valeurs de retour de >> sont testées pour vérifier la fin du flux mais en gros, ça revient à faire :
Code:

1 2 3 4 5 while (fichier) { fichier >> cle; // on lit le caractère à chiffrer fichier >> valeur; // on lit le caractère "chiffré" correspondant lut[cle] = valeur; // on remplit la map } // on boucle pour les caractères cle/valeur suivants

22/08/2016, 10h08
Bousk

La map c'est le premier jet, l'application naïve. Par la suite l'utilisation d'un vector est effectivement préférable par souci de performance :)
Et le passage de map à vector devrait être totalement gratuit grâce à l'opérateur [] de part et d'autre :P

Tu ne travaille que sur l'alphabet?
Dans ce cas c'est très simple.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/** Table de remplacement */
//                                   { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M','N', 'O', 'P', 'Q','R','S','T', 'U', 'V', 'W', 'X', 'Y', 'Z' };
static const char ReplacementMaj[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M','N', 'O', 'P', 'Q','R','S','T', 'U', 'V', 'W', 'X', 'Y', 'Z' };
//                                   { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm','n', 'o', 'p', 'q','r','s','t', 'u', 'v', 'w', 'x', 'y', 'z' };
static const char ReplacementMin[] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm','n', 'o', 'p', 'q','r','s','t', 'u', 'v', 'w', 'x', 'y', 'z' };
 
char Decrypt(const char C)
{
    // Recuperer la value numerique du character
    const int CleNum = (int)C;
 
    // La lettre est-elle Majuscule?
    if (CleNum >= (int)'A' && CleNum <= (int)'Z') // C-cast. et alors? :)
    {
        return ReplacementMaj[CleNum - (int)'A'];
    }
    // Est-elle possible Minuscule?
    if ( CleNum >= ('a') && CleNum <= 'z' )
    {
        return ReplacementMin[CleNum - (int)'a'];
    }
    //La lettre n'est pas decryptable    
    return '?';
}
 
char Decrypt(const wchar_t C)
{
    if(C > 0x7F) // Le caractère n'est pas ASCII pure
        return '?'; //La lettre n'est pas decryptable
    return Decrypt((char)C);
}

Celui qui me parle de C-Cast je le clou sur place.

22/08/2016, 13h45
zobal

@Astraya; oui mais je pense que le but de la discussion est d'aider alexandrempg à écrire de lui-même une solution en C++ propre, pas de lui fournir un code tout fait en C tout moche....
22/08/2016, 14h02
Astraya

On va prendre le problème a l'envers. Qu'est ce qui ne compile pas en C++ dans ce programme?
La map n'a aucun intérêt. Tu veux pas du tableau static? Mets un vector et prouve moi que c'est mieux. Tu veux du static_cast, met le et prouve moi que c'est plus lisible et plus rapide et plus mieux.

Le code fourni lui permets de comprendre comment faire pour changer une lettre par un autre, ce n'est en aucun cas la réponse à son TP
22/08/2016, 14h08
zobal

Citation:

Envoyé par Astraya

On va prendre le problème a l'envers. Qu'est ce qui ne compile pas en C++ dans ce programme?
La map n'a aucun intérêt. Tu veux pas du tableau static? Mets un vector et prouve moi que c'est mieux. Tu veux du static_cast, met le et prouve moi que c'est plus lisible et plus rapide et plus mieux.

Ok, excuse-moi d'avoir oser critiquer ta solution, elle est merveilleuse et tu es beau, fort et intelligent.
22/08/2016, 14h22
Ehonn

Petit message juste en passant (je n'ai pas lu le reste et ne veux pas prendre au débat "le C c'est mal" ici).

Citation:

Envoyé par Astraya

Mets un vector et prouve moi que c'est mieux. Tu veux du static_cast, met le et prouve moi que c'est plus lisible et plus rapide et plus mieux.

L'équivalent serait plus :
- std::array (pour éviter l'allocation dynamique)
- les "constructeurs" pour les casts (exemple : int(a_char)) (coding style)
- l'utilisation de std::isupper et std::islower (coding style)
- on pourrait utiliser un else if dans la fonction Decrypt (coding style)
23/08/2016, 16h53
Bousk

Citation:

Envoyé par Ehonn

- std::array (pour éviter l'allocation dynamique)

allocation dynamique d'un tableau static const ? :calim2:

Citation:

Envoyé par Ehonn

- les "constructeurs" pour les casts (exemple : int(a_char)) (coding style)

inutile

Citation:

Envoyé par Ehonn

- l'utilisation de std::isupper et std::islower (coding style)

totalement gadget. Perso je ferais un gros switch case.

Citation:

Envoyé par Ehonn

- on pourrait utiliser un else if dans la fonction Decrypt (coding style)

inutile puisqu'on ne sort jamais d'un if vu qu'ils ont tous un return :calim2:
23/08/2016, 19h56
Ehonn

Pas sûr que mon message a été bien interprété :s

Astraya "proposait" (avec "ironie") des changements pour introduire plus de "C++" dans le code qu'il propose.
Il parlait de std::vector et static_cast, je disais juste que std::array et T() était plus "adapté".
Le reste est évidement "inutile" et cela est précisé par « coding style ».

Du coup j'ai une question.
Dans static const std::vector<int> v = { 1, 2, 3 };, il n'y a pas d'allocation dynamique ?
23/08/2016, 22h51
jo_link_noir

Citation:

Envoyé par Ehonn

Du coup j'ai une question.
Dans static const std::vector<int> v = { 1, 2, 3 };, il n'y a pas d'allocation dynamique ?

static const ne fait rien de magique sur le constructeur, alors si, il y a allocation dynamique. Mais qu'une fois.
Perso, les constantes dans les fonctions, je les préfère en static constexpr pour les optimisations potentielles.
23/08/2016, 23h06
Bousk

Citation:

Envoyé par Ehonn

Dans static const std::vector<int> v = { 1, 2, 3 };, il n'y a pas d'allocation dynamique ?

Bien sur que si, interne au vector :weird:
Donc on s'en moque.
26/11/2016, 15h06
alexandrempg

Bonjour,

Navré pour la réponse tardive, je suis parti sur la solution de zobal, et ça a marché correctement. Je vous remercie tous pour votre implication. Je marque le sujet comme résolu.