Dat artikel gaat wat slordig om met definities en beschrijvingen.
Hier wat ze doen:
Je gaat uit van een image C (later in het artikel verward met I) zie Table 1.
Van alle pixelwaarden in die image neem je het minst significante bit = LSB, dit levert de first bit plane I (dit is de juiste I).
In feite: I = alle pixelwaarden in C modulo 2 genomen. Dit is Table 4.
Het resultaat deel je op in blokken Ib van bekende afmetingen n x m, hier 4 x 4.
Per blok b doe je dan het volgende:
- eerst XOR je Ib met een geheime sleutel K (Table 2), dit geeft Table 5: Vb = Ib XOR K
(matrix Vb = het resultaat in blok b)
- dit resultaat vermenigvuldig je elementgewijs met gewichtmatrix W, Table 6: Hb = Vb .* W
(matrix Hb = elementgewijze (puntgewijze = .* ) vermenigvuldiging van Vb en W)
K en W zijn geheim, alleen bekend bij zender en ontvanger.
Even tussendoor:
De definitie van W op de derde pagina van het artikel klopt niet.
W is zodanig opgebouwd, dat ALLE getallen van 1 t/m (2^r)-1 er ten minste 1 keer in voorkomen.
In het voorbeeld is r=4 en hebben we alle getallen van 1 t/m 15 nodig.
In de constructie van een geschikte W plaats je eerst deze getallen.
Deze getallen hoeven in W niet op de juiste volgorde te staan (maar mag wel, zoals in het voorbeeld Table 4).
Alle plaatsen p die over zijn in W geef je ieder voor zich een willekeurige waarde Lp waarbij 1 <= Lp <= (2^r)-1.
Nu verder met het algoritme:
In stap 3 berekenen we H = de som van alle elementen van matrix Hb.
In feite hebben we van dit getal alleen de waarde mH = de waarde van H modulo 2^r nodig:
mH = H mod 2^r.
We willen nu Ib zodanig manipuleren naar Ib', dat deze berekening nu niet meer mH, maar B oplevert,
waarbij B = de waarde van de bitstring b1..br gezien als getal.
Dus zodanig dat:
SUM( (Ib' XOR K) .* W) mod 2^r = B
Merk op: als mH = B hoeven we niets te veranderen in Ib en zijn we klaar.
In alle andere gevallen moeten we een waarde d bij mH opgeteld zien te krijgen, zodanig dat mH + d = B.
Ofwel: d = (B - mH) mod 2^r
(Noot: ze claimen dat je hiervoor maximaal 2 bits van Ib hoeft om te flippen, ik neem nu aan dat dit zo is, maar mogelijk wil je dit ook nog bewijzen.)
De gedachte is daarbij als volgt:
Als we het bit op plaats (i,j) in Ib omflippen, dan flipt het bit (i,j) in Vb (= Ib XOR K) ook om (ga na).
- als dat bit van 0 naar 1 gaat, dan was het gewicht W(i,j) in de oorspronkelijke mH NIET meegeteld, maar in de nieuwe situatie WEL (oorspronkelijk was dat gewicht met nul vermenigvuldigd, maar nu met 1).
mH wordt dan vermeerderd met W(i,j)
- als dat bit van 1 naar 0 gaat, dan was het gewicht W(i,j) in de oorspronkelijke mH WEL meegeteld, maar in de nieuwe situatie NIET (oorspronkelijk was dat gewicht met 1 vermenigvuldigd, maar nu met nul).
mH wordt dan verminderd met W(i,j)
Omdat we modulo 2^r werken, is verminderen met een getal a gelijk aan vermeerderen met een getal (2^r)-a.
We kunnen hiermee elke bitflip van bit (i,j) in Ib vertalen naar een gewichtstoename w van mH.
Dit gebeurt in stap 4:
Sw = de verzameling indexparen (i,j) van elementen van Ib (en dus ook van Vb) waarvoor bitflip een gewichtstoename w oplevert:
- als Vb(i,j)==0 dan voeg je (i,j) toe aan S(W(i,j)): omflippen van Ib(i,j) geeft gewichttoename W(i,j)
- als Vb(i,j)==1 dan voeg je (i,j) toe aan S(2^r-W(i,j)): omflippen van Ib(i,j) geeft gewichttoename 2^r-W(i,j)
Voorbeeld: blok I2 pagina 4:
Vb =
1 1 0 0
1 1 1 1
1 1 1 1
1 0 1 0
W =
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 2
Ga alle elementen van Vb af:
Vb(1,1) = 1, dus voeg (1,1) toe aan S(16 - W(1,1)) = S(16-1) = S15 => S15 = { (1,1) }
Vb(1,2) = 1, dus voeg (1,2) toe aan S(16 - W(1,2)) = S(16-2) = S14 => S14 = { (1,2) }
Vb(1,3) = 0, dus voeg (1,3) toe aan S(W(1,3)) = S3 => S3 = { (1,3) }
etc.
Je vindt zo:
S0 = leeg
S1 = { (4,3) }
S2 = { (4,4) }
S3 = { (1,3), (4,1) }
S4 = { (1,4), (3,4) }
S5 = { (3,3) }
S6 = { (3,2) }
S7 = { (3,1) }
S8 = { (2,4) }
S9 = { (2,3) }
S10 = { (2,2) }
S11 = { (2,1) }
S12 = leeg
S13 = leeg
S14 = { (1,2), (4,2) }
S15 = { (1,1) }
Verder is voor blok 2: H = 99, dus mH = 3
De gewenste binaire bitcode voor blok 2 = 1101, dit is tientallig B = 13.
Dan is d = 13 - 3 mod 16 = 10 mod 16
Nu stap 6:
Als d=0 dan is mH = B en hoeven we niets te doen.
In de andere gevallen berekenen we voor alle h van 0 t/m (2^r)-1:
h*d en -(h-1)*d
en zoeken we de 2 S-verzameling die deze getallen produceren:
als we bij mH eerst h*d optellen en vervolgens -(h-1)*d,
dan tellen we bij mH in totaal h*d - (h-1)*d = h*d - h*d + d = d op (mod 2^r).
In het voorbeeld van blok I2 (alle waarden weer modulo 16):
Code: Selecteer alles
h h*10 -(h-1)*10
0 0 10
1 10 0
2 4 6
3 14 12
4 8 2
5 2 8
6 12 14
7 6 4
8 0 10
9 10 0
10 4 6
11 14 12
12 8 2
13 2 8
14 12 14
15 6 4
S0 heeft een bijzondere plaats: deze is weliswaar leeg, maar hebben ook niet nodig:
in bovenstaand voorbeeld vinden we S0 voor h = 0, 1, 8 of 9:
S0 wordt in al deze 4 gevallen gecombineerd met S10, dus S10 levert in zijn eentje een mogelijke oplossing:
S10 = { (2,2) }, dus flip ALLEEN bit (2,2) en je hebt een oplossing: dit is gedaan in Table 7.
Om meer oplossingen te vinden:
Verwijder alle regels met waarden i waarvoor Si = leeg: hier: S0, S12 en S13
(hierbij is i = h*10 of i = -(h-1)*10)
(Noot: in het artikel gebruiken ze de letter phi, maar ze bedoelen het symbool voor de lege verzameling.)
Dan houden we over:
Code: Selecteer alles
h h*10 -(h-1)*10
2 4 6
4 8 2
5 2 8
7 6 4
10 4 6
12 8 2
13 2 8
15 6 4
De oplossingen met 2 bitflips kan je dus kiezen uit de combinaties:
- S2 en S8: bit (4,4) en bit (2,4)
- S4 en S6: [bit (1,4) en bit (3,2)] OF [bit (3,4) en bit (3,2)]
Je kan nu random een oplossing met 1 of 2 bitflips kiezen.
Een ander voorbeeld dan in het artikel: flip bit (1,4) en bit (3,2):
Ib =
0 1 1 0
1 0 1 0
0 1 0 1
0 1 1 1
wordt daardoor omgezet naar:
Ib' =
0 1 1 1
1 0 1 0
0 0 0 1
0 1 1 1
en dan is
SUM( (Ib' XOR K) .* W) mod 16 = 13 = B
dus precies wat we wilden.
EDIT: Stap 6 (vermenigvuldiging met h) heb je helemaal niet nodig en geeft te weinig oplossingen.
Ik kom hier op terug.