Кодирование простыми числами04
26

В октябре 1999 года группа во главе с тогда еще 16-летним норвежцем Йоном Лехом Йохансеном выпустила программу DeCSS , предназначенную для обхода защиты воспроизведения DVD-дисков, обеспечиваемой системой шифрования контента (CSS). CSS использовала 40-битное шифрование, ключи к которому распространялись среди лицензированных производителей, для ограничения воспроизведения DVD. Поскольку распространение кода подпадало под действие американского закона 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 цифру, оно было слишком малым для верхних строчек списков самых больших простых чисел того времени. Позже он создал версию из 1905 цифр, искусственно увеличенную за счет нулевых байтов, чтобы занять десятое место в рейтинге ECPP . Этот успех продемонстрировал невозможность цензуры чистой математики, поскольку число заслужило свое место в списке исключительно на основе своих математических свойств.

Назад