Encryption
Revision as of 06:23, 17 August 2022 by Andr3w (talk | contribs) (→Generate public/private key pairs)
Fermat's Little Theorem
Fermat's little theorem tells us that
xp mod p = x
if p is prime for x<p
Verify this by trying prime and non-prime values for p. You can can generate prime numbers from https://bigprimes.org/
document.body.append(
mkInput('p','101'),
mkInput('m','3'),
$m('button',{onclick:function(){
document.getElementById('result').value =
pow(getbig('m'),getbig('p'),getbig('p'));
}},`m<sup>p</sup> mod p`),
$m('input',{id:'result'})
);
//raise n to the power e, modulo m
function pow(n,e,m){
if (e<=0) return 1n;
let r = pow(n,e/2n,m);
return (r*r*(e%2n===1n?n:1n))%m;
}
//Create an element with tagname and properties
//children can be a string (innerHTML) or a list of elements
function $m(tag,prop,children){
let ret = document.createElement(tag);
for(let k in prop)
ret[k] = prop[k];
if (typeof(children)==='string')
ret.innerHTML = children;
if (Array.isArray(children))
for(let c of children)
ret.append(c);
return ret;
}
//Get the value in element with id, convert it to a BigInt
function getbig(id){return BigInt(document.getElementById(id).value)}
//Return a div containing label and input. id is shown in the label
function mkInput(id,value){
return $m('div',{},[$m('label',{},id),$m('input',{id,value})]);
}
Generate public/private key pairs
document.body.append(
addHiddenInput('p','101'),
addHiddenInput('q','103'),
addInput('e','7'),
$m('button',{onclick:()=>{
$i('d').value=modInverse(gb('e'),(gb('p')-1n)*(gb('q')-1n));
$i('n').value=gb('p')*gb('q');
}},'Generate public/private key'),
addHiddenInput('d',''),
addInput('n',''),
addInput('message','123'),
$m('button',{onclick:()=>{
$i('encrypted').value=pow(gb('message'),gb('e'),gb('n'));
}},'encrypt with public key'),
addInput('encrypted',''),
$m('button',{onclick:()=>{
$i('decrypted').value=pow(gb('encrypted'),gb('d'),gb('n'));
}},'decrypt with private key'),
addInput('decrypted','')
);
function modInverse(a, m){
a = (a%m+m)%m;
if (!a||m<2n) {
return NaN // invalid input
}
// find the gcd
const s=[]
let b=m
while(b) {
[a,b] = [b,a%b]
s.push({a, b})
}
if (a!==1n) {
return NaN // inverse does not exists
}
// find the inverse
let x = 1n
let y = 0n
for(let i=s.length-2; i>=0;--i) {
[x,y] = [y,x-y*(s[i].a/s[i].b)]
}
return (y%m+m)%m
}
//Utility functions
function pow(n,e,m){
if (e<=0) return 1n;
let r = pow(n,e/2n,m);
return (r*r*(e%2n===1n?n:1n))%m;
}
function $i(id){return document.getElementById(id);}
function $m(tag,prop,children){
let ret = document.createElement(tag);
for(let k in prop)
ret[k] = prop[k];
if (typeof(children)==='string')
ret.innerHTML = children;
if (Array.isArray(children))
for(let c of children)
ret.append(c);
return ret;
}
function gb(id){return BigInt(document.getElementById(id).value)}
function addInput(id,value){
return $m('div',{},[$m('label',{},`${id} `),$m('input',{id,value})]);
}
function addHiddenInput(id,value){
return $m('div',{},[
$m('label',{},`${id} `),
$m('input',{id,value,type:'password'}),
$m('span',{onclick:()=>{$i(id).removeAttribute('type')}},' show')
]);
}
Fermat's Little Theorem
Fermat's little theorem tells us that
xp mod p = x
if p is prime for x<p
Verify this by trying prime and non-prime values for p. You can can generate prime numbers from https://bigprimes.org/
document.body.append(
mkInput('p','101'),
mkInput('m','3'),
$m('button',{onclick:function(){
document.getElementById('result').value =
pow(getbig('m'),getbig('p'),getbig('p'));
}},`m<sup>p</sup> mod p`),
$m('input',{id:'result'})
);
//raise n to the power e, modulo m
function pow(n,e,m){
if (e<=0) return 1n;
let r = pow(n,e/2n,m);
return (r*r*(e%2n===1n?n:1n))%m;
}
//Create an element with tagname and properties
//children can be a string (innerHTML) or a list of elements
function $m(tag,prop,children){
let ret = document.createElement(tag);
for(let k in prop)
ret[k] = prop[k];
if (typeof(children)==='string')
ret.innerHTML = children;
if (Array.isArray(children))
for(let c of children)
ret.append(c);
return ret;
}
//Get the value in element with id, convert it to a BigInt
function getbig(id){return BigInt(document.getElementById(id).value)}
//Return a div containing label and input. id is shown in the label
function mkInput(id,value){
return $m('div',{},[$m('label',{},id),$m('input',{id,value})]);
}
Splitting the exponent
document.body.append(
addHiddenInput('p','101'),
addHiddenInput('q','103'),
addInput('e','7'),
$m('button',{onclick:()=>{
$i('d').value=modInverse(gb('e'),(gb('p')-1n)*(gb('q')-1n));
$i('n').value=gb('p')*gb('q');
}},'Generate public/private key'),
addHiddenInput('d',''),
addInput('n',''),
addInput('message','123'),
$m('button',{onclick:()=>{
$i('encrypted').value=pow(gb('message'),gb('e'),gb('n'));
}},'encrypt with public key'),
addInput('encrypted',''),
$m('button',{onclick:()=>{
$i('decrypted').value=pow(gb('encrypted'),gb('d'),gb('n'));
}},'decrypt with private key'),
addInput('decrypted','')
);
function modInverse(a, m){
a = (a%m+m)%m;
if (!a||m<2n) {
return NaN // invalid input
}
// find the gcd
const s=[]
let b=m
while(b) {
[a,b] = [b,a%b]
s.push({a, b})
}
if (a!==1n) {
return NaN // inverse does not exists
}
// find the inverse
let x = 1n
let y = 0n
for(let i=s.length-2; i>=0;--i) {
[x,y] = [y,x-y*(s[i].a/s[i].b)]
}
return (y%m+m)%m
}
//Utility functions
function pow(n,e,m){
if (e<=0) return 1n;
let r = pow(n,e/2n,m);
return (r*r*(e%2n===1n?n:1n))%m;
}
function $i(id){return document.getElementById(id);}
function $m(tag,prop,children){
let ret = document.createElement(tag);
for(let k in prop)
ret[k] = prop[k];
if (typeof(children)==='string')
ret.innerHTML = children;
if (Array.isArray(children))
for(let c of children)
ret.append(c);
return ret;
}
function gb(id){return BigInt(document.getElementById(id).value)}
function addInput(id,value){
return $m('div',{},[$m('label',{},`${id} `),$m('input',{id,value})]);
}
function addHiddenInput(id,value){
return $m('div',{},[
$m('label',{},`${id} `),
$m('input',{id,value,type:'password'}),
$m('span',{onclick:()=>{$i(id).removeAttribute('type')}},' show')
]);
}