Жөнөкөй сандар түрүндөгү код04
26

1999-жылдын октябрь айында ошол кездеги 16 жаштагы норвегиялык Джон Лех Йохансен жетектеген топ Content Scramble System (CSS) DVD ойнотуудан коргоону айланып өтүү үчүн DeCSS программасын чыгарган. CSS DVD ойнотууну чектөө үчүн 40-биттик шифрлөөнү колдонгон, анын ачкычтары лицензияланган өндүрүүчүлөргө таратылган. Кодду таратуу АКШнын DMCA мыйзамына киргендиктен жана мыйзамдуу түрдө тыюу салынгандыктан, активисттер кодду математикалык бирдик катары жашыруунун жолдорун издешкен.

---

Андан кийин Фил Кармоди gzip декомпрессиясынан кийин экилик санда чечмеленгенде, DeCSSтин толук баштапкы кодун камтыган жөнөкөй санды түзгөн. DeCSS алгоритминин өзөгүн TypeScriptте төмөнкүдөй ишке ашырууга болот, мында биттик операциялар сектордук чечмелөө логикасын түздөн-түз чагылдырат.:

function CSSdescramble(sec: Uint8Array, key: Uint8Array): void {
    let t1: number, t2: number, t3: number, t4: number, t5: number, t6: number;
    const end = 0x800;

    t1 = (key[0] ^ sec[0x54]) | 0x100;
    t2 = key[1] ^ sec[0x55];

    const keyView = new DataView(key.buffer, key.byteOffset);
    const secView = new DataView(sec.buffer, sec.byteOffset);

    t3 = (keyView.getUint32(2, true) ^ secView.getUint32(0x56, true)) >>> 0;
    t4 = t3 & 7;
    t3 = (t3 * 2 + 8 - t4) >>> 0;

    let offset = 0x80;
    t5 = 0;

    while (offset < end) {
        t4 = CSStab2[t2] ^ CSStab3[t1];
        t2 = t1 >>> 1;
        t1 = ((t1 & 1) << 8) ^ t4;
        t4 = CSStab5[t4];
        t6 = (((((((t3 >>> 3) ^ t3) >>> 1) ^ t3) >>> 8) ^ t3) >>> 5) & 0xff;
        t3 = (((t3 << 8) >>> 0) | t6) >>> 0;
        t6 = CSStab4[t6];
        t5 += t6 + t4;

        sec[offset] = CSStab1[sec[offset]] ^ (t5 & 0xff);
        t5 >>>= 8;
        offset++;
    }
}

Жөнөкөй сандын принциби - бүтүндөй баштапкы кодду бир бүтүн сан катары чечмелөө. Бир дагы файл эч качан жөнөкөй сан болбогондуктан, сан кошумча байттар (толтуруу) менен жасалма түрдө көбөйтүлөт. Бул толтуруу Миллер-Рабин тести сыяктуу жөнөкөйлүк тести сандын жөнөкөй экенин тастыктаганга чейин циклде көбөйтүлөт. Төмөнкү генератор жогоруда сүрөттөлгөн DeCSS кодун колдонот жана тиешелүү жөнөкөй сандын көрсөтүлүшүн издейт.:

import { isPrime } from 'crypto-utils-lib'; // Hypothetical library for primality testing

async function generateIllegalPrime(code: string): Promise<bigint | null> {
    const encoder = new TextEncoder();
    const bytes = encoder.encode(code);

    let hexBase = Array.from(bytes)
        .map(b => b.toString(16).padStart(2, '0'))
        .join('');

    // Start bei 1, da 0x00 immer gerade und damit keine Primzahl ist
    for (let i = 1; i < 256; i++) {
        const candidateHex = hexBase + i.toString(16).padStart(2, '0');
        const candidateInt = BigInt('0x' + candidateHex);

        if (await isPrime(candidateInt)) {
            return candidateInt;
        }
    }
    return null;
}

const source = `void CSSdescramble(unsigned char *sec, unsigned char *key) { ... }`;
generateIllegalPrime(source).then(p => console.log(p));

Жөнөкөй сандын амалы эч качан өзүнчө сот ишинин предмети болгон эмес жана андай болушу да мүмкүн эмес болчу. Кармодинин баштапкы жөнөкөй санында 1401 орун болгону менен, ал ошол кездеги эң чоң жөнөкөй сандардын жогорку тизмелери үчүн өтө кичинекей болгон. Кийинчерээк ал ECPP рейтингинде онунчу орунду ээлөө үчүн нөл байттар менен жасалма түрдө көбөйтүлгөн 1905 орундуу версиясын түзгөн. Бул ийгилик таза математиканы цензуралоо мүмкүн эместигин көрсөттү, анткени сан тизмеде өзүнүн ордун математикалык касиеттеринин негизинде гана алган.