Kodo en primoj04
26

En oktobro 1999, grupo gvidata de la tiama 16-jaraĝa norvego Jon Lech Johansen publikigis la programon DeCSS por eviti la protekton kontraŭ DVD-reludigo de la Sistemo de Enhavo Miksita (CSS). CSS uzis 40-bitan ĉifradon, kies ŝlosiloj estis distribuitaj al rajtigitaj fabrikantoj, por limigi DVD-reludigon. Ĉar la distribuado de la kodo falis sub la usona DMCA kaj estis laŭleĝe malpermesita, aktivuloj serĉis manierojn alivesti la kodon kiel matematikan enton.

---

Phil Carmody tiam konstruis primon kiu, kiam interpretita duume post gzip-malkunpremo, enhavas la kompletan fontkodon de DeCSS. La kerno de la DeCSS-algoritmo povas esti efektivigita en TypeScript jene, kie la bitaj operacioj rekte mapas la sektoran malĉifran logikon.:

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++;
    }
}

La principo malantaŭ la primo estas interpreti la tutan fontkodon kiel unuopan, solidan entjeron. Ĉar neniu donita dosiero iam estas primo, la nombro estas artefarite pliigita per aldonaj bajtoj (plenigo). Ĉi tiu plenigo estas pliigita en buklo ĝis primeco-testo, kiel ekzemple la testo de Miller-Rabin, konfirmas, ke la nombro estas primo. La sekva generatoro uzas la DeCSS-kodon priskribitan supre kaj serĉas korespondan primnombran reprezentaĵon.:

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));

La truko pri primaj nombroj neniam estis la temo de aparta kortuma kazo, nek necesis. Kvankam la originala primo de Carmody havis 1401 ciferojn, ĝi estis tro malgranda por la supraj listoj de la plej grandaj primoj tiutempe. Li poste kreis 1905-ciferan version, artefarite ŝveligitan per nulaj bajtoj, por atingi la dekan lokon en la ECPP-rangotabelo . Ĉi tiu sukceso montris la neeblecon cenzuri puran matematikon, ĉar la nombro gajnis sian lokon en la listo nur surbaze de siaj matematikaj ecoj.