vigenere
TRANSCRIPT
Criptanaliza criptosistemului Vigenere
Fie x un cuvant peste {0, 1, . . . , 25} si k ∈ {0, 1, . . . , 25}m o cheie arbitrara,m ≥ 1. Criptarea lui x folosind cheia k va conduce la criptotextul y dat prin
yi = xi + k(((i−1) mod m)+1) mod 26,
pentru orice 1 ≤ i ≤ |x|.Textul obtinut din y extragand simboluri din n ın n pozitii ıncepand cu
pozitia a j-a va fi notat cu yn,j , pentru orice n ≥ 1 si 1 ≤ j ≤ n. Este interesantde remarcat ca, ın cazul ın care y = ek(x), are loc relatia
ym,j = SHIFT (xm,j , kj),
pentru orice 1 ≤ j ≤ m, unde m = |k|.Pentru determinarea cheii k, avand un criptotext y, se va proceda astfel:
1. Determinarea lungimii cheii (m) - folosind testul indexului de coincidenta:
Pentru un text α ∈ {0, 1, . . . , 25}∗, indexul de coincidenta, notat cu IC(α),reprezinta probabilitatea ca un simbol sa apara de cel putin doua ori ınα. Mai exact, IC(α) este dat prin
IC(α) =25∑
i=0
fi(α)|α|
fi(α)− 1|α| − 1
,
unde fi(α) reprezinta numarul de aparitii ale simbolului i ın α.
• Daca α este un text normal ın limba engleza sau un text obtinutdintr-un text normal ın limba engleza extragand simboluri din m ınm pozitii, IC(α) se poate aproxima prin
∑25i=0 p2
i∼= 0.065, unde pi
reprezinta probabilitatea de aparitie a simbolului i;
• Este interesant de remarcat ca criptarea folosind criptosistemul Sh(26)nu modifica acest indicator. Mai exact, IC(SHIFT (α, s)) = IC(α),pentru orice 0 ≤ s ≤ 25.
Astfel, IC(ym,j) = IC(xm,j) ∼= 0.065, pentru m = |k| si orice 1 ≤ j ≤ m.Urmatorul algoritm va conduce la gasirea lungimii cheii:
1
Determina lungimea cheii(y)input: y, un criptotext;output: m, lungimea cheii folosite;begin
m := 0;repeat
m := m + 1;until IC(ym,1) ∼= IC(ym,2) ∼= · · · ∼= IC(ym,m) ∼= 0.065
end.
2. Determinarea efectiva a cheii (k1, . . . , km) - folosind testul indexului decoincidenta mutuala.Pentru α, β ∈ {0, 1, . . . , 25}∗, indexul de coincidenta mutuala, notat cuMIC(α, β), reprezinta probabilitatea ca un simbol sa apara si ın α si ınβ. Mai exact, MIC(α, β) este dat prin
MIC(α, β) =25∑
i=0
fi(α)|α|
fi(β)|β|
.
• Daca α si β sunt texte normale ın limba engleza (sau texte obtinutedin texte normale ın limba engleza extragand simboluri din m ın mpozitii), MIC(α, β) se poate aproxima prin
∑25i=0 p2
i∼= 0.065;
• Daca α este un text normal ın limba engleza (sau un text obtinutdintr-un text normal ın limba engleza extragand simboluri din m ınm pozitii), MIC(α, β) se poate aproxima prin
∑25i=0 pi
fi(β)|β| .
Deoarece xm,j = SHIFT (ym,j ,−kj) si MIC(textnormal, xm,j) ∼= 0.065,pentru orice 1 ≤ j ≤ m, unde m = |k|, putem construi urmatorul algoritmpentru determinarea efectiva a cheii:
Determina cheia(y,m)input: y, un criptotext si m, lungimea cheii;output: k1, . . . , km, componentele cheii folosite;begin
for j:=1 to m dobegin
s := −1;repeat
s := s + 1;until MIC(textnormal, SHIFT (ym,j , s)) ∼= 0.065kj := (26− s) mod 26;
endend.
2