Difference between revisions of "Encryption"

From ProgZoo
Jump to navigation Jump to search
Tag: Reverted
 
(30 intermediate revisions by the same user not shown)
Line 1: Line 1:
<pre id='shellbody' data-qtp='DOM'></pre>
<pre id='shellbody' data-qtp='DOM'></pre>
==Fermat's Little Theorem==
==Fermat's Little Theorem==
<div class='qu'>
<div class='qu' data-width=300>
Fermat's little theorem tells us that
x<sup>p</sup> mod p = x
if <code>p</code> is prime for <code>x<p</code>
 
Verify this by trying prime and non-prime values for p. You can can generate prime numbers from https://bigprimes.org/
<pre class='usr'>
<pre class='usr'>
document.body.append(
document.body.append(
   addInput('p','101'),
   mkInput('p','101'),
   addInput('m','3'),
   mkInput('m','3'),
   $m('button',{onclick:function(){
   $m('button',{onclick:function(){
     document.getElementById('result').value =
     document.getElementById('result').value =
Line 13: Line 18:
);
);


//Utility functions
//raise n to the power e, modulo m
function pow(n,e,m){
function pow(n,e,m){
    if (e<=0) return 1n;
  if (e<=0) return 1n;
    let h = e/2n;
  let r = pow(n,e/2n,m);
    let r = pow(n,h,m);
  return (r*r*(e%2n===1n?n:1n))%m;
    r = (r*r) % m;
    if (% 2n === 1n){
        return (n * r) % m;
    }
    return r;
}
}


//Create an element with tagname and properties
//children can be a string (innerHTML) or a list of elements
function $m(tag,prop,children){
function $m(tag,prop,children){
   let ret = document.createElement(tag);
   let ret = document.createElement(tag);
Line 36: Line 38:
   return ret;
   return ret;
}
}
//Get the value in element with id, convert it to a BigInt
function getbig(id){return BigInt(document.getElementById(id).value)}
function getbig(id){return BigInt(document.getElementById(id).value)}
function addInput(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})]);   
   return $m('div',{},[$m('label',{},id),$m('input',{id,value})]);   
}
}
</pre>
</pre>
<pre class=ans><pre>
</div>
</div>


<div class=qu>
==Generate public/private key pairs==
<div class=qu data-width=500 data-height=250>
<pre class=usr>
<pre class=usr>
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')
  ]);
}
</pre>
</div>
<pre id='shellbody' data-qtp='DOM'></pre>
==Splitting the exponent==
<div class='qu' data-width=300 data-height=500>
Fermat's little theorem tells us that
x<sup>p</sup> mod p = x
if <code>p</code> is prime for <code>x<p</code>
Verify this by trying prime and non-prime values for p. You can can generate prime numbers from https://bigprimes.org/
<pre class='usr'>
document.body.append(
  mkInput('p','1000000007'),
  mkInput('scramble','112233'),
  $m('button',{onclick:()=>{
    document.getElementById('unscramble').value =
      modInverse(getbig('scramble'),getbig('p')-1n);
  }},'calculate unscramble'),
  mkInput('unscramble',''),
  mkInput('secret','888'),
  $m('button',{onclick:function(){
    document.getElementById('scrambled').value =
      pow(getbig('secret'),getbig('scramble'),getbig('p'));
  }},`scramble secret`),
  mkInput('scrambled',''),
  $m('button',{onclick:function(){
    document.getElementById('tada').value =
      pow(getbig('scrambled'),getbig('unscramble'),getbig('p'));
  }},`unscramble scrambled`),
  mkInput('tada','')
);
//raise n to the power e, modulo m
function pow(n,e,m){
function pow(n,e,m){
    if (e<=0) return 1n;
  if (e<=0) return 1n;
    let h = e/2n;
  let r = pow(n,e/2n,m);
    let r = pow(n,h,m);
  return (r*r*(e%2n===1n?n:1n))%m;
    r = (r*r) % m;
    if (e % 2n === 1n){
        return (n * r) % m;
    }
    return r;
}
}


function modInverse(a, m){
function modInverse(a, m){
   a = (a % m + m) % m
   a = (a%m+m)%m;
   if (!a || m < 2n) {
   if (!a||m<2n) {
     return NaN // invalid input
     return NaN // invalid input
   }
   }
   // find the gcd
   // find the gcd
   const s = []
   const s=[]
   let b = m
   let b=m
   while(b) {
   while(b) {
     [a, b] = [b, a % b]
     [a,b] = [b,a%b]
     s.push({a, b})
     s.push({a, b})
   }
   }
   if (a !== 1n) {
   if (a!==1n) {
     return NaN // inverse does not exists
     return NaN // inverse does not exists
   }
   }
Line 75: Line 183:
   let x = 1n
   let x = 1n
   let y = 0n
   let y = 0n
   for(let i = s.length - 2; i >= 0; --i) {
   for(let i=s.length-2; i>=0;--i) {
     [x, y] = [y, x - y * (s[i].a / s[i].b)]
     [x,y] = [y,x-y*(s[i].a/s[i].b)]
   }
   }
   return (y % m + m) % m
   return (y%m+m)%m
}
}
let getbig = id => BigInt(document.getElementById(id).value);
 
let addInput = (id,value) => {
//Create an element with tagname and properties
//children can be a string (innerHTML) or a list of elements
const $i = document.getElementById;
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})]);   
   return $m('div',{},[$m('label',{},id),$m('input',{id,value})]);   
}
}
document.body.append(addInput('p','101'),addInput('q','103'));
</pre>
</pre>
</div>
</div>

Latest revision as of 22:20, 17 August 2022


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



Splitting the exponent

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','1000000007'),
  mkInput('scramble','112233'),
  $m('button',{onclick:()=>{
    document.getElementById('unscramble').value = 
      modInverse(getbig('scramble'),getbig('p')-1n);
  }},'calculate unscramble'),
  mkInput('unscramble',''),
  mkInput('secret','888'),
  $m('button',{onclick:function(){
    document.getElementById('scrambled').value =
      pow(getbig('secret'),getbig('scramble'),getbig('p'));
  }},`scramble secret`),
  mkInput('scrambled',''),
  $m('button',{onclick:function(){
    document.getElementById('tada').value =
      pow(getbig('scrambled'),getbig('unscramble'),getbig('p'));
  }},`unscramble scrambled`),
  mkInput('tada','')
);

//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;
}

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
}

//Create an element with tagname and properties
//children can be a string (innerHTML) or a list of elements
const $i = document.getElementById;
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})]);  
}