RSA Encoding
0) {
r+=s.charAt(rand(sl))
}
//status("rstring "+r)
return r
}
function key2(k) {
var l=k.length
var kl=l
var r=''
while(l--) {
r+=k.charAt((l*3)%kl)
}
return r
}
function rsaEncrypt(keylen,key,mod,text) {
// I read that rc4 with keys larger than 256 bytes doesn't significantly
// increase the level of rc4 encryption because it's sbuffer is 256 bytes
// makes sense to me, but what do i know...
status("encrypt")
if(text.length >= keylen) {
var sessionkey=rc4(rstring(text,keylen),rstring(text,keylen))
// session key must be less than mod, so mod it
sessionkey=b2t(bmod(t2b(sessionkey),t2b(mod)))
alert("sessionkey="+sessionkey)
// return the rsa encoded key and the encrypted text
// i'm double encrypting because it would seem to me to
// lessen known-plaintext attacks, but what do i know
return modexp(sessionkey,key,mod) +
rc4(key2(sessionkey),rc4(sessionkey,text))
} else {
// don't need a session key
return modexp(text,key,mod)
}
}
function rsaDecrypt(keylen,key,mod,text) {
status("decrypt")
if(text.length <= keylen) {
return modexp(text,key,mod)
} else {
// sessionkey is first keylen bytes
var sessionkey=text.substr(0,keylen)
text=text.substr(keylen)
// un-rsa the session key
sessionkey=modexp(sessionkey,key,mod)
alert("sessionkey="+sessionkey)
// double decrypt the text
return rc4(sessionkey,rc4(key2(sessionkey,text),text))
}
}
function trim2(d) { return d.substr(0,d.lastIndexOf('1')+1) }
function bgcd(u,v) { // return greatest common divisor
// algorythm from http://algo.inria.fr/banderier/Seminar/Vallee/index.html
var d, t
while(1) {
d=bsub(v,u)
//alert(v+" - "+u+" = "+d)
if(d=='0') {return u}
if(d) {
if(d.substr(-1)=='0') {
v=d.substr(0,d.lastIndexOf('1')+1) // v=(v-u)/2^val2(v-u)
} else v=d
} else {
t=v; v=u; u=t // swap u and v
}
}
}
function isPrime(p) {
var n,p1,p12,t
p1=bsub(p,'1')
t=p1.length-p1.lastIndexOf('1')
p12=trim2(p1)
for(n=0; n<2; n+=mrtest(p,p1,p12,t)) {
if(n<0) return 0
}
return 1
}
function mrtest(p,p1,p12,t) {
// Miller-Rabin test from forum.swathmore.edu/dr.math/
var n,a,u
a='1'+rstring('01',Math.floor(p.length/2)) // random a
//alert("mrtest "+p+", "+p1+", "+a+"-"+p12)
u=bmodexp(a,p12,p)
if(u=='1') {return 1}
for(n=0;n
//dg+=u+" "
if(u=='1') return -100
if(u==p1) return 1
}
return -100
}
pfactors='11100011001110101111000110001101'
// this number is 3*5*7*11*13*17*19*23*29*31*37
function prime(bits) {
// return a prime number of bits length
var p='1'+rstring('001',bits-2)+'1'
while( ! isPrime(p)) {
p=badd(p,'10'); // add 2
}
alert("p is "+p)
return p
}
function genkey(bits) {
q=prime(bits)
do {
p=q
q=prime(bits)
} while(bgcd(p,q)!='1')
p1q1=bmul(bsub(p,'1'),bsub(q,'1'))
// now we need a d, e, and an n so that:
// p1q1*n-1=de -> bmod(bsub(bmul(d,e),'1'),p1q1)='0'
// or more specifically an n so that d & p1q1 are rel prime and factor e
n='1'+rstring('001',Math.floor(bits/3)+2)
alert('n is '+n)
factorMe=badd(bmul(p1q1,n),'1')
alert('factor is '+factorMe)
//e=bgcd(factorMe,p1q1)
//alert('bgcd='+e)
e='1'
// is this always 1?
//r=bdiv(factorMe,e)
//alert('r='+r.q+" "+r.mod)
//if(r.mod != '0') {alert('Mod Error!')}
//factorMe=r.q
d=bgcd(factorMe,'11100011001110101111000110001101')
alert('d='+d)
if(d == '1' && e == '1') {alert('Factoring failed '+factorMe+' p='+p+' q='+q)}
e=bmul(e,d)
r=bdiv(factorMe,d)
d=r.q
if(r.mod != '0') {alert('Mod Error 2!')}
this.mod=b2t(bmul(p,q))
this.pub=b2t(e)
this.priv=b2t(d)
}
function status(a) { }//alert(a)}
// -->
RSA-type:
Note that long keys will likely be slow.
keylength:
How many bytes?
key:
Binary
modulo:
Binary
text:
For sample values you can use:
Public Key: 10001
Modulo: 110010100001
Private Key: 101011000001