Algorytm szyfrujący DES

Hej, potrzebuję napisać algorytm szyfrujący DES. Niestety przerasta mnie trochę sposób jego opisu choćby ten z wikipedi.
Gdyby ktoś pomógł mi zrozumieć co muszę zrobić, by coś takiego napisać. Będę sobie pisał w C#, gdyż w tym języku czuję się chyba najlepiej. Studiuje i to jeden z projektów...
To tak najpierw algorytm szyfrowania danych, na początku tekst jawny, który ma zostać zaszyfrowany, dzielony jest na bloki 64-bitowe. Czyli jeżeli dobrze rozumiem "Ala ma kota" powinno zostać zapisana jako wartości int 64 bitowe. Czyli biorę tablice mająca 64 pozycje i wrzucam do niej a (97), w jedna komórkę, l w kolejną (108), teraz znowu a (97), spacje ignoruje, m wpisuje jako 109 itd.
Teraz mamy dokonać permutacji, ale na jakiej zasadzie.
z tego co widzę jest jakaś ustalona kolejność? Czyli najpierw 58 <- czyli to co na indexie 58-mym ma trafić na pierwsze miejsce w tablicy permutacji?
Teraz ma zostać podzielone na dwa bloki, 32-bitowe (czyli co od 0 do 31 to bd cześć pierwsza, a od 32 do 63 cześć druga?).

Teraz funkcje Feistela:
bity klucza są przesuwane, a następnie wybieranych jest 48 z 56 bitów klucza - nie do końca rozumiem tę procedurę. Jeżeli mój klucz tekstowy to "test" to co ja mam z nim właściwie zrobić?
prawa część danych rozszerzana jest do 48-bitów za pomocą permutacji rozszerzonej - a to? Permutacja rozszerzona pokazuje wartości 32 1 2 3 itd
czyli co pierwszy element tablicy to ma być 32-gi starej?
rozszerzona prawa połowa jest sumowana modulo 2 z wybranymi wcześniej (i przesuniętymi) 48 bitami klucza - no tu chyba nawet koncepcji nie mam.
Eh no dalej nie ma co pisać bo się totalnie gubię nie rozumiem.
Tu moja prośba mógłby ktoś podrzucić jakiś przykład, na nim wytłumaczyć, albo wytłumaczył to jakoś jak laikowi, albo podrzucie tematy, które muszę poczytać by to ogarnąć proszę. Mam wrażenie, że to jest dość proste tylko jakoś nie potrafię tego zrozumieć, zbyt ograniczony jestem, za duże braki mam.

spacje ignoruje

xD Tak, a potem zgadniesz gdzie były? Czy ty jesteś poważny? Spacja to znak jak każdy inny.

z tego co widzę jest jakaś ustalona kolejność

Tak, to jest po prostu s-box, nic więcej.

Jeżeli mój klucz tekstowy to "test" to co ja mam z nim właściwie zrobić?

W normalnym życiu należy użyć jakiegoś PBKDF żeby na podstawie hasła wygenerować klucz kryptograficzny. Użycie jakiegoś slowa jak twój test to BARDZO zły pomysł, bo sam widzisz ze twoje hasło ma tylko 4 znaki (więc jest brutowalne trywialnie) i jeszcze bardzo mało entropii (bo to tylko literki).

rozszerzona prawa połowa jest sumowana modulo 2 z wybranymi wcześniej (i przesuniętymi) 48 bitami klucza - no tu chyba nawet koncepcji nie mam.

To jest zwykły XOR, nic więcej.

Może znajdź sobie przykładową implementacje i przeanalizuj? Albo zmień projekt na coś łatwiejszego, jak RSA albo chociaż Salsa/Chacha, albo może nawet od biedy AES.

xD Tak, a potem zgadniesz gdzie były? Czy ty jesteś poważny? Spacja to znak jak każdy inny.

Nie, przepraszam, może byłem zbyt mało precyzyjny. Poprzednie programy jakie napisałem to było szyfrowanie Cezara, szyfr Vigenera, szyfr afiniczny, szyfr playfair. W kazdym z tych kodów nie kodowałem spacji. Po prostu zapamiętywałem miejsca sobie gdzie są, a potem gdy zakodowałem ciąg to w odpowiednich indexach wstawiałem te spacje. Nie wiem czy to dobre podejście w przypadku tego kodu, z informacji które posiadam od prowadzącego, nie widzę żadnych informacji co z spacją.

Tak, to jest po prostu s-box, nic więcej.

Dobra rozumiem, w takim razie, chyba. Dzięki!

