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

Примите и эту простую защиту персональных данных для математиков и программистов.

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

А значит, если p и E(m) взаимно просты, то есть существуют c и d, такие что c*p + d*E(m) = 1, и s = c % E(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 : (z + 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

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

UPD.
Ха-ха — судя по рейтингу статьи (-4 на 17.03.2024) — работает машинка английская…

Комментарии (4)


  1. SUNsung
    14.03.2024 19:37

    А какие еше есть асиметричные адекватные по безопасность/быстродейсвие кроме RSA собственно?


    1. dprotopopov Автор
      14.03.2024 19:37

      уже никаких, после выхода в коммерцию квантовых устройств

      ну а правительства, я так думаю, уже после 11 сентября напряглось и построило себе квантовый девайс чтобы читать всех в режиме реального времени


      1. SUNsung
        14.03.2024 19:37

        Мда. Просто мда.

        Ради общего развития почитайте за квантовые компьютеры современные. И про все их проблемы.

        Очень сильно сомневаюсь что правительство приняло закон влияюший на саму реальность, ради создания не шумяшего квантовика.

        .

        Я вообше в целом спрашивал. Есть проекты где нужна криптография и на сейчас приходится использовать rsa который не самый оптимальный по ресурсам (aes симетричный, он хорош но не для ситуаций когда нет зашитого ключа)


        1. dprotopopov Автор
          14.03.2024 19:37

          Ради общего развития почитайте за квантовые компьютеры современные

          Давно