Devoir Maison - Musique Décalée - Corrigé
Table of Contents
Les coefficients des questions sont les suivants :
1.1 | 1.2 | 1.3 | 1.4 | 1.5 | 1.6 | 1.7 | 1.8 | 1.9 | 1.11 a | 1.11 b | 1.12 | 1.13 | 1.14 | 1.15 | 2.1 | 2.2 | 2.3 | 2.5 | 2.6 | 2.7 | 2.8 | 2.9 | 2.10 | 2.11 |
2 | 1 | 2 | 3 | 1 | 3 | 4 | 3 | 4 | 4 | 4 | 3 | 1 | 4 | 2 | 3 | 3 | 2 | 5 | 5 | 5 | 5 | 5 | 5 | 5 |
1. Création de fichier WAV
import numpy as np from scipy.io import wavfile
1.1. Introduction
1.1.1. Fréquence d’une touche de piano
def freq_touche(n) : """ Entrées : n le numéro d'une touche de piano entre 1 et 88 Sortie : la fréquence en Hz de la touche n du piano si 0 < n < 89, 0 sinon. """ freq = 0 if 0 < n < 89 : freq = 2 ** ( ( n - 49 ) / 12 ) * 440 return freq
1.2. Outils numériques
1.2.1. Valeur absolue
def abs(x) : """ Entrées : x un flottant Sortie : la valeur absolue de x """ a = x if x < 0 : a = -a return a
1.2.2. Approximation de pi
def approx_pi(n) : """ Entrées : un entier n Sortie : Pn qui converge vers pi. """ somme = 0 i = 0 while i <= n : somme += (-3.0) ** (-i) / (2.0 * i + 1.0) i = i + 1 return 12.0 ** 0.5 * somme
def approx_pi(n) : """ Entrées : un entier n Sortie : Pn qui converge vers pi. """ somme = 0 for i in range(n+1) : somme += (-3.0) ** (-i) / (2.0 * i + 1.0) return 12.0 ** 0.5 * somme
approx_pi(40), np.pi
3.141592653589794 | 3.141592653589793 |
1.2.3. Première approximation de \(\sin(x)\)
def approx_sin(x,n) : """ Entrées : un entier n et un réel x Sortie : Sn qui converge vers sin(x). """ somme = 0 u = x somme = u i = 1 while i <= n : u = - u * x * x / ( 2 * i * (2 * i + 1) ) somme += u i = i + 1 return somme
Avec une boucle for.
def approx_sin(x,n) : """ Entrées : un entier n et un réel x Sortie : Sn qui converge vers sin(x). """ somme = 0 u = x somme = u for i in range(1, n+1) : u = - u * x * x / ( 2 * i * (2 * i + 1) ) somme += u return somme
approx_sin(np.pi / 2,100), np.sin(np.pi / 2)
1.0000000000000002 | 1.0 |
1.2.4. Etude de la convergence de approx_sin
La fonction conv
renvoie le plus petit rang i
à partir du quel
approx_sin(2 * n * pi, i)
est plus petit que erreur
ou nmax
si i
dépasse
nmax
. En pratique on remarque que pour \(n \leq 4\), on arrive en moins de 100
itération à une précision de \(10^{-5}\), mais dès que \(n\) devient plus grand que
\(5\) il faut plus de 100 itération pour atteindre cette précision (si elle peut
être atteinte).
1.2.5. Amélioration de l’approximation de \(\sin(x)\)
def modulo_2pi(x) : """ Entrées : x un flottant Sortie : x modulo 2*pi """ x_modulo = abs(x) pi = approx_pi(40) while x_modulo > pi : x_modulo = x_modulo - 2 * pi if x < 0 : x_modulo = - x_modulo return x_modulo
def approx_sin(x,n) : """ Entrées : un entier n et un réel x Sortie : Sn qui converge vers sin(x). """ somme = 0 x_modulo = modulo_2pi(x) u = x_modulo somme = u i = 1 while i <= n : u = - u * x_modulo * x_modulo / ( 2 * i * (2 * i + 1) ) somme += u i = i + 1 return somme
1.3. Échantillonnage
1.3.1. Discrétisation d’un intervalle
On note que \(i_n - i_1 = \sum_{i = 1} ^ {n-1} i_{k+1} - i_k = \alpha \, (n-1)\) donc \(\alpha = \frac {b-a} {n-1}\) et par récurrence \(\forall 1 \leq k \leq n, i_k = i_1 + (k-1)\, \alpha\).
def discretisation(a,b,n) : """ Entrées : - a < b deux flottants représentant un intervalle [a;b]. - n >= 2 un entier. Sortie : Une liste de n points i1, i2, ..., in de [a,b] tels que i1 = a, in = b et |i(k+1) - ik| est constant. """ dis = [] ecart = (b-a) / (n-1) i = 0 while i < n-1 : dis = dis + [ a + i * ecart ] i = i + 1 dis = dis + [b] return dis
Avec boucle for et mutabilité des listes :
def discretisation(a,b,n) : """ Entrées : - a < b deux flottants représentant un intervalle [a;b]. - n >= 2 un entier. Sortie : Une liste de n points i1, i2, ..., in de [a,b] tels que i1 = a, in = b et |i(k+1) - ik| est constant. """ dis = [] ecart = (b-a) / (n-1) for i in range(n-1) : dis.append(a + i * ecart) dis.append(b) return dis
1.3.2. Échantillonage d’une note
def echantillonnage_note(frequence,duree,freq_ech,amplitude) : """ Entrées : - frequence : flottant. La fréquence (Hz) de la note. - duree : flottant. La durée (s) de la note. - freq_ech : entier. La frequence d'echantillonnage. - amplitude : entier. L'amplitude de la note. Sortie : Une liste de valeur flottante correspondant à l'echantillonnage de la note, avec le freq_ech et l'amplitude donnés """ pi = approx_pi(40) t = discretisation(0,duree,int(freq_ech*duree)) e = [] i = 0 n = len(t) while i < n : e = e + [ amplitude * approx_sin(2 * pi * frequence * t[i], 100) ] i = i + 1 return e
Avec for et mutabilité des listes
def echantillonnage_note(frequence,duree,freq_ech,amplitude) : """ Entrées : - frequence : flottant. La fréquence (Hz) de la note. - duree : flottant. La durée (s) de la note. - freq_ech : entier. La frequence d'echantillonnage. - amplitude : entier. L'amplitude de la note. Sortie : Une liste de valeur flottante correspondant à l'echantillonnage de la note, avec le freq_ech et l'amplitude donnés """ pi = approx_pi(40) t = discretisation(0,duree,int(freq_ech*duree)) e = [] for x in t : e.append(amplitude * approx_sin(2 * pi * frequence * x, 100)) return e
pi = approx_pi(40) t = discretisation(0,2,5) echantillonnage_note(freq_touche(49),2,5,2)
0.0 | -1.9696155060240348 | -0.684040286657463 | 1.732050807563315 | 1.2855752193621506 | -1.2855752194139196 | -1.732050807521986 | 0.6840402867509466 | 1.9696155060146263 | -6.732392421326949e-12 |
1.3.3. Échantillonage d’une partition
def echantillonnage_partition(partition, freq_ech, amplitude) : """ Entrées : - partition : liste de couples d'entier et de flottant. Chaque couple correspont au numéro d'une touche de lavier et à la durée de la note produite. - freq_ech : entier. La frequence d'echantillonnage. - amplitude : entier. L'amplitude de la note. Sortie : un échantillonage de la mélodie générée. """ e = [] i = 0 n = len(partition) while i < n : couple = partition[i] note = couple[0] duree = couple[1] freq = freq_touche(note) e = e + echantillonnage_note(freq,duree,freq_ech,amplitude) i = i + 1 return e
Avec for sur une liste de couples et la notation e +
…=, ayant le même effet
que e = e + ...
, mais étant plus efficace.
def echantillonnage_partition(partition, freq_ech, amplitude) : """ Entrées : - partition : liste de couples d'entier et de flottant. Chaque couple correspont au numéro d'une touche de lavier et à la durée de la note produite. - freq_ech : entier. La frequence d'echantillonnage. - amplitude : entier. L'amplitude de la note. Sortie : un échantillonage de la mélodie générée. """ e = [] for (note,duree) in partition : freq = freq_touche(note) e += echantillonnage_note(freq,duree,freq_ech,amplitude) return e
1.3.4. Génération du fichier WAV
freq_e = 44100 # Fréquence d'échantillonnage amplitude = 2048 # Amplitude de l'échantillonnage partition = [(40,2),(42,2),(44,2),(45,2),(47,2),(49,2),(51,2)] e = echantillonnage_partition(partition,freq_e,amplitude) wavfile.write('octave4_2s.wav', rate=freq_e, data=np.array(e).astype(np.int16) )
1.3.5. Échantillonage d’un accord - Bonus
def echantillonnage_accord(frequences,duree,freq_ech,amplitude) : """ Entrées : - frequences : une liste de flottant. La listes des fréquences (Hz) des notes composant l'accord. - duree : flottant. La durée (s) de la note. - freq_ech : entier. La frequence d'echantillonnage. - amplitude : entier. L'amplitude de la note. Sortie : Une liste de valeur flottante correspondant à l'echantillonnage de la note, avec le taux et l'amplitude donnés """ pi = approx_pi(40) t = discretisation(0,duree,int(freq_ech*duree)) e = [] for x in t : valeur = 0 for f in frequences : valeur = valeur + amplitude * approx_sin(2 * pi * f * x, 100) e.append(valeur) return e
def echantillonnage_partition_accords(partition, freq_ech, amplitude) : """ Entrées : - partition : liste de couples de liste d'entiers et de flottant. Chaque couple correspont à la liste des numéros d'un accord de piano et à la durée de l'accord produite. - freq_ech : entier. La frequence d'echantillonnage. - amplitude : entier. L'amplitude de la note. Sortie : un échantillonage de la mélodie générée. """ e = [] for (accord,duree) in partition : freqs_accord = [] for note in accord : freqs_accord.append(freq_touche(note)) e += echantillonnage_accord(freqs_accord,duree,freq_ech,amplitude) return e
freq_ech = 44100 amplitude = 2048 e = echantillonnage_partition_accords([([49,52,45],5)],freq_ech,amplitude) wavfile.write('accord_fa_5s.wav', rate=freq_ech, data=np.array(e).astype(np.int16) )
1.4. Conversion d’une partition
1.4.1. Touche correspondant à une note dans l’octave
def touche_octave(s) : notes = "CcDdEFfGgAaB" i = 0 n = len(notes) while i < n : if notes[i] == s : return i i = i + 1 return -1
Avec for et enumerate
def touche_octave(s) : for i,x in enumerate("CcDdEFfGgAaB") : if x == s : return i return -1
1.4.2. Touche correspondant à une note dans l’octave
La première note, A0
donne bien une valeur de 1
.
\(t-8\) permet de donner le décalage entre la note courante et le la (A
) et
\(n*12\) permet de se situer dans l’octave \(n\).
def touche_piano(s,n) : t = touche_dans_octave(s) if t != - 1 : t = t - 8 + n * 12 return t
touche("A",4)
49
1.4.3. Lecture d’une partition
def partition(s) : notes = [] i = 0 n = len(s) while i < n : note = s[i] octave = int(s[i+1]) duree = int(s[i+2]) / 8 t = touche_piano(note,octave) notes = notes + [(t, duree)] i = i + 3 return notes
def partition(s) : notes = [] for i in range(0,len(s),3) : notes.append((touche_piano(s[i],int(s[i+1])), int(s[i+2]) / 8)) return notes
freq_ech = 44100 amplitude = 2048 e = echantillonnage_partition(partition("C42D42E42F42G42A42B42C52B42A42G42F42E42D42C42Z08"),freq_ech,amplitude) wavfile.write('octave4_allerretour.wav', rate=freq_ech, data=np.array(e).astype(np.int16) )
1.4.4. Conversion fichier vers WAV - Bonus
def generer_partition(fichier, wave, freq_ech, amplitude) : fichier = open(fichier,'r') s = fichier.read() p = partition(s) e = echantillonnage_partition(p,freq_ech,amplitude) wavfile.write(wave, rate=freq_ech, data=np.array(e).astype(np.int16) )
2. Chiffre de César
2.1. Chiffrement et Déchiffrement
2.1.1. Décalage de caractère
def decalage(c,n) : dec = ord(c) if ord('a') <= dec <= ord('z') : dec = dec + n if dec > ord('z') : dec = dec - 26 return chr(dec)
Deuxième version avec formule générique.
def decalage(c,n) : dec = ord(c) if ord('a') <= dec <= ord('z') : dec = (ord(c)-ord('a') + n) % 26 + ord('a') return chr(dec)
2.1.2. Chiffrement de César
def chiffrement_cesar(s,n) : s_chiffree = "" i = 0 n = len(s) while i < n : s_chiffree = s_chiffree + decalage(s[i],n) i = i + 1 return s_chiffree
Avec boucle for
def chiffrement_cesar(s,n) : s_chiffree = "" for c in s : s_chiffree = s_chiffree + decalage(c,n) return s_chiffree
2.1.3. Déchiffrement de César
Pour déchiffre il faut, intuivement, décaler dans le sens inverse. Toutefois,
l’énoncé impose un décalage toujours dans le même sens. Comme le décalage est
circulaire, pour décaler de -n
il suffit de décaler de 26-n
.
def dechiffrement_cesar(s,n) : return chiffrement_cesar(s,26-n)
2.1.4. Chiffrement de Fichiers
f = open('messages/message_secret_1.txt','r') texte = f.read() texte_decrypte = dechiffrement_cesar(texte,7) f_decrypte = open('message_1.txt','w') f_decrypte.write(texte_decrypte) f.close() f_decrypte.close()
2.1.5. Chiffrement de Vigenère - Bonus
def chiffrement_vigenere(s, cle) : s_chiffree = "" j = 0 # lettre de la clé utilisée comme décalage n = len(s) m = len(cle) for c in s : dec = ord(cle[j]) - ord('a') s_chiffree = s_chiffree + decalage(c,dec) # si on a décalé le caractère i, on passe au caractère suivant de la clé if ord('a') <= ord(c) <= ord('z') : j = ( j + 1 ) % m return s_chiffree
def dechiffrement_vigenere(s, cle) : cle_inversee = "" for c in cle : numero_lettre = ord(c) - ord('a') decalage_inverse = 26 - numero_lettre numero_lettre_inversee = ord('a') + decalage_inverse cle_inversee = cle_inversee + chr(numero_lettre_inverse) return chiffrement_vigenere(s, cle_inversee)
f = open("messages/message_secret_2.txt",'r') texte = f.read() texte_decrypte = dechiffrement_vigenere(texte,'eiffel') f_decrypte = open("message_2.txt",'w') f_decrypte.write(texte_crypte) f.close() f_decrypte.close()
--------------------------------------------------------------------------- NameError Traceback (most recent call last) Input In [231], in <cell line: 3>() 1 f = open("messages/message_secret_2.txt",'r') 2 texte = f.read() ----> 3 texte_decrypte = dechiffrement_vigenere(texte,'eiffel') 4 f_decrypte = open("message_2.txt",'w') 5 f_decrypte.write(texte_crypte) Input In [230], in dechiffrement_vigenere(s, cle) 5 decalage_inverse = 26 - numero_lettre 6 numero_lettre_inversee = ord('a') + decalage_inverse ----> 7 cle_inversee = cle_inversee + chr(numero_lettre_inverse) 8 return chiffrement_vigenere(s, cle_inversee) NameError: name 'numero_lettre_inverse' is not defined
2.2. Attaques du chiffrement - Bonus
2.2.1. Brute Force
Il y a 26 clés de chiffrement possible.
def brute_force(s) : l = [] for dec in range (26) : l.append(dechiffrement_cesar(s, dec)) return l
0 : wz dofowh eis borwbs b'owas dog zs xoapcb. 1 : vy cnenvg dhr anqvar a'nvzr cnf yr wnzoba. 2 : ux bmdmuf cgq zmpuzq z'muyq bme xq vmynaz. 3 : tw alclte bfp ylotyp y'ltxp ald wp ulxmzy. 4 : sv zkbksd aeo xknsxo x'kswo zkc vo tkwlyx. 5 : ru yjajrc zdn wjmrwn w'jrvn yjb un sjvkxw. 6 : qt xiziqb ycm vilqvm v'iqum xia tm riujwv. 7 : ps whyhpa xbl uhkpul u'hptl whz sl qhtivu. 8 : or vgxgoz wak tgjotk t'gosk vgy rk pgshut. 9 : nq ufwfny vzj sfinsj s'fnrj ufx qj ofrgts. 10 : mp tevemx uyi rehmri r'emqi tew pi neqfsr. 11 : lo sdudlw txh qdglqh q'dlph sdv oh mdperq. 12 : kn rctckv swg pcfkpg p'ckog rcu ng lcodqp. 13 : jm qbsbju rvf obejof o'bjnf qbt mf kbncpo. 14 : il parait que nadine n'aime pas le jambon. 15 : hk ozqzhs ptd mzchmd m'zhld ozr kd izlanm. 16 : gj nypygr osc lybglc l'ygkc nyq jc hykzml. 17 : fi mxoxfq nrb kxafkb k'xfjb mxp ib gxjylk. 18 : eh lwnwep mqa jwzeja j'weia lwo ha fwixkj. 19 : dg kvmvdo lpz ivydiz i'vdhz kvn gz evhwji. 20 : cf julucn koy huxchy h'ucgy jum fy dugvih. 21 : be itktbm jnx gtwbgx g'tbfx itl ex ctfuhg. 22 : ad hsjsal imw fsvafw f'saew hsk dw bsetgf. 23 : zc grirzk hlv eruzev e'rzdv grj cv ardsfe. 24 : yb fqhqyj gku dqtydu d'qycu fqi bu zqcred. 25 : xa epgpxi fjt cpsxct c'pxbt eph at ypbqdc.
2.2.2. Analyse de fréquence
def freq_lettre(s, lettre) : nb_lettre = 0 nb_minuscules = 0 for c in s : if lettre == c: nb_lettre = nb_lettre + 1 if ord('a') <= ord(c) <= ord('z') : nb_minuscules = nb_minuscules + 1 return nb_lettre / nb_minuscules
def freq_texte(s) : l = [] for o in range(ord('a'),ord('z')) : l.append(freq_lettre(s, chr(o))) return l
f = open('messages/message_secret_3.txt','r') texte = f.read() freq = freq_texte(texte) freq
a : 0.004368036597063381 b : 0.0 c : 0.0577731867483214 d : 0.02985316904006493 e : 0.07043459012764701 f : 0.05303622814137091 g : 0.02730022873164613 h : 0.010920091492658452 i : 0.06481221869696746 j : 0.08440935586217074 k : 0.07313509924002067 l : 0.06336604441820999 m : 0.016867114292038663 n : 1.4756880395484394e-05 o : 0.0038367889028259427 p : 0.0023758577436729877 q : 0.0013133623551981112 r : 0.0857669888585553 s : 0.01303032538921272 t : 0.027152659927691288 u : 0.03783664133402199 v : 0.1685235741164318 w : 0.010344573157234561 x : 0.011141444698590719 y : 0.007658820925256401
Le fréquence du v
est proche de celle du e
.
Il y a 5 lettres entre le a
et le e
, on vérifie que 5 lettres avant le v
,
c’est à dire pour la lettre r
, la fréquence est proche de celle du a
. C’est
bien le cas. Idem pour s
et b
, t
et c
, u
et d
, … On essaye donc
la clé qui décale a
sur r
:
cle = ord('r') - ord('a') f = open('messages/message_secret_3.txt','r') texte = f.read() texte_decrypte = dechiffrement_cesar(texte,cle) f_decrypte = open('message_3.txt','w') f_decrypte.write(texte_decrypte) f.close() f_decrypte.close()
2.2.3. Analyse de fréquence avec renvoi de la clé
def distance(l,k) : d = 0 for i in range(len(l)) : d = d + (l[i]-k[i])**2 return d
On note l_n
la liste des fréquence théorique décalée de n
vers la droite.
La clé n
la plus probable pour un texte dont la fréquence est l
est celle
qui minimise distance(l,l_n)
.
On note que ln[k] = l[k-n]
si k - n
est positif. 26 + k - n
sinon.
Donc on a toujours ln[k] = l[ (26 + k -n ) % 26 ]
.
Si on considère l’accès par
indice négatif, on remarque même que la formule ln[k] = l[k-n]
est vrai aussi
quand k-n
est négatif.
def cle(s) : l0 = [0.084,0.0106,0.0303,0.0418,0.1726,0.0112, 0.0127,0.0092,0.0734,0.0031,0.0005,0.0601, 0.0296,0.0713,0.052,0.0301,0.0099,0.0655, 0.0808,0.0707,0.0574,0.0132,0.0004,0.0045, 0.003,0.0012] l = freq_texte(s) dec_min = 0 d_min = distance(l,l0) for i in range (1,26) : li = [ l0[k-i] for k in range(26) ] d = distance(l,li) if d < d_min : d_min = d dec_min = i return dec_min
f = open('messages/message_secret_3.txt','r') texte = f.read() cle(texte), ord('r') - ord('a')
17 | 17 |
2.2.4. Attaque du chiffre de Vigenère. Longueur de clé connue
def freq_vigenere(s, n): textes = [""] * n i = 0 # Texte à remplir for c in s : if ord('a') <= ord(c) <= ord('z') : textes[i] = textes[i] + c i = ( i + 1 ) % n cle_vigenere = "" for t in textes : cle_vigenere = cle_vigenere + chr(ord('a') + cle(t)) return cle_vigenere
f = open('messages/message_secret_4.txt','r') texte = f.read() f.close() freq_vigenere(texte, 12)
brusselrules
2.2.5. Calcul de la longueur de clé la plus probable.
# Calcul de l'indice de coïncidence pour le texte s composé de minuscules ASCII # dont on extrait une lettre sur n def incidence(s, n) : # Calcul des ni nb_lettres = [0]*26 for i in range(0,len(s),n) : nb_lettres[ord(s[i]) - ord('a')] += 1 # Calcul de Ic Ic = 0 for nb in nb_lettres : Ic += nb * (nb - 1) n = len(s) // n return Ic / (n * (n-1))
def meilleur_incidence(s) : texte = "" # les minuscules ASCII de s for c in s : if ord('a') <= ord(c) <= ord('z') : texte += c n = 1 Ic = 0 while Ic < 0.07 and n <= 50 : n = n + 1 Ic = incidence(texte, n) return n
f = open("messages/message_secret_5.txt", 'r') texte = f.read() len_cle = meilleur_incidence(texte) cle_vigenere = freq_vigenere(texte, len_cle) f.close() len_cle, cle_vigenere
6 | enidan |
2.2.6. Question ouverte
- Non. Un chiffrement de césar de \(x\) puis de \(y\) est équivalent à un chiffrement de cesar de \(x+y\).
- Non. Un chiffrement de césar de
x
puis un chiffrement de Vigenère de clék
correspond à un chiffrement de vigenère de cléchiffrement_cesar(k,x)
. Non. On se ramène à un chiffrement de Vigenère simple, mais c’est un peu plus compliqué à montrer. On chiffre d’abord avec un clé
k
de longueurn
et une clék'
de longueurm
. On considère la clék''
obtenu en répétantn
foisk'
. Le chiffrement est équivalent à un chiffrement parchiffrement_vigenere(k'', k)
.On peut l’observer sur le schéma ci-dessous avec commes clés
cle
ettour
.cle
donne comme décalages, 2, 11 et 4.tour
donne 19, 14,20 et 17.t e x t e a c r y p t e r p a r d e u x c h i f f r e m e n t s + c l e c l e c l e c l e c l e c l e c l e c l e c l e c l e c l + t o u r t o u r t o u r t o u r t o u r t o u r t o u r t o u r
t | e | x | t | e | a | c | r | y | p | t | e | r | p | a | r | d | e | u | x | c | h | i | f | f | r | e | m | e | n | t | s | ||||||
+ | c+t | l+o | e+u | c+r | l+t | e+o | c+u | l+r | e+t | c+o | l+u | e+r | c+t | l+o | e+u | c+r | l+t | e+o | c+u | l+r | e+t | c+o | l+u | e+r | c+t | l+o | e+u | c+r | l+t | e+o | c+u | l+r |
On a une periodicité de 12, avec la clé [c+t,l+o,e+u,c+r,l+t, e+o, c+u,
l+r,e+t,c+o,l+u, e+r]
qui donne comme clé vzyteswcxqfv
.
Pour obtenir k''
on peut répéter k'
au minimum ppcm(m,n)
fois en réalité.