[exercice] décoder le codage de Vigenere

**InOCamlWeTrust** · 14/10/2008, 02h12

Envoyé par Saint_Louis

Effectivement, les hypothèses du sujet sont trop réductrices et un long texte
aboutit à un pgcd égal à 1 donc inutilisable.
Bref il ne faut voir dans ce sujet qu'un simple exercice de programmation itérative mais inutilisable dans la pratique.

Comme beaucoup de choses en informatique... Il ne faut pourtant pas jetter la pierre sur les gens qui découvrent ce genre de choses, mais sur ceux qui s'obstinent à s'y attarder sans essayer des les améliorer ou d'en poursuivre les raisonnements.

**elishac** · 14/10/2008, 10h36

Justement, j'aimerais bien l'améliorer, moi... mais comment ?

**InOCamlWeTrust** · 14/10/2008, 14h16

Pour un TIPE ?

**elishac** · 14/10/2008, 16h56

Non, juste pour information personnelle

.
(mais bien tenté néanmoins

. Mon tipe, ce sera plutôt sur le cryptage sur les courbes elliptiques, j'en reparlerai dans quelques temps).

**elishac** · 15/10/2008, 19h00

Alors, quelqu'un peut-il m'aider à rendre l'algorithme correct, de telle sorte qu'il marche sur un exemple ?

**coyotte507** · 15/10/2008, 20h22

Salut,

j'ai du mal avec le caml (ce n'est pas mon langage de base), donc j'ai un fusible qui a craqué et je me suis laissé allé niveau codage (sûrement possible de faire beaucoup mieux)

J'ai adopté un modèle avec la décomposition en facteurs premiers et leurs puissances (je me suis arrêté à 25), l'algo marche à la fin mais je comprends pourquoi ça rame autant

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
let intvect_of_text s=
	let n=string_length s in
	let v=make_vect n 0 in
		for i=0 to n-1 do
			v.(i)<-(int_of_char s.[i]) -97
		done;
v;;
 
let text_of_intvect v=
	let n=vect_length v in
	let s=make_string n `a` in
		for i=0 to n-1 do
			s.[i]<- char_of_int (v.(i) +97)
		done;
s;;
 
let codageVigenere t c =
	let aux_codageVigenere t n c k =
		for i=0 to n-1 do
			t.(i)<-(let a=(t.(i)+c.(i mod k)) in if a>25 then a-26 else a)
		done;
		text_of_intvect t
	in
	aux_codageVigenere (intvect_of_text t) (string_length t) (intvect_of_text c) (string_length c) 
;;
 
