Jak zjistit způsob výpočtu kontrolní číslice (~EAN)

Ahoj, jdu prosit o radu jak reverznout výpočet kontrolní číslice...

Mám nějaký kontrolní součet a neznám způsob, jak se počítá.
Jedná se o něco jako je kontrolní číslice v EAN, výpočet je zřejmě velmi podobný.

V PHP používám na ean tohle:

    $number = strrev('12345');
   $total = 0;
   for ($i = 0, $max = strlen($number); $i < $max; $i++) {
      if (($i % 2) == 0) {
         $total += ($number[$i] * 3);
      } else {
         $total += $number[$i];
      }
   }
   $mod = ($total % 10);
   $calculated_checksum = (10 - $mod) % 10;

Neplatí omezení na 8/12 znaků, takže třeba pro 12345 je kontrolní číslice 7, pro 54 je to 3. (v případě EAN)

Příklad reálných vstupů a výstupů o které mi jde:
vstup | checksum
003 | 3
009 | 9
012 | 3
024 | 2
054 | 1

Podle prvních dvou se zdá, že není využíváno připočtení pozice aktuální číslice (jako to má např. Code128) tedy jsou to případy, kdy je dělitel vyšší, než vstup a výstupem je tedy stejné číslo jako na vstupu. Pokud by byly pozice připočítány, můžou být až 4, ale nezdá se mi to ani možné.

Vyzkoušel bruteforcovat jsem statisíce variant s růhnými změnami ve výše uvedené funkci. Násobení sudých čísel 2-100, konečné dělení do 103, připočtení 0-500 ke konečnému výsledku a spoustu podobných variant.
Neúspěšně samozřejmě...  Tam může být úplně cokoli random.
Jak to řešit lépe, než hloupým bruteforce?


Re:Jak zjistit způsob výpočtu kontrolní číslice (~EAN)
« Odpověď #1 kdy: 20. 05. 2024, 11:43:03 »
resis problem jak najit kolizi v hashovaci funkci.
a nevis ani hashovaci funkci, nevis ani jaky je vstup do funkce, znas jen vysledek.
a co kdyz se pouziva vice hashovacich funkce za sebou, co se mezi tim treba provadi s daty.
podle me to je neresitelne, nebo je to resitelne brute-force pro nejake pidi velikosti dat.


RDa

  • *****
  • 2 567
    • Zobrazit profil
    • E-mail
Re:Jak zjistit způsob výpočtu kontrolní číslice (~EAN)
« Odpověď #3 kdy: 20. 05. 2024, 13:58:21 »
Reseni bude - 1/ najit co za standart to je, pripadne 2/ se zeptat tam, kde to pouzivaji, jak to overovat, a pokud mermomoci chcete bruteforcovat, tak to udelejte treba distribuovane/verejne, zverejnenim co nejvetsiho souboru se vzorky dat

Jak uz naznacil nekdo vyse - ja bych pridal problem, ze jak vubec vite ze co jsou data a co je kontrolni cislice? (naivni predstava posledniho mista neobstoji)

Re:Jak zjistit způsob výpočtu kontrolní číslice (~EAN)
« Odpověď #4 kdy: 20. 05. 2024, 14:24:30 »
Za předpokladu, že s jistotou víš, která část jsou data a která pozice je kontrolní, ale nic dalšího, mi jako nejnadějnější přijde to nakrmit do AI a ta na to dost možná přijde.


Re:Jak zjistit způsob výpočtu kontrolní číslice (~EAN)
« Odpověď #5 kdy: 20. 05. 2024, 15:57:00 »
Jediná spolehlivá možnost je zjistit to z dokumentace. Je to vlastně varianta takových těch her, kdy se doplňují řady čísel: „Jsou dána čísla 7, 23, 6, 14, 27 – které číslo bude následovat?“ Existuje nekonečně mnoho funkcí, které vám takovouto řadu vygenerují. A i když těch řad budete mít víc, nijak si tím nepomůžete.

