🚀 go-pugleaf

On Aug 8, 2:39 pm, "Remek" <wias...@neostrada.pl> wrote:

> mam napisać program liczący ilość kombinacji k znaków
> ze zbioru n znaków. Może to być np. hasło dostępowe do
> czegoś.[...] Jak nazywa sie omawiane zagadnienie?
> Mutacja, permutacja, wariacja ...?

Jak go zwał tak go zwał. Uczyłęm tych rzeczy na
uniwerkach, ale gdy student zadał mi podobne
pytanie ("Mamy użyć permutacji czy kombinacji?),
to opowiedziałem klasie stary dowcip żydowski:

dwóch bardzo inteligentnych przyjaciół ukończyło
biznesową szkołę z samymi najwyższymi stopniami
i wuróżnieniami, po czym założyli własny interes.
I o dziwo nie szło im. Więc za psie pieniądze sprzedali
ten interes trzeciemu kledze, głupiemu, bez wyksztalcenia.
I o dziwo, ich przyjaciel prosperował, biznes kwitł
i przynosił mu opgromne dochody. Ci dwaj wspaniele
mądrzy pytają głupiego przyjaciela:

 -- słuchaj, my jesteśmy inteligentni, wykształceni
i w ogóle cud świata, a Ty głupi. Jak to jest, że ci
tak dobre idzie.

Na co tamten:

 -- słuchajcie, wy jesteści wspaniale inteligentni
i wszystko wiecie, macie w małym palcu, a jestem
malutki, głupi, więc skromny, nie mam wielkich
wymagań - jeden procent zysku mi wystarcza,
z jednego dolara robię dwa, to wszystko, jeden
procent mnie zadawala.

Muszę z przyjemnością powiedzieć, że mój
business class docenił historyjkę, i przynajmniej
chwilowo już mnie nie męczył zbędnymi
pytaniami.

Z tego co piszesz wynika, że chodzi ci po
prostu o wszystkie funkcje z k-elementowego
zbioru, powiedzmy  {0 1 ... k-1}  w n-elementowy
zbior, powiedzmy  A,  gdzie  A jest jakimś tam
"alfabetem" czyli zbiorem znaków. Mońa też
powiedzieć (na jedno wychodzi), że rozpatrujesz
zbiór wszystkich ciągów długości  n,  o wyrazach
ze zbioru n-elementowego  A, albo że chodzi o
k-literowe napisy (słowa, strings), gdzie znowu
za alfabet służy n-elementowy zbiór znaków, A.

> Znalazłem wzór:
>
> K = n do potęgi k

Slusznie!  Dopuszczasz przy tym napisy,
w których występuje mniej niż k różnych
znaków. Powiedzmy dla  k = 10  dopuszczasz
napis:

    r r r r r r r r r r

(gdy litera  r  należy do  A).

> gdzie:
>
> K  - ilość mozliwych kombinacji
> k  - podzbiór znaków hasła
> n  - zbiór znaków jakie mamy do dyspozycji/użycia

Wyrażasz się jak ten trzeci kolega (czyli
niepoprawnie); byleś z jednego dolara robił dwa.

>
> Taki wzór jest np. tutaj:
>
> http://matma4u.akcja.pl/twierdzenia/kombinatoryka/k.htm
>
> Chodzi o ten ostatni na wariacje z powtórzeniami.
> Wg tego wzoru wychodzą
> astronomiczne liczby. Np. ilość możliwych
> kombinacji 4-ro znakowego hasła ze
> zbioru 30 znaków wychodzi 810 000,

Tak.

 > a dla 10 znakowgo to już astronomiczna
> liczba 651 044 743 906 304.
>
> Zakładając, że komputer wykona 1000 operacji
> sprawdzających na sekundę, złamanie takiego
> hasła metodą brute force zajmie mu 20 644 lata.
>
> Czy popełniam błąd w rozumowaniu?

Zdaje się, że rozpatrujesz złamanie na 100%
w takim czasie.  Ale ile czasu potrzeba, żeby
mieć szansę 5%?  Czy 5% Ci nie przeszkadza?
Wciąż daje spać spokojnie?

Ponadto naprawdę w całą sekundę dzisiejszy
komputer sprawdzi tylko 1K = 1000 przypadków,
a nie 10M?

Pozdrawiam,

    Włodek

Użytkownik "Wlodzimierz Holsztynski (Wlod)" napisał:

> opowiedziałem klasie stary dowcip żydowski:

Faktycznie stary :)

> Zdaje się, że rozpatrujesz złamanie na 100%
> w takim czasie.  Ale ile czasu potrzeba, żeby
> mieć szansę 5%?  Czy 5% Ci nie przeszkadza?
> Wciąż daje spać spokojnie?