W normalnym życiu należy użyć jakiegoś PBKDF żeby na podstawie hasła wygenerować klucz kryptograficzny. Użycie jakiegoś slowa jak twój test to BARDZO zły pomysł, bo sam widzisz ze twoje hasło ma tylko 4 znaki (więc jest brutowalne trywialnie) i jeszcze bardzo mało entropii (bo to tylko literki).>

Dobrze rozumiem, aczkolwiek chciałem po prostu najpierw to zrozumieć stąd pomysł na coś trywialnego - uznałem, że dzięki temu będzie prostsze. Jak mniemam patrząc na reakcje, nawet jeżeli ma być to tylko poglądowe działanie to i tak, nie ma to sensu ustawianie takiego trywialnego klucza.

Może znajdź sobie przykładową implementacje i przeanalizuj?

No dobra :/ posiedzę nad tym, próbowałem to wcześniej ogarnąc, ale kod który otrzymałem jako do wzoru... Średnio działał, stąd pomysł o zapytanie tutaj... No nic poszukam jeszcze, ewentualnie będę pytał :P Dzięki za odpowiedź =)

Albo zmień projekt na coś łatwiejszego, jak RSA albo chociaż Salsa/Chacha, albo może nawet od biedy AES.

1. Napisz program, który szyfruje tekst N bloków w trybie ECB i trybie CBC (Procedura szyfrowania – DES).
2. Napisz program, który szyfruje tekst N bloków w trybie CFB i trybie OFB (Procedura szyfrowania – DES).
3. Napisz program, który szyfruje tekst N bloków w trybie PCBC (Procedura szyfrowania – DES).
4. Napisz program, który szyfruje tekst N bloków w trybie CTR (Procedura szyfrowania – DES).
   To są moje 4 pozostałe możliwości wszędzie pisze o DES, nic innego nie mam do wyboru. Więć uznałem że skoro wszędzie jest procedura DES, to najłatwiej będzie napisać najpierw po prostu DES.
   Muszę napisać conajmniej 2 z tych 5 =) stąd cisnięcie DESa.

Nie wiem czy to dobre podejście w przypadku tego kodu, z informacji które posiadam od prowadzącego, nie widzę żadnych informacji co z spacją.

To są zupełnie inne, tzw klasyczne szyfry, stworzone z myślą o wykonywaniu ich ręcznie, na kartce. Szyfry komputerowe opierają sie na zupełnie innych zasadach i generalnie traktują dane jako liczby (np. dla RSA cały plaintext to jedna wielka liczba i ciphertext to też jedna wielka liczba) albo ewentualnie jako bloki bajtów różnych rozmiarów. W ogóle nie patrzy się na to co te dane "reprezentują", bo przecież możesz szyfrować nie tekst kodowany w ASCII ale np. obrazek albo video. Trudno byłoby mówić wtedy o czymś takim jak spacja w treści ;)

Dobrze rozumiem, aczkolwiek chciałem po prostu najpierw to zrozumieć stąd pomysł na coś trywialnego

Jak chcesz trywialnie, to możesz zawsze dodać sobie padding, np. uzupełnić brakujące bajty zerami albo dać jakieś PKCS2, ale generalnie tak sie nie robi. Nadal słabym, ale juz bardziej ludzkim rozwiązaniem byłoby np. policzyć hash z tego twojego hasła i użyć tego hasha jako klucza szyfrującego. Czyli liczysz jakieś md5 czy sha, obcinasz tyle bajtów ile ci potrzeba i voila. Hashe mają to do siebie że rozkład bitów jest dość losowy, więc nie da się trywialnie tego brutować inaczej niż pełnym brute-force.

Hmm ale na pewno musisz sam tego DESa implementować tutaj? Bo jeśli celem jest pokazanie jak działają różne tryby szyfru blokowego, to ten DES jest tam zupełnie nieistotny, to jest absolutny szczegół który można traktować jako black-box. Tryby działają identycznie dla dowolnego szyfru blokowego.
Ten DES to dziwny wybór, bo ani nie jest łatwy ani bezpieczny i w zasadzie nie ma specjalnie powodów żeby zmuszać kogoś do implementowania go.

Dobra trochę posiedziałem nad tym, przejrzałem inny kod napisany w JAVIE. Nawet sobie go przekopiowałem do InteliJa i puściłem debugowanie. Po popatrzeniu jak to wygląda, postanowiłem to przekonwertować na c# przepisując. Natrafiłem na problem mianowicie konwersji w pewnym momencie. Jast tam metoda hextoBin

int n = input.length() * 4;
input = Long.toBinaryString(
Long.parseUnsignedLong(input, 16));//tutaj jak mniemam zamienia nam na longa hexowego, a potem binaryString zamienia na dwójkową wartość, dziwną akcją jest że ta zamiana na longa powoduje wartość ujemną, tak jakby się wartość nie mieściła
while (input.length() < n)
    input = "0" + input;