Obvykle se počítá vážený součet jednotlivých znaků, ze kterého se na závěr spočítá nějaký zbytek po dělení. Pokud může vyjít víc než 9, řeší se, jestli se vyšší čísla nějak mapují, nebo zda takové číslo je celé neplatné. Někdy ale kontrolní číslice nemusí být jedna, nemusí být na konci apod.

Re:Jak zjistit způsob výpočtu kontrolní číslice (~EAN)
« Odpověď #6 kdy: 20. 05. 2024, 18:17:38 »
ChatGPT jsi se ptal?

Re:Jak zjistit způsob výpočtu kontrolní číslice (~EAN)
« Odpověď #7 kdy: 20. 05. 2024, 23:28:17 »
Nieco podobne som riesil v predchadzajucej praci.

Na to neexistuje ine spolahlive riesenie ako sa spytat tvorcu toho "EAN-u". Ak si aj budes mysliet, ze si na to prisiel, tak sa necuduj ak ti to napriklad prestane fungovat 1.1. nasledujuci rok.

neurlang

Re:Jak zjistit způsob výpočtu kontrolní číslice (~EAN)
« Odpověď #8 kdy: 22. 05. 2024, 14:33:11 »
Ak mas dostatocne velky dataset (kompletne pokryvajuci vsetky vstupy a vystupy), a vies ktora cislica je kontrolna, tak vytrenovanie klasifikatoru na bazi hashtronu je zalezitost minut az hodin.

Kód: [Vybrat]
package main

import "runtime"

import "github.com/neurlang/classifier/datasets"
import "github.com/neurlang/classifier/learning"

func main() {
var h learning.HyperParameters
var dataset datasets.Datamap

dataset.Init()

dataset[3] = 3
dataset[9] = 9
dataset[12] = 3
dataset[24] = 2
dataset[54] = 1

h.Threads = runtime.NumCPU()
//affects initial modulo
h.Factor = 1

// shuffle before solving attempts
h.Shuffle = true
h.Seed = true

// restart when stuck
h.DeadlineMs = 1000
h.DeadlineRetry = 3

// additional modulo reduction, affects solution size
h.Subtractor = 1

// reduce Backtracking printing on the log
h.Printer = 7

// save any solution to disk
h.InitialLimit = 99999999
h.SetLogger("solution.txt")

h.EndWhenSolved = true

h.Training(dataset)
}
priklad treningu modelu:
Kód: [Vybrat]
~/classifier/cmd/train_ean$ go mod tidy
~/classifier/cmd/train_ean$ go build
~/classifier/cmd/train_ean$ ./train_ean
[========================================] 100% SOLUTION saved! SIZE ==  8
« Poslední změna: 22. 05. 2024, 14:34:42 od neurlang »

neurlang

Re:Jak zjistit způsob výpočtu kontrolní číslice (~EAN)
« Odpověď #9 kdy: 22. 05. 2024, 15:12:10 »
Tu je priklad inferencie vysledneho modelu v PHP:

Citace
<?php

// define hashtron hash
$hash = function($n, $s, $max) {
    // Ensure the inputs are treated as unsigned 32-bit integers
    $n = $n & 0xFFFFFFFF;
    $s = $s & 0xFFFFFFFF;
    $max = $max & 0xFFFFFFFF;

    // Mixing stage, mix input with salt using subtraction
    $m = ($n - $s) & 0xFFFFFFFF;

    // Hashing stage, use xor shift with prime coefficients
    $m ^= ($m << 2) & 0xFFFFFFFF;
    $m ^= ($m << 3) & 0xFFFFFFFF;
    $m ^= ($m >> 5) & 0xFFFFFFFF;
    $m ^= ($m >> 7) & 0xFFFFFFFF;
    $m ^= ($m << 11) & 0xFFFFFFFF;
    $m ^= ($m << 13) & 0xFFFFFFFF;
    $m ^= ($m >> 17) & 0xFFFFFFFF;
    $m ^= ($m << 19) & 0xFFFFFFFF;

    // Mixing stage 2, mix input with salt using addition
    $m = ($m + $s) & 0xFFFFFFFF;

    // Modular stage using multiply-shift trick
    // Cast to 64-bit integer for multiplication
    $result = ((($m & 0xFFFFFFFF) * ($max & 0xFFFFFFFF)) >> 32) & 0xFFFFFFFF;

    return $result;
};