Wydaje się, że nieprecyzyjnie opisałem problem. Nie chcę niczego łamać, lecz
upewnić się co do poprawności rozumowania, obalenia w dyskusjach różnych
mitów. A to znaczenia 128 bitowych algorytmów szyfrujących, lub "siły"
hasła, która rzekomo ma znaczenie. Trudno ludziom uwierzyć jak trudno złamać
czteroznakowe, niesłownikowe hasło. I, że to "pic" dla naiwnych. Tak
naprawdę wykorzystywane są metody zdobywania hasła, a nie jego łamanie.

> Ponadto naprawdę w całą sekundę dzisiejszy
> komputer sprawdzi tylko 1K = 1000 przypadków,
> a nie 10M?

Taką właśnie wydajność przyjąłem i wychodzi dla 8 znaków w haśle jakieś 160
tys godzin. A to po spełnieniu warunku pełnego dostępu do badanego obiektu.
W przypadku działania na odległość np. dopasowania hasła do nazwy
użytkownika na jakimś serwisie sieciowym, to w ogóle nie ma sensu.

> Pozdrawiam.

Pozdrawiam również i pięknie dziękuję za wyczerpujący wykład.

Remek

On Aug 8, 8:26 pm, "Remek" <wias...@neostrada.pl> wrote:

> Trudno ludziom uwierzyć jak trudno złamać
> czteroznakowe, niesłownikowe hasło.

(2^7)^4 = 2^28. Nawet  (2^8)^4 = 2^32 ~=~ 4*10^9
to nie jest wiele dla PC. Pierwszy administrator
sieci NeXT w Wiltel co jakiś czas puszczał program
sprawdzający hasła użytkowników. Krótkie ludziom
"odsyłał" i prosił, żeby zmienić na solidniejsze.
Jego program szedł chyba na NeXT, a NeXT do takich
rzeczy było powolne. Czyli łamać krotkie hasła
było raczej łatwo. Wiltela już nie ma, ale z owym
administratorem wciąż jestem w emailowym
kontakcie i mogę go o to zapytać, nawet o detale
(niepersonalne :-). Chciałbyś, bym to uczynił?

> Taką właśnie wydajność przyjąłem i wychodzi
> dla 8 znaków w haśle jakieś 160 tys godzin.

Osiem brzmi już solidniej :-)

Pozdrawiam raz jeszcze i zawsze serdecznie,

    Włodek

Użytkownik "Wlodzimierz Holsztynski (Wlod)" napisał:

> (2^7)^4 = 2^28. Nawet (2^8)^4 = 2^32 ~=~ 4*10^9
> to nie jest wiele dla PC.

Dla wspóczesnego PC to trochę ponad dwie godziny pracy. Niby niewiele, ale
jednak... No i trzeba mieć dostęp do bazy.

> Pierwszy administrator sieci NeXT w Wiltel co jakiś czas puszczał program
> sprawdzający hasła użytkowników. Krótkie ludziom
> "odsyłał" i prosił, żeby zmienić na solidniejsze.
> Jego program szedł chyba na NeXT, a NeXT do takich
> rzeczy było powolne. Czyli łamać krotkie hasła
> było raczej łatwo.

Jako profan matematyczny, lecz zaawansowany użytkownik komputera sądzę, że
nie sprawdzał każdego hasła przez jego "łamanie" metodą brute force. Na
ówczesnym sprzęcie "przerobienie" jednego hasła trwało by kilka godzin.
Zastosował raczej metodę oceny statystycznej (ilość znaków, najczęściej
występujące słowa, imię, lub nazwisko wspak itp.)

> z owym administratorem wciąż jestem w emailowym
> kontakcie i mogę go o to zapytać, nawet o detale
> (niepersonalne :-). Chciałbyś, bym to uczynił?

Bardzo proszę. Jestem niezmiernie ciekaw stosowanej wówczas metody.

> Pozdrawiam raz jeszcze i zawsze serdecznie.


Pozdrawiam  Remek

On Aug 9, 8:22 am, "Remek" <wias...@neostrada.pl> wrote:


> [...] sądzę, że nie sprawdzał każdego hasła przez
> jego "łamanie" metodą brute force. Na
> ówczesnym sprzęcie "przerobienie" jednego hasła
> trwało by kilka godzin.

Zwłaszcza, że miał w sieci ponad 100 stacji.

> Zastosował raczej metodę oceny statystycznej (ilość
> znaków, najczęściej występujące słowa, imię, lub
> nazwisko wspak itp.)

Coś mi chodzi po głowie, że masz rację.
Zresztą doradzają unikania słów ze słownika,
oraz proponują (czasem systemy nawet wymuszają)
używanie i liter i cyfr, jak w "ur70im20".

>
> > z owym administratorem wciąż jestem w emailowym
> > kontakcie i mogę go o to zapytać, nawet o detale
> > (niepersonalne :-). Chciałbyś, bym to uczynił?
>
> Bardzo proszę. Jestem niezmiernie ciekaw stosowanej
> wówczas metody.

Zapytam.

