[c++] implementatie RC4 algoritme

[writser]

Voor een uitleg over RC4, zie Wikipedia: RC4

Ik probeer het RC4-algoritme te implementeren in C++. Aangezien het algoritme vrij simpel is kan ik hier de gehele code wel posten:

C++:

#include <iostream>
#include <string>
#include <vector>

class RC4 {
public:
    RC4(std::string key) : x(0), y(0) {
        s.reserve(256);
        for (unsigned int i = 0; i < 256; i++) {
            s.push_back(i);
        }

        unsigned int j = 0;
        for (unsigned int i = 0; i < 256; i++) {
            j = (j + s[i] + key[i % key.size()]) % 256;
            swap(i, j);
        }
    }

    unsigned int getKeystreamByte() {
        x = (x + 1) % 256;
        y = (y + s[x]) % 256;
        swap(x, y);
        return s[(s[x] + s[y]) % 256];
    }

private:
    void swap(unsigned int i, unsigned int j) {
        unsigned int temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }

    std::vector<unsigned int> s;
    unsigned int x,y;
};


int main() {
    unsigned char c;
    RC4 rc4("2008");
    
    while (std::cin.good()) {
        std::cin >> c;
        c = c ^ rc4.getKeystreamByte();
        std::cout << c;
    }
    
    return 0;
}

Voorzover ik weet is dit gewoon een letterlijke implementatie van het algoritme zoals het op wikipedia staat. Ik gebruik ook geen pointers o.i.d., de code is straightforward. Toch levert dit niet dezelfde resultaten op als de voorbeelden op wikipedia. Heeft er iemand enig idee wat er fout is aan mijn implementatie? Ik ben al dagen aan het prutsen maar kom er niet uit ..

[writser]

Volgens wikipedia:

RC4( "Secret", "Attack at dawn" ) == 45A01F645FC35B383552544B9BF5

Volgens mijn programma:

Attack at dawn
45a01f645fc31a2d25134744

De eerste paar karakters gaan dus goed, maar daarna gaat er ergens iets verkeerd in mijn algoritme. Maar geen idee wat, volgens mij zijn zowel mijn getKeystreamByte() als de initialisatie van de tabel goed geimplementeerd. Hieronder staat de pseudocode van wikipedia. Deze heb ik toch letterlijk geimplementeerd?

Initialisatie:

for i from 0 to 255
S[i] := i
endfor
j := 0
for i from 0 to 255
j := (j + S[i] + key[i mod keylength]) mod 256
swap(S[i],S[j])
endfor

bytes opleveren:

i := 0
j := 0
while GeneratingOutput:
i := (i + 1) mod 256
j := (j + S[i]) mod 256
swap(S[i],S[j])
output S[(S[i] + S[j]) mod 256]
endwhile

[ Voor 38% gewijzigd door writser op 21-02-2008 13:55 ]

[Creepy]

Ben je al aan het debuggen geslagen? Ja? Wat heb je dan precies gedebugged en kreeg je echt de output die je verwachte?

Het is hier niet de bedoeling dat je je code dumpt, roept wat er fout is en ondertussen hopen dat wij het voor je gaan fixen.

Edit: ah, je tweede post stond er net nog niet.

Tip: debug (de aanroep van) je swap functie.
Tip2: we hebben een edit knop, gebruik die dan ook

[ Voor 14% gewijzigd door Creepy op 21-02-2008 13:57 ]

[.oisyn]

Komt dat niet door de newline die je na je invoer krijgt? Misschien moet je gewoon eens proberen letterlijk de string "Attack at dawn" in je programma te testen ipv dmv invoer.

En op wikipedia gebruiken ze "Secret" als key, jij "2008"

[ Voor 15% gewijzigd door .oisyn op 21-02-2008 14:08 ]

[writser]

@Creepy: de swap-functie doet precies wat hij moet doen, voorzover ik zie.

@Oisyn: het algoritme werkt byte-voor-byte. Dus als die newline het probleem is dan zou alleen de laatste hexadecimaal anders moeten zijn. In de voorbeeldcode hier staat inderdaad de key "2008", maar die heb ik wel aangepast . Zoals je ziet zijn de eerste x karakters van mijn uitvoer wel identiek. Maar daarna gaat mijn programma de soep in. Ik vermoed dat ergens een overflow zit, of dat een unsigned <-> signed conversie dit probleem veroorzaakt, maar kan niks vinden.

[ Voor 44% gewijzigd door writser op 21-02-2008 14:11 ]

[.oisyn]

Je kunt idd beter gebruik maken van &255 ipv %256 - die laatste kan negatief zijn als het getal wat je deelt ook negatief is. En aangezien std::char gebruik maakt van char en char vaak signed is, kan dat dus wel voorkomen. Maar niet in jouw testcase, want dat zijn als het goed is allemaal ASCII characters (en vallen dus in de range 1..127 en zijn dus niet negatief als signed char)

[writser]

Oisyn: daar was ik ook bang voor. Maar ik werk overal met unsigned datatypes dus voorzover ik weet zou modulo ook moeten werken. Ook heb ik alle modulo-operaties al vervangen door een bitwise AND. Maar mijn programma levert dan nog steeds precies hetzelfde resultaat op. Daar zit de fout dus niet in.

[Creepy]

writser schreef op donderdag 21 februari 2008 @ 14:08:
@Creepy: de swap-functie doet precies wat hij moet doen, voorzover ik zie.

Duh... ik ben echt niet wakker, je hebt gelijk.

[writser]

Zucht. Ik heb het probleem gevonden. std::cin > c slaat speciale karakters over ... Ik zat zo te focussen op mijn algoritme dat ik daar overheen keek. Bovendien kreeg ik van iemand een te decoderen bestand aangeleverd in binair formaat, terwijl ik het probeerde te lezen als plaintext. Die combinatie zorgde er voor dat het zo lang duurde voor ik het probleem vond. Toch bedankt voor de hulp allen.

[.oisyn]

writser schreef op donderdag 21 februari 2008 @ 14:30:
Maar ik werk overal met unsigned datatypes

Zoals ik al zei, std::string werkt met char en die is niet per se unsigned, dus om die goed te converteren naar een unsigned int moet je sowieso & 255 gebruiken . Maar dit verklaart idd niet de "'verkeerde" werking van je implementatie (kan het niet zijn dat het voorbeeld op wikipedia gewoon niet klopt?).

.edit: ik zei toch dat je het moest testen met een letterlijke string en niet met invoer

[ Voor 9% gewijzigd door .oisyn op 21-02-2008 14:52 ]

[writser]

Jup, je had gelijk. Het probleem is nu wel opgelost, maar wat is de correcte manier om 1 karakter uit de standaard invoer te krijgen? Dus zonder dat speciale karakters worden weggefilterd? cin.get()?

[.oisyn]

Ja, cin.get() idd. Of je leest meteen een heel buffertje in met cin.read(), dat is performance-wise wat beter (vervolgens kun je met cin.gcount() opvragen hoeveel chars dat waren in het geval je een EOF oid tegenkomt)