// define hashtron inference
$infer = function($command, $bits, $program) {
    global $hash;
    $out = 0;
   
    $programLength = count($program);
    if ($programLength == 0) {
        return $out;
    }

    for ($j = 0; $j < $bits; $j++) {
        $input = ($command & 0xFFFFFFFF) | (($j & 0xFF) << 16);

        $ss = $program[0][0];
        $maxx = $program[0][1];

        $input = $hash($input, $ss, $maxx);

        for ($i = 1; $i < $programLength; $i++) {
            $s = $program[$i][0];
            $max = $program[$i][1];
            $maxx -= $max;

            $input = $hash($input, $s, $maxx);
        }

        $input &= 1;
        if ($input != 0) {
            $out |= 1 << $j;
        }
    }

    return $out;
};

// Define the number of program bits
$programBits = 4;

// Define the program array
$program = [
    [147, 144],
    [6077, 130],
    [116, 5],
    [717, 3],
    [68479, 2],
    [565, 0],
    [15, 2],
    [143, 0]
];


echo $infer(3, $programBits, $program); echo "\n"; //3
echo $infer(9, $programBits, $program); echo "\n"; //9
echo $infer(12, $programBits, $program); echo "\n"; //3
echo $infer(24, $programBits, $program); echo "\n"; //2
echo $infer(54, $programBits, $program); echo "\n"; //1


?>
spustenie:
Kód: [Vybrat]
~/classifier/cmd/train_ean$ php infer.php
3
9
3
2
1

