Encryption - Revision history

Andr3w: /* Splitting the exponent */

2022-08-17T22:20:17Z

Splitting the exponent

← Older revision		Revision as of 22:20, 17 August 2022
Line 130:		Line 130:
	<pre id='shellbody' data-qtp='DOM'></pre>		<pre id='shellbody' data-qtp='DOM'></pre>
	==Splitting the exponent==		==Splitting the exponent==
	<div class='qu' data-width=300>		<div class='qu' data-width=300 data-height=500>
	Fermat's little theorem tells us that		Fermat's little theorem tells us that
	x<sup>p</sup> mod p = x		x<sup>p</sup> mod p = x

2022-08-17T22:19:53Z

Splitting the exponent

← Older revision		Revision as of 22:19, 17 August 2022
Line 138:		Line 138:
	<pre class='usr'>		<pre class='usr'>
	document.body.append(		document.body.append(
	mkInput('p','~~4093082899~~'),		mkInput('p','1000000007'),
	mkInput('m','~~19620520~~'),		mkInput('scramble','112233'),
	mkInput('a','~~11223344~~'),		$m('button',{onclick:()=>{
			document.getElementById('unscramble').value =
			modInverse(getbig('scramble'),getbig('p')-1n);
			}},'calculate unscramble'),
			mkInput('unscramble',''),
			mkInput('secret','888'),
	$m('button',{onclick:function(){		$m('button',{onclick:function(){
	document.getElementById('b').value =		document.getElementById('scrambled').value =
	~~modInverse~~(getbig('a'),getbig('p'));		pow(getbig('secret'),getbig('scramble'),getbig('p'));
	}},`~~inverse of a mod p~~`),		}},`scramble secret`),
	$m('~~input~~',{id:'~~result~~'}),		mkInput('scrambled',''),
	mkInput('b',''),		$m('button',{onclick:function(){
			document.getElementById('tada').value =
			pow(getbig('scrambled'),getbig('unscramble'),getbig('p'));
			}},`unscramble scrambled`),
			mkInput('tada','')
	);		);

Line 182:		Line 191:
	//Create an element with tagname and properties		//Create an element with tagname and properties
	//children can be a string (innerHTML) or a list of elements		//children can be a string (innerHTML) or a list of elements
			const $i = document.getElementById;
	function $m(tag,prop,children){		function $m(tag,prop,children){
	let ret = document.createElement(tag);		let ret = document.createElement(tag);

2022-08-17T06:30:07Z

Splitting the exponent

2022-08-17T06:29:42Z

Splitting the exponent

2022-08-17T06:28:59Z

Fermat's Little Theorem

← Older revision		Revision as of 06:28, 17 August 2022
Line 129:		Line 129:

	<pre id='shellbody' data-qtp='DOM'></pre>		<pre id='shellbody' data-qtp='DOM'></pre>
	==~~Fermat's Little Theorem~~==		==Splitting the exponent==
	<div class='qu' data-width=300>		<div class='qu' data-width=300>
	Fermat's little theorem tells us that		Fermat's little theorem tells us that
Line 138:		Line 138:
	<pre class='usr'>		<pre class='usr'>
	document.body.append(		document.body.append(
	mkInput('p','~~101~~'),		mkInput('p','4093082899'),
	mkInput('m','3'),		mkInput('m','19620520'),
			mkInput('a','11223344'),
	$m('button',{onclick:function(){		$m('button',{onclick:function(){
	document.getElementById('~~result~~').value =		document.getElementById('b').value =
	~~pow~~(getbig('~~m'),getbig('p~~'),getbig('p'));		modInverse(getbig('a'),getbig('p'));
	}},`~~m<sup>p</sup>~~ mod p`),		}},`inverse of a mod p`),
	$m('input',{id:'result'})		$m('input',{id:'result'})
			mkInput('b',''),
	);		);

Line 152:		Line 154:
	let r = pow(n,e/2n,m);		let r = pow(n,e/2n,m);
	return (rr(e%2n===1n?n:1n))%m;		return (rr(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
	}		}

2022-08-17T06:23:26Z

Splitting the exponent

@@ Line 172: / Line 172: @@
 function mkInput(id,value){
    return $m('div',{},[$m('label',{},id),$m('input',{id,value})]);
+}
 </pre>
 </div>

2022-08-17T06:23:04Z

Generate public/private key pairs

@@ Line 48: / Line 48: @@
 ==Generate public/private key pairs==
 <div class=qu data-width=500 data-height=250>
 <pre class=usr>

2021-09-26T19:58:06Z

Fermat's Little Theorem

← Older revision		Revision as of 19:58, 26 September 2021
Line 18:		Line 18:
	);		);

	// raise n to the power e, modulo m		//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;
Line 26:		Line 26:

	//Create an element with tagname and properties		//Create an element with tagname and properties
	//~~Children~~ can be a string (innerHTML) or a list of elements		//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);

2021-09-26T19:57:14Z

Fermat's Little Theorem

2021-09-26T19:51:55Z

Fermat's Little Theorem

← Older revision		Revision as of 19:51, 26 September 2021
Line 9:		Line 9:
	<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 19:		Line 19:

	//Utility functions		//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;
Line 25:		Line 27:
	}		}

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