Птицу узнают по оперению… или профзащита от спама14.03.2024 21:00

Часто у каждого из нас возникает желание найти похожих на себя (в профессиональном смысле), но в то же время размещение в публичных сетях своей контактной информации может породить кучу спама (ах эти древние консервы).
На помощь в этом случае приходит общее знание — образовательный ценз в профессиональной области — которое не даст воспользоваться данными «непосвящённым».

Примите и эту простую защиту персональных данных для математиков и программистов.
Вспомним одну из первых систем ассиметричного шифрования RSA — что лежит в её основе?
Простой факт:
если для числа m известно значение функции Эйлера E (m),
то для любого a!= 0 выполняется a ^ E (m) % m = 1

А значит, если p и E (m) взаимно просты, то есть существуют c и d, такие что c*p + d*E (m) = 1, и s = c % m
то для любого a из [0, m) выполняется a ^ (s*p) % m = a

Воспользуемся этим.
Набросаем программку на js (надеюсь читающие это в браузере знают как заходить в консоль)

function split(x) {
    for (let i = 2n; i * i <= x; i++) {
        let j = x / i;
        if (i * j == x) return [i, j];
    }
}

function toPrimes(x) {
    let arr = [x];
    let primes = [];
    while (arr.length > 0) {
        let x = arr.pop();
        let s = split(x);
        if (s) s.forEach(y => arr.push(y));
        else primes.push(x);
    }
    primes.sort((a, b) => a < b ? -1 : a > b ? 1 : 0);
    return primes;
}

function euler(p) {
    let z = 1n;
    let map = new Map();

    p.forEach(x => {
        let value = 0n;
        if (map.has(x)) { value = map.get(x); map.delete(x); }
        value++;
        map.set(x, value);
    });
    for (let [key, value] of map.entries()) {
        z *= pow(key, value) - 1n;
    }
    return z;
}

function xgcd(a, b) {
    if (!b) return [1n, 0n];
    let [c, d] = xgcd(b, a % b);
    let q = a / b;
    return [d, c - d * q];
}

function pow(x, y) {
    if (!y) return 1n;
    let h = y / 2n;
    let z = pow(x, h);
    let r = (z * z);
    if (y % 2n) r = (r * x);
    return r;
}

function powmod(x, y, m) {
    if (!y) return 1n;
    let h = y / 2n;
    let z = powmod(x, h, m);
    let r = (z * z) % m;
    if (y % 2n) r = (r * x) % m;
    return r;
}

let p = 3n;
let q = 13n;
let m = pow(10n, q) + 1n;

let primes = toPrimes(m);
let z = euler(primes);
let primes2 = toPrimes(z);
while (primes2.find(x => x == p)) p += 2n;
let [c, d] = xgcd(p, z);

let s = c >= 0n ? c : (m + c);

function get(x) {
    let t = powmod(x, s, m);
    console.log(`(${t} ^ ${p}) % (10 ^ ${q} + 1) =`, powmod(t, p, m));
}

get(81234567890n);

Запускаем, проверяем, получаем

(275491122648 ^ 7) % (10 ^ 13 + 1) = 81234567890n

Работает машинка английская?

© Habrahabr.ru