Difference between revisions of "Encryption"

From ProgZoo
Jump to navigation Jump to search
Line 50: Line 50:
   addInput('q','103'),
   addInput('q','103'),
   addInput('e','3'),
   addInput('e','3'),
   $m('button',{},'Generate public/private key'),
   $m('button',{onclick:()=>{
    $i('n').value=gb('p')*gb('q');
  }},'Generate public/private key'),
   addInput('d',''),
   addInput('d',''),
   addInput('n','')
   addInput('n','')
Line 85: Line 87:
   return (r*r*(e%2n===1n?n:1n))%m;
   return (r*r*(e%2n===1n?n:1n))%m;
}
}
 
function $i(id){return document.getElementById(id);}
function $m(tag,prop,children){
function $m(tag,prop,children){
   let ret = document.createElement(tag);
   let ret = document.createElement(tag);
Line 97: Line 99:
   return ret;
   return ret;
}
}
function getbig(id){return BigInt(document.getElementById(id).value)}
function gb(id){return BigInt(document.getElementById(id).value)}
function addInput(id,value){
function addInput(id,value){
   return $m('div',{},[$m('label',{},`${id} `),$m('input',{id,value})]);   
   return $m('div',{},[$m('label',{},`${id} `),$m('input',{id,value})]);   
}
}
</pre>
</pre>
</div>
</div>

Revision as of 22:36, 19 September 2021


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(
  addInput('p','101'),
  addInput('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'})
);

//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 $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 getbig(id){return BigInt(document.getElementById(id).value)}
function addInput(id,value){
  return $m('div',{},[$m('label',{},id),$m('input',{id,value})]);  
}

Generate public/private key pairs

document.body.append(
  addInput('p','101'),
  addInput('q','103'),
  addInput('e','3'),
  $m('button',{onclick:()=>{
    $i('n').value=gb('p')*gb('q');
  }},'Generate public/private key'),
  addInput('d',''),
  addInput('n','')
);


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})]);  
}