W MM wielokrotnie proponowałem (nieformalnie chyba,
"na korytarzu") stosowanie GAPP do kodowania. Wtedy
klucz może mieć z łatwością setki tysięcy bitów, a
kodowanie i dekodowanie jest przy tym prościutkie
i super szybkie. Takie kodowanie jest praktycznie
nie do złamania. Ogólnie, łatwo o kodowanie virtualnie
nie do złamania, ale trudno, żeby dawało prosty i szybki
system. W danym przypadku ceną jest posiadanie GAPP.
Jednak należy uzbrajać PC w niewielki GAPP. Dziś
wystarczy dodać jedną kość w tanich systemach, lub
cztery w drogich. Nawet 10 lat temu, może 12, mieli
kości GAPP z 32x32 = 1024 komórkami, każda miałą
1024 bity własnej pamięci. Tylko brakiem rozpowszechnionej
wiedzy o algorytmach typu GAPP można wytłumaczyć
znikome istnienie GAPP, prawie żadne (a inne komercjalne
geometryczne SIMD ponoć w ogóle znikły).

Pozdrawiam,

    Włodek

Użytkownik "Wlodzimierz Holsztynski (Wlod)" napisał:

> Ponadto naprawdę w całą sekundę dzisiejszy
> komputer sprawdzi tylko 1K = 1000 przypadków,
> a nie 10M?

Przepraszam za brak refleksu. Nie dopatrzyłem się pytajnika. Czytnik tak mi
przełamał wiersze, że nie zrozumiałem treści. Do meritum.

Zakładamy, że bazę mamy na swoim dysku. Program sprawdzający zgodność hasła
musi kolejno wywoływać funkcje:

    call wygeneruj_haslo         -  1 cykl
    wykonanie funkcji            -  5 cykli
    zapisz hasło do zmiennej     -  1 cykl
    call funkcja_sprawdzająca    - 10 cykli
    spawdź wynik (good/bad)      -  1 cykl
    skok zależny od wyniku
   (na początek pętli, lub
    kończymy i podajemy
    prawidłowe hasło)            -  1 cykl

Czyli załózmy 20 taktów zegara, co dla przeciętnego procesora 1,6 GHZ daje
wynik ok. 80 tys operacji na sekundę.  Oczywiście przy założeniu
zastosowania wydajnych/szybkich algorytmów. Ma to znaczenie dla haseł
kilkuznakowych, bo czy złamane ono zostanie w 10 godzin, czy kilkanaście
sekund będzie istotne. Natomiast to czy PC będzie szukła wieloznakowego
hasła 1000 lat, czy "tylko" rok, to juz ma mniejsze znaczenie :)

Chciałbym zaznaczyć, że ilość instrukcji obliczyłem baaardzo optymistycznie.
W rzeczywistości będzie ich więcej, bo niektórych w kodzie nie widać.
Procesor wywołując funkcję, odkłada jej adres na stos. Jeśli funkcja jest
wieloargumentowa, to w trakcie jej uruchamiania zdejmowane są adresy
zmiennych i inne wartości. W trakcie powrotu z funkcji trzeba wyrównać ramkę
stosu... Itd. itp. Tak, że czas wykonania nieco się wydłuży, ale chyba
zmieścimy się w przyzwoitych granicach.

Pozdrawiam  Remek

Użytkownik "Remek" <wiasmed@neostrada.pl> napisał w wiadomości 
news:h5krai$504$2@inews.gazeta.pl...
> Witam
>
> Przepraszam za trywialne pytanie, ale w sieci jest dużo niekompetentnych
> artykułów na ten temat i trudno znaleźć jednoznaczna odpowiedź. Otóż mam
> napisać program liczący ilość kombinacji k znaków ze zbioru n znaków. Może
> to być np. hasło dostępowe do czegoś. Znaki w hasle mogą powtarzać się
> dowolną ilość razy. Znalazłem troche materiałów, ale trudo sie w nich
> poruszać bez ugruntowanej wiedzy. Jak nazywa sie omawiane zagadnienie?
> Mutacja, permutacja, wariacja ...?

Klucz do oznaczania "-acji"

1. Czy zadanie polega na wybieraniu elementów z większego zbioru?
T -> Idz do pkt 2.
N -> Czy w zadaniu jest coś w rodzaju "na ile sposobów...?" Pewnie chodzi o 
permutacje. Jeśli nie to możliwe, ze nie chodzi nawet o zagadnienie 
kombinatoryczne

2. Czy istotna jest kolejność wybieranych elementów?
T -> Wariacja - idz do punktu 3.
N -> Kombinacja  idż do punktu 4.

3. Czy wybierane elementy mogą się powtarzać?
T -> Wariacja z powtórzeniami
N -> Wariacja bez powtórzeń

3. Czy wybierane elementy mogą się powtarzać?
T -> Kombinacja z powtórzeniami
N -> Kombinacja bez powtórzeń

Twoje zagadnienie zgodnie z tym kluczem określone jest więc jako wariacja z 
powtórzeniami.

pozdr
dK