Re:Jak zjistit způsob enkódování (~base64
« Odpověď #10 kdy: 05. 06. 2024, 14:13:18 »
Mám podobný praktický problém:
páry řetězců jsou zde (může obsahovat i https://):
sdovolena.seznam.cz ZXl5fX43IiJ-aWJ7YmFoY2wjfmh3Y2xgI253Im1oYH15dG08Ojw6ODU1ND06IzQ4Ow
www.sauto.cz/ ZXl5fX43IiJ6enojfmx4eWIjbncibWhgfXl0bTw6PDo4NTQ8PT8jODw1
www.sbazar.cz/ ZXl5fX43IiJ6enojfm9sd2x_I253Im1oYH15dG08Ojw6ODU1Pz06Izo9NA
sreality.cz ZXl5fX43IiJ6enojfn9obGFkeXQjbncibWhgfXl0bTw6PDo4NTQ4OjUjPDs6

Zkoušel jsem base64, rot13,...  Pravdepodobně v abecedě base64 je _ zaměněné za / a asi - za +.

Re:Jak zjistit způsob enkódování (~base64
« Odpověď #11 kdy: 05. 06. 2024, 16:14:31 »
Mám podobný praktický problém:
páry řetězců jsou zde (může obsahovat i https://):
sdovolena.seznam.cz ZXl5fX43IiJ-aWJ7YmFoY2wjfmh3Y2xgI253Im1oYH15dG08Ojw6ODU1ND06IzQ4Ow
www.sauto.cz/ ZXl5fX43IiJ6enojfmx4eWIjbncibWhgfXl0bTw6PDo4NTQ8PT8jODw1
www.sbazar.cz/ ZXl5fX43IiJ6enojfm9sd2x_I253Im1oYH15dG08Ojw6ODU1Pz06Izo9NA
sreality.cz ZXl5fX43IiJ6enojfn9obGFkeXQjbncibWhgfXl0bTw6PDo4NTQ4OjUjPDs6

Zkoušel jsem base64, rot13,...  Pravdepodobně v abecedě base64 je _ zaměněné za / a asi - za +.
Ne, to je úplně jiný problém.
To kódování není žádný záměna v BASE64, je to prostě kódování base64url. Ta data uvnitř na první pohled vypadají jako nějaké binární smetí. Může to být cokoli. Náhodně vygenerovaný identifikátor, hash (asi ne, má to různé délky), zašifrovaná data…

RDa

  • *****
  • 2 567
    • Zobrazit profil
    • E-mail
Re:Jak zjistit způsob enkódování (~base64
« Odpověď #12 kdy: 05. 06. 2024, 16:26:21 »
Mám podobný praktický problém:
páry řetězců jsou zde (může obsahovat i https://):
sdovolena.seznam.cz ZXl5fX43IiJ-aWJ7YmFoY2wjfmh3Y2xgI253Im1oYH15dG08Ojw6ODU1ND06IzQ4Ow
www.sauto.cz/ ZXl5fX43IiJ6enojfmx4eWIjbncibWhgfXl0bTw6PDo4NTQ8PT8jODw1
www.sbazar.cz/ ZXl5fX43IiJ6enojfm9sd2x_I253Im1oYH15dG08Ojw6ODU1Pz06Izo9NA
sreality.cz ZXl5fX43IiJ6enojfn9obGFkeXQjbncibWhgfXl0bTw6PDo4NTQ4OjUjPDs6

Zkoušel jsem base64, rot13,...  Pravdepodobně v abecedě base64 je _ zaměněné za / a asi - za +.

To je priklad jako ze skolky, tvl

Je tam base64 s tou zamenou (kvuli transportu v url), a vevnitr je retezec, jehoz kazde pismeno je XOR 0x0D, v plaintextu tedy:

Kód: [Vybrat]
https://sdovolena.seznam.cz/`empty`1717588907.956
https://www.sauto.cz/`empty`1717589102.518
https://www.sbazar.cz/`empty`1717588207.709
https://www.sreality.cz/`empty`1717589578.167

Re:Jak zjistit způsob výpočtu encodovaného řetězce.
« Odpověď #13 kdy: 05. 06. 2024, 16:54:39 »
Dobrý fištrón, skoro mám pocit, jestli neděláte pro seznam.cz   ;D :-[ .  Chtěl jsem ještě dodat delší URL (40 znaků), kde by se to možná dalo lépe analyzovat, ale koukám není to třeba.
, ale ono to unášení URL na bcr.iva.seznam.cz se neděje vždy, i po smazání cookies. Má to asi i nějakou trvanlivost na IP adresu
  :)
Base64::urlsafe_decode64(a).chars.map {|c|(c.ord ^ 0x0D).chr}.join
date --date=@1717589511 souhlasí


A skutečně,ono to opravdu je doslova ...konecURL`empty`1717589456

Nicméně, to že prostřední část mezi fortranistickými uvozovkami  všech případech tady je emtpy, neznamená, že to tak je vždy
« Poslední změna: 05. 06. 2024, 17:04:07 od Vietnamka »

RDa

  • *****
  • 2 567
    • Zobrazit profil
    • E-mail
Re:Jak zjistit způsob výpočtu kontrolní číslice (~EAN)
« Odpověď #14 kdy: 05. 06. 2024, 18:01:13 »
@Vietnamka - onen back-tick bude oddelovac zaznamu a volba tohoto znaku je asi zamerne takova, aby se to nenachazelo v beznem payloadu (osobne bych tam dal 0x00 nebo (CR)LF ci TAB). To posledni pak muze byt nejaky cas v unixtime vcetne milisekund imho, ale to uz vidite sam. Momentalne to ma celkem od pohledu znamou hodnotu - mezi 1.4 az 1.8M.

Pro seznam nedelam ale binarni data rozebiram casto - ono staci videt urcity pattern - zde to, ze stejny prefix vede na stejny sifrovany obsah, a holt https:// pak tomu dost napomohlo - ze to bude prefixnuto jak jste predpokladal jsem vedel uz od pohledu na ty samply. Cekal jsem tedy konstantni xor klic, jen ne delky 1, to bylo az nasledne prekvapeni.