Cryptography Implementation Discussion

[Ipquarx]

If I can manage to interpret the python code you linked to earlier which uses ECC and actually works then I might just be able to translate the code. It uses a lot of the mod function, so lug if you would be so kind as to test out that function for some really big numbers, like, 2^400-1 mod 2^399-3 and see how it compares to the divide-multiply method?

[Ad Bot]

[Lugnut]

i'll check it out in a bit

[Lugnut]

echo(Math_Mod(Math_Pow("52","52"), 5));

blockland has been locked up and not responding for about a minute now

edit: stuff, typed it wrong.

echo(Math_Mod(Math_Pow("52","52")), 5);[/t] isn't even designed to work

[Lugnut]

okay now that i figured out what the forget i'm doing

echo(Math_Mod(Math_Subtract(Math_Pow("2","400"), "1"), Math_Subtract(Math_Pow("2","399"), "1"));
gives back "1" in less than a tenth of a second - blockland doesn't even stutter.

that's not even doing something like
$a = Math_Subtract(Math_Pow("2", "400"), "1");
$b = Math_Subtract(Math_Pow("2", "399"), "1");
echo(Math_Mod($a, $b));
which would undoubtedly be even faster

[Lugnut]

ok so i played with different numbers, then i implemented the fastExpMod (the python squaring modulus thing i found in the PyECC thing) and played with it for a bit - it's pretty fast, but it's around 3-4 seconds of freeze if you have numbers like

Math_fastExpMod("501982476978698273937623", "509820983609", "123567882237");

going into it.
on that note, modulo works, the fastExpMod thing works, now just make them work on schedule loops, which will slow them down tremendously, but it will still work, ideally without lagging too badly

or we could like, just be lazy, and just toss it all together, make sure it works with the numbers, then make it work well.


oh and i pushed stuff to the repo.

[Ipquarx]

I added more optimizations to the method to make it ~2x faster in most cases.

random 150 digit number mod another random 150 digit number is instantaneous with new mod, and old mod takes ~700ms
random 150 digit number mod random 100 digit number takes ~550ms with new mod, old mod again takes ~700ms
random 150 digit number mod random 20 digit number takes ~1.1s with new mod, and ~1.4s with old mod.

So now new mod is always faster than old mod. Wonderful.

I'll just add in handling for numbers that torque can actually mod with and that'll be set to go.

New code:

Code: [Select]

function Math_Mod(%a, %b)
{
%x = %b;
%y = strLen(%a); %z = strLen(%b);

if(%z > %y)
return %a;
else if((%aa=%y-%z) > 0)
%b = Math_Multiply(%b, Math_Pow(2, ~~(3.4 * %aa)));

while(!alessthanb(%a, %b))
%b = Math_Multiply(%b, 2);

while(!alessthanb(%a, %x))
{
if(alessthanb(%a,%b))
{
%aa = strLen(%b) - strLen(%a);
if(%aa > 0)
%b = Math_Multiply(%b, Math_Pow(0.5, ~~(3.4 * %aa)), -1);
else
%b = Math_Multiply(%b, 0.5, -1);

while(alessthanb(%a, %b))
%b = Math_Multiply(%b, 0.5, -1);
}

%a = Math_Subtract(%a, %b);
}
return %a;
}

[Lugnut]

http://www.johannes-bauer.com/compsci/ecc/

course,

FAQ

Cool! Now that I know how to use ECC, should I write my own crypto library?

Please don't. This tutorial is meant to merely help people understand how the underlying crypto works. It is not meant to be used productively at all! Please understand that the people who do write crypto libraries for a living have an incredible amount of knowledge about all kinds of topics that are relevant to ensure security in a real-world scenario. If you don't know your stuff, do not expect to write code that is secure (although it might give the false impression of being secure).

they all say that though. i am curious though, disregarding a faulty RNG, this stuff is just a series of mathematical operations - how bad can you screw that up?

i mean, as long as your one-time-use numbers are used only once, your rng is actually random enough, you didn't forget up the math somehow, and barring an error or omission in the article, i want to know literally what could go wrong?

[Ipquarx]

Honestly even if we do screw up, someone will at least tell us so we can fix it.

[Greek2me]

on that note, modulo works, the fastExpMod thing works, now just make them work on schedule loops, which will slow them down tremendously, but it will still work, ideally without lagging too badly

No, the math functions should not work on schedule loops; they need to return something. The actual encryption function is what will use schedule loops.

Also, what needs doing? We need to post a to-do list somewhere, like on the Github issue tracker.

[Ipquarx]

First thing that needs doing is for someone to figure out the parameters we'll use for our encryption. iirc we already agreed on a 384-bit p, but what about the others?

Second is someone actually needs to translate all the math into actual code. Then we can deal with actually doing something with it.

[Ipquarx]

Oh, and we also need some form of symmetric encryption to actually encrypt the messages, according to that article.

[Lugnut]

greek, we need schedules because.. well, let's just look at RSA key generation http://en.wikipedia.org/wiki/RSA_(cryptosystem)#A_working_example

pick two prime numbers, this can be easily scheduled off
pick a number, run the primality check (which is pretty stuffty as it stands) by scheduling the modulo operations

here's the code

Code: [Select]

function isPrime(%num) // this is the basic function, it needs to be implemented utilizing APA (Abritrary Precision Arithmetic).
{
if(%num % 2 == 0)
return false;

if(num + 1 % 6 == 0 || num - 1 % 6 == 0)
continue;
else
return false; // holy stuff this is so loving inefficient and probably broken. i totally screwed something up here.

%squareRoot = mSqrt(%num);

for(%i = 3; %i < %squareRoot; %i += 2) // this can be sped up if we generate a set of primes using the sieve of eratsones, or just flat out include a list of primes from like, one to a million.
{
if(%num % %i == 0)
{
return false;
}
}

return true;
}note the for loop
that's bad
everything up to the for loop can be completed quickly, and everything inside the for loop can be processed quickly, but having the for loop means a bunch of menial operations back to back, leading to slow slow slow slow slow stuff

now realize that rsa encryption is raising the given message m to a power (the public key) e mod a public number n

so basically, 33^17 mod n
not big, but this is using the example i linked above - as soon as the numbers get big, it won't be quite as fast

on the other hand, i don't think ECC uses exponential operations too often, so maybe i'm wrong

what i know is we can't do this

echo(Math_Mod(Math_Subtract(Math_Pow("2","400"), "1"), Math_Subtract(Math_Pow("2","399"), "1"));

we have to do this on schedules

$a = Math_Subtract(Math_Pow("2", "400"), "1");
$b = Math_Subtract(Math_Pow("2", "399"), "1");
echo(Math_Mod($a, $b));

the client cannot notice the operations happening in the background (given reasonable hardware) or else we've failed
[0]we need (included in the library) a function for getting the square root of an arbitrarily large number (primality check)

• we need symmetric encryption - either OTP using ports RNG (in the repo as of five minutes from now) and ECCDH to get the same seed on both ends, or AES (modified for use with binary strings, not actual binary) using ECCDH.
  
• we need the basics of ECC down. i'll be trying to work on that myself this weekend, but i dunno
[0]we need to implement 192 bit ECC first, then 384 bit, mainly just to get the algorithm working

• what would be cool is if we could make a fully functional add-on that utilized just the diffie-hellman exchange and otp (both extremely simple algorithms that i understand inside and out already) just as a proof of concept

edit: we won't be using ports RNG for number generation, we'll have to get user input like truecrypt does - wiggle mouse, type keys, or just record input data as they play the game... a fps perhaps? that should give a bunch of good clean data.

[Greek2me]

greek, we need schedules because.. well, let's just look at RSA key generation http://en.wikipedia.org/wiki/RSA_(cryptosystem)#A_working_example

pick two prime numbers, this can be easily scheduled off
pick a number, run the primality check (which is pretty stuffty as it stands) by scheduling the modulo operations

Math functions need to return a number. They can't do that if they contain schedules.

[Xalos]

here's the code

Code: [Select]

function isPrime(%num) // this is the basic function, it needs to be implemented utilizing APA (Abritrary Precision Arithmetic).
{
if(%num % 2 == 0)
return false;

if(num + 1 % 6 == 0 || num - 1 % 6 == 0)
continue;
else
return false; // holy stuff this is so loving inefficient and probably broken. i totally screwed something up here.

%squareRoot = mSqrt(%num);

for(%i = 3; %i < %squareRoot; %i += 2) // this can be sped up if we generate a set of primes using the sieve of eratsones, or just flat out include a list of primes from like, one to a million.
{
if(%num % %i == 0)
{
return false;
}
}

return true;
}

==>echo(isPrime(2));
0

[Lugnut]

==>echo(isPrime(2));
0

it's obviously intended for use with really big numbers, not for total primality checking across the board

consider it fixed though

Math functions need to return a number. They can't do that if they contain schedules.

they can call a function like onMathFunctionDone(%output, %phase); then just package that function to do stuff, where %phase is something like "keyGenPrimeCheck"

it's a completely different, almost totally roundabout way of thinking, but it can be done.