Reverse engineering wag algorytmu PESEL Opcje

[helmutek]

Wszyscy znamy algorytm obliczania poprawności numeru np. PESEL.
Jest to suma iloczynów kolejnych cyfr z wagami im przydzielonymi.
Wynik modulo 11 i mamy sumę kontrolną.

Odwróćmy teraz sytuację, powiedzmy że nie znamy wag przydzielanych kolejnym cyfrom.
Czy jesteśmy w stanie dowiedzieć się jakie wartości przyjmują wagi mając
tylko kilkanaście/kilkadziesiąt poprawnych numerów PESEL i znając algorytm?

[kamil4u]

Nie znam się na algorytmach. Ale zastanówmy się. Mamy coś takiego:

Kod

(a*liczba + b*liczba + c*liczba + d*liczba + e*liczba)%11 = liczba
(a*liczba + b*liczba + c*liczba + d*liczba + e*liczba)%11 = liczba
(a*liczba + b*liczba + c*liczba + d*liczba + e*liczba)%11 = liczba
(a*liczba + b*liczba + c*liczba + d*liczba + e*liczba)%11 = liczba
(a*liczba + b*liczba + c*liczba + d*liczba + e*liczba)%11 = liczba

Gdyby nie %11 to byłoby zwykły układ równań, ale tak nie jest.

Uprośmy przykład i mamy:

Kod

(a*liczba + b*liczba)%11 = liczba
(a*liczba + b*liczba)%11 = liczba

Pytanie co zrobić z %11 ?
Na mój gust nie da się tego zrobić w prosty sposób. Ale, że mamy do dyspozycji komputer to możemy założyć, że mamy:

Kod

(a*liczba + b*liczba) = liczba
(a*liczba + b*liczba) = liczba

(a*liczba + b*liczba) = liczba + 1*11
(a*liczba + b*liczba) = liczba + 1*11

(a*liczba + b*liczba) = liczba + 2*11
(a*liczba + b*liczba) = liczba + 2*11

...

(a*liczba + b*liczba) = liczba + n*11
(a*liczba + b*liczba) = liczba + n*11

Pod "n" przyjmujemy jakąś sensowną liczbę, żeby wynik był realny.


Gdy wyznaczymy a i b ( = liczba ) to sprawdzamy czy wynik się zgadza dla innych PESEL-i ( = liczba + n*11 ). Jak będzie się zgadzać dla chociaż jednej wartości z n to można uznać, że a i b są wyznaczone poprawnie. I tak musi być dla wszystkich dostępnych danych . Jeżeli dla chociaż jeden wartości będzie inaczej to wyznaczamy a i b dla innej liczby ( = liczba + 11) i powtarzamy operację od nowa. Itd. ( = liczba + 11*n ) Mając sporo danych prawdopodobnie da się to zrobić.

Powtórzę, że to są jedynie moje przemyślenia, nie jestem specem od algorytmów. Pewnie da się to zrobić dużo lepiej, ale myślę, że tak też będzie działać.

Ten post edytował kamil4u 25.01.2013, 21:45:17