Encryption

1) 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/

Input

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

xxxxxxxxxx

 

1

document.body.append(

2

  addInput('p','101'),

3

  addInput('m','3'),

4

  $m('button',{onclick:function(){

5

    document.getElementById('result').value =

6

      pow(getbig('m'),getbig('p'),getbig('p'));

7

  }},`m<sup>p</sup> mod p`),

8

  $m('input',{id:'result'})

9

);

10

​

11

//Utility functions

12

function pow(n,e,m){

13

  if (e<=0) return 1n;

14

  let r = pow(n,e/2n,m);

15

  return (r*r*(e%2n===1n?n:1n))%m;

16

}

17

​

18

function $m(tag,prop,children){

19

  let ret = document.createElement(tag);

20

  for(let k in prop)

21

    ret[k] = prop[k];

22

  if (typeof(children)==='string')

23

    ret.innerHTML = children;

24

  if (Array.isArray(children))

25

    for(let c of children)

26

      ret.append(c);

27

  return ret;

28

}

29

function getbig(id){return BigInt(document.getElementById(id).value)}

30

function addInput(id,value){

31

  return $m('div',{},[$m('label',{},id),$m('input',{id,value})]);  

32

}

33

​

Go reset

Output

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

2) Generate public/private key pairs

Input

document.body.append( addInput('p','101'), addInput('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'), addInput('d',''), addInput('n',''), addInput('message','123'), $m('button',{onclick:()=>{ $i('encrypted').value=pow(gb('message'),gb('e'),gb('m')); }},'encrypt with public key'), addInput('encrypted',''), ); 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})]); }

xxxxxxxxxx

 

1

document.body.append(

2

  addInput('p','101'),

3

  addInput('q','103'),

4

  addInput('e','7'),

5

  $m('button',{onclick:()=>{

6

    $i('d').value=modInverse(gb('e'),(gb('p')-1n)*(gb('q')-1n));

7

    $i('n').value=gb('p')*gb('q');

8

  }},'Generate public/private key'),

9

  addInput('d',''),

10

  addInput('n',''),

11

  addInput('message','123'),

12

  $m('button',{onclick:()=>{

13

    $i('encrypted').value=pow(gb('message'),gb('e'),gb('m'));

14

  }},'encrypt with public key'),

15

  addInput('encrypted',''),

16

);

17

​

18

​

19

function modInverse(a, m){

Go reset

Output

document.body.append(
  addInput('p','101'),
  addInput('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'),
  addInput('d',''),
  addInput('n',''),
  addInput('message','123'),
  $m('button',{onclick:()=>{
    $i('encrypted').value=pow(gb('message'),gb('e'),gb('m'));
  }},'encrypt with public key'),
  addInput('encrypted',''),
);


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