let distanceRepetitions t' n i record =
	let rec dist acc t' n abs = function
		i when i <= n-3 -> if t'.(abs)=t'.(i) && t'.(abs+1)=t'.(i+1) && t'.(abs+2)=t'.(i+2) 
							then (record.(i) <- true; (dist ((i - abs)::acc) t' n abs (i+1)))
							else dist acc t' n abs (i+1)
		| _ -> acc
	in
	dist [] t' n i (i+3)
;;
 
let longueurDeLaCle t' n =
	let l = vect_length t' in
	let record = make_vect l false in
	let rec distances accu = function
		i when i <= n-3 -> 
			if record.(i) == false then distances (( accu @ (distanceRepetitions t' n i record))) (i+1)
			else distances accu (i+1)
		| _ -> accu
	in
	let all_distances = distances [] 0 in
	let nombres_premiers = [| 2; 3; 4; 5; 7; 8; 9; 11; 13; 16; 17; 19; 23; 25|] in
	let ln = vect_length nombres_premiers in
	let facteurs = make_vect ln 0 in
	let decompose_en_facteurs liste = 
		let rec divise nombre = function
			i when i < ln -> if nombre mod nombres_premiers.(i) == 0 
								then facteurs.(i) <- (facteurs.(i) + 1);
								divise nombre (i+1)
			| _ -> 0
		in
		let rec dec count = function
			l::r -> (divise l 0; dec (count+1) r)
			| [] -> count
		in
		dec 0 liste
	in
	let num = decompose_en_facteurs all_distances in
	print_string "Nombres de distances: ";
	print_int num;
	print_string "\n tableau des apparitions des facteurs premiers: \n";
	for i = 0 to ln - 1 do
		if facteurs.(i) > 0 then
			(print_int nombres_premiers.(i); 
			print_string ": ";
			print_int facteurs.(i);
			print_string "(";
			print_int (facteurs.(i)*100/num);
			print_string "%)\n";)
	done;	
	0
;;
 
let texte = "<je n'ai pas assez de place pour taper le texte (fichue limite de caractères) - remplacer ce texte par celui super long>";;
let cle = "chienne";;
 
let texte_code = codageVigenere texte cle;;
let t' = intvect_of_text texte_code;;
 
longueurDeLaCle t' (string_length texte);;

A la fin j'ai le droit à 77% de distances '7', ce qui est la longueur de la clé (pour des répétitions de 3 caractères), il y aura sûrement un pourcentage plus élevé avec des répétitions de 4 caractères.

C'est normal qu'il y ai un si fort pourcentage de 2 (50%) après tout la moitié des nombres sont pairs, il en est de même pour les 3 (33%), 4 (25%), 5 (20%), etc.

Conclusion: des répétitions de 4 caractères et 80% d'un facteur semblent un bon compromis.

**elishac** · 16/10/2008, 05h05

Oui j'ai testé ton programme ça marche.
(juste je ne comprends pas pourquoi le dernier résultat est 0?).
Je vais essayer de le faire moi-même. Je le mettrai sur internet d'ici peu.
PS: j'ai pas compris ta liste de nombres premiers ? (pourquoi 16 est premier, par exemple)

Question subsidiaire pour tout le monde: comment compiler le programme, pour qu'il aille plus vite (actuellement, j'utilise juste le logiciel pour windows fourni par l'inria).

**gasche** · 16/10/2008, 11h53

Facteurs premiers et leurs puissances. Il essaie de stocker les p^n avec p premier et n entier (strictement positif) inférieurs à un nombre donné. 4, 8, 9, 16 et 25 sont des puissances d'un nombre premier.

**elishac** · 17/10/2008, 19h09

Mais alors que se passe-t-il si 6 est la longueur de la clé ?

**coyotte507** · 17/10/2008, 20h42

Alors 2 et 3 auront chacun + de 80% d'apparition.

**elishac** · 17/10/2008, 21h08

Dans ce cas pourquoi ne pas faire pour chaque k entier, au lieu de seulement les premiers et les puissances de premiers ?

**coyotte507** · 18/10/2008, 00h39

Parce que ça prend moins de temps de tester la division par des nombres premiers que par tous les nombres.

D'ailleurs dans le tableau j'ai stocké les puissances des nombres premiers, et j'ai testé tous les nombres premiers et leurs puissances de 2 à 25, dans la réalité on regarde si d mod p = 0, si oui on prend d = d/p et on continue jusqu'à d = 1, pour stocker les puissances on s'y prend autrement (Liste pour chaque nombre premier?), bref y'a moyen d'augmenter de beaucoup l'efficacité.

Tu n'as qu'à tester...

**elishac** · 18/10/2008, 20h57

Quelqu'un peut-il répondre à la question suivante :

Question subsidiaire pour tout le monde: comment compiler le programme, pour qu'il aille plus vite (actuellement, j'utilise juste le logiciel pour windows fourni par l'inria).

**InOCamlWeTrust** · 18/10/2008, 23h33

Ben alors, tu peux pas.

Il faut que tu installes ou Cygwin ou MingW ou VisualC++... pour le faire.

Bien-sûr, la solution plus simple consistant à installer Linux (réellement, je ne plaisante pas).

**elishac** · 19/10/2008, 15h17

Tu peux préciser la marche à suivre en détail ?

**InOCamlWeTrust** · 19/10/2008, 15h39

Et bien c'est très simple.

1- tu sauvegardes toutes tes données importantes sur un support amovible : disque dur externe, clef USB, CD ou DVD, voire un autre ordinateur

2- tu mets ton CD ou DVD de Windows dans le lecteur et tu redémarres l'ordinateur. Tu réinstalles Windows sur une partition réduite, et le reste de la place, tu n'y touches pas ; tu la laisses en tant que mémoire libre.

3- tu prends Mandriva ou Suse (les deux plus simples à installer et à utiliser), et tu démarres l'ordinateur avec le CD ou DVD. Au début, tu choisis "installer sur espace libre", et tu attends que ça se passe.

Environ 20 à 30 minutes après, tu auras un ordinateur avec deux systèmes, et tu pourras accéder sans problèmes à ta partition Windows depuis Linux.

**elishac** · 19/10/2008, 17h19

Sauvegarder toutes mes données, tout ça, c'est beaucoup trop compliqué... t'es sûr qu'il n'y a aucun autre moyen pour qu'un programme s'exécute plus vite ??