Часто у каждого из нас возникает желание найти похожих на себя (в профессиональном смысле), но в то же время размещение в публичных сетях своей контактной информации может породить кучу спама (ах эти древние консервы).
На помощь в этом случае приходит общее знание — образовательный ценз в профессиональной области — которое не даст воспользоваться данными «непосвящённым».
Примите и эту простую защиту персональных данных для математиков и программистов.
Вспомним одну из первых систем ассиметричного шифрования 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 (надеюсь читающие это в браузере знают как заходить в консоль)
Запускаем, проверяем, получаем
Работает машинка английская?
UPD.
Ха-ха — судя по рейтингу статьи (-4 на 17.03.2024) — работает машинка английская…
На помощь в этом случае приходит общее знание — образовательный ценз в профессиональной области — которое не даст воспользоваться данными «непосвящённым».
Примите и эту простую защиту персональных данных для математиков и программистов.
Вспомним одну из первых систем ассиметричного шифрования 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) — работает машинка английская…
SUNsung
А какие еше есть асиметричные адекватные по безопасность/быстродейсвие кроме RSA собственно?
dprotopopov Автор
уже никаких, после выхода в коммерцию квантовых устройств
ну а правительства, я так думаю, уже после 11 сентября напряглось и построило себе квантовый девайс чтобы читать всех в режиме реального времени
SUNsung
Мда. Просто мда.
Ради общего развития почитайте за квантовые компьютеры современные. И про все их проблемы.
Очень сильно сомневаюсь что правительство приняло закон влияюший на саму реальность, ради создания не шумяшего квантовика.
.
Я вообше в целом спрашивал. Есть проекты где нужна криптография и на сейчас приходится использовать rsa который не самый оптимальный по ресурсам (aes симетричный, он хорош но не для ситуаций когда нет зашитого ключа)
dprotopopov Автор
Давно