return input;

W C#, na razie niekompletnie ale w ten sposób, no tutaj wartość parsowania na longa też wywala z minusem, ale już przekonwertowanie na binarną liczbę nie przechodzi (bo wartośc ujemna).

int n = input.Length * 4;
long l = long.Parse(input,NumberStyles.HexNumber);
input = l.ToString("D16");
input = Convert.ToUInt64(long.Parse(input, NumberStyles.HexNumber).ToString("D16"), 2).ToString("X");

Próbowałem też tak to parse'ować, ale wtedy wartość mi się totalnie nie zgadza, to co w C# totalnie inne niż wyjściowe w javie:

 input=String.Join(String.Empty,
  input.Select(
          c => Convert.ToString(Convert.ToInt32(c.ToString(), 16), 2).PadLeft(4, '0')
  ));

Trochę z tego co rozumiem w javie to działa dobrze, bo po sprintowaniu ta wartość wyświetlana ma być okay, jeżeli dobrze rozumiem.
Trochę już nie wiem, jak to zrobić żeby ten typ był okay i ta hexowa inwersja przebiegła okay. Jutro znowu poszukam, ale może ktoś ma jakieś rady? =) Coś co by przyśpieszyło... bo na razie parę h na kombinowaniu, kończąc na wyjątku że liczba ujemna.

1. Java ma tylko signed liczby stąd te dziwne ujemne wartości. Taki głupi język, nic nie poradzisz :)
2. Pisałbyś to w pythonie jak człowiek, to problemy same by znikały...
3. Za bardzo kombinujesz, masz po prostu zamienić twojego hexowego stringa na postać binarną i tyle. Nie próbuj przepisywać kodu 1:1 tylko włącz myślenie. Chcesz zrobić https://stackoverflow.com/questions/6617284/c-sharp-how-convert-large-hex-string-to-binary i tyle. Nie porównuj interpretacji tych bitów, bo jak jedna jest signed a druga unsigned to wiadomo że będą różne.

Mam wrażenie że nie bardzo rozumiesz czym są dane w komputerze. Bity to bity, bajty to bajty. One NIE niosą same z siebie zadnej informacji o semantyce. To w jaki sposób je intepreterujesz nadaje im znaczenie. Weźmy liczbę 65, można ja przedstawić jako 0x41, można jako 1000001 a można powiedzieć że to jest znak ASCII 'A'. Kto ma racje? Wszystko jest kwestia interpretacji! To są tylko bity, nic więcej. Nie ma czegoś takiego dla komputera jak ujemna liczba. Jest co najwyżej interpretacja bitów jako liczby ze znakiem.

Niestety przerasta mnie trochę sposób jego opisu choćby ten z wikipedi.

Nie czuj się źle z tego powodu, opis algorytmu na tej stronie jest do bani. Tutaj masz lepszy artykuł http://page.math.tu-berlin.de/~kant/teaching/hess/krypto-ws2006/des.htm .

Lepszego raczej nie znajdziesz, ale lepszego też nie potrzebujesz. Jasno wyszczególnione kroki, każda permutacja i przejście przez sboxy pokazane na przykładzie.

@several :D ten link co podesłałeś, jest no żeby nie powiedzieć brzydko to powiem po prostu BARDZO super pomocny <3 dziękuje, za niego, wszystko jest zrozumiałe :P. Ten tekst i przede wszystkim przykład pozwolił mi w pełni zrozumieć zasady działania. Kurcze czytając to TAK NA PRAWDĘ dopiero zrozumiałem jak bardzo ten algorytm jest odjechany =). No, ale zrozumiałem dzięki Several!
@Shalom dzięki za pomoc i rady =) udało się to napisać! Kurde, ale przekombinowałem z ta zamianą hex -> bin/ bin -> hex. Podejście do tego typu uzyskaj na koniec tą liczbę zapisaną binarnie, albo heksadecymalnie... No mega fest uprościło sprawę. Działa bardzo za rady, ultra mocno doceniam i było to bardzo pomocne. Pozwoliło mi dostrzec, nieco moją ignorancję i głupotę. Dziękuję =)

A tu dla potomnych, gdyby ktoś szukał algorytmu w C#, albo w ogóle algorytmu, to wrzuciłem to co zrobiłem na gita: https://github.com/Jarverr/DES-encrypt

Ostatnio zrobiłem sobie powtórkę z C99 i stwierdziłem, że implementacja DES może być dobrą rozgrzewką. Potem przypomniałem sobie o tym wątku.

Nie jest to zbyt optymalna binarna implementacja, ale nie ma "oszukiwania" na stringach https://github.com/pdy/des_illustrated