Courses for this semester

1. II5164
2. EL2010

Math and cryptography: uneasy

Neal Koblitz wrote it’s uneasy because:

1. Bandwagon effect
2. Clash of research cultures between math and cryptography
3. Different assumptions and understanding

VERY interesting.

Complexity Theory

How strong, how complex, how efficient, how effective is an algorithm?

1. http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
2. http://pages.cs.wisc.edu/~hasti/cs367-1/notes/complexity.html
3. http://leepoint.net/notes-java/algorithms/big-oh/bigoh.html
4. http://en.wikipedia.org/wiki/Big_O_notation

Group-based cryptography

How difficult it is to construct a group-based cryptography?

1. http://www.springer.com/birkhauser/mathematics/book/978-3-7643-8826-3
2. http://www.sci.ccny.cuny.edu/~shpil/book_cryp_50.pdf
3. http://homepages.cwi.nl/~hofheinz/pdf/metabelian.pdf

Digital Circuit Decomposition

Gathering ideas about decomposition. The philosophy, the theory, the math, the examples.
Stuff to read:

1. General Decomposition and Its Use in Circuit Synthesis Digital - LECH JOZWIAK, VLSI DESIGN 1995, Vol. 3, Nos. 3-4, pp. 225-248(C) 1995 OPA (Overseas Publishers Association)
2. FUNCTIONAL DECOMPOSITION – THE VALUE AND IMPLICATION FOR MODERN DIGITAL DESIGNING – Mariusz RAWSKI†, Tadeusz ŁUBA†, Zbigniew JACHNA‡, Rafał RZECHOWSKI†,The International Workshopon Discrete-Event System Design, DESDes’01, June 27÷29, 2001; Przytok near Zielona Gora, Poland
3. And a good and simple example can be found here.

Thanks to the author of this article in his blog for directing me to the links.

Non-adjacent form (NAF)

NAF is a signed-digit representation. It’s a unique integer representation. In NAF representation, two non-zero values cannot be adjacent. In cryptography using, NAF representation reduces number of multiplications needed for performing exponentiation.

Example:
7 can have several binary representations:

(0 1 1 1) = 4 + 2 + 1 = 7

(1 0 −1 1) = 8 − 2 + 1 = 7

(1 −1 1 1) = 8 − 4 + 2 + 1 = 7

(1 0 0 −1) = 8 − 1 = 7

But only the last representation is NAF.

The algorithm is:

Input: E = (em − 1 em − 2 ··· e1 e0)10
Output: E = (zm zm − 1 ··· z1 z0)NAF

i ← 0
while E > 0 do
if E is odd then
zi ← 2 − (E mod 4)
else
zi ← 0
E ← (E − zi)/2
i ← i + 1
return z


The coding implementation will be done as soon as the phd student finish writing progress report, presentation slides and simulating small curves for progress seminar.

Big numbers in crypto

One big problem I always have is I have no sense of how big are numbers used in cryptography. Yes I always now that it can reach . But HOW BIG IS IT??? And I also get lost on comparing that 2 power of something is equal to 10 power of something.

Last night I had a very unexpected intellectually challenging conversation with a professor of chemistry. Surprisingly he’s very good at general cryptography and math. And probably everything He also play chess

As Rosing wrote in his book that elliptic curve crypto systems are in the range of astronomical, it means that numbers used in crypto is large enough compared to the large numbers in the universe.

Here’s is the example given by the prof. He get a piece of paper and rip it into two pieces, piled it and rip it into two pieces and again for about 4 times. After doing that he said that how thick would you think the paper would be if I rip the paper for 50 times with the assumption that the paper is 1mm thick?

First I thought that it’s maybe just as thick as The Codebreakers book but later I think that it’s . But how big it is? Let’s grab a calculator.

= 1125899906842624. So the pile of papers is 1.1 x mm.

Still have no idea how big it is.

Now let’s compare it to some astronomical numbers. From here I get the info that the distance from earth to sun is 92,935,700 miles or 149565139.43800 km or 149565139438000 mm or 1.5 x mm.

So then the pile of paper wouldn’t fit the space between earth and the sun! WOW!!!

Now let’s pick another example. For a bit length key, = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096, which is equal to 1.3 x . Which is MUCH bigger than the number of atoms in all the earth, which is 8.87 x .

Well, now I have a better sense of how big those numbers are. Hoping you will too

List of torsion subgroups

A list of elliptic curves with each possible torsion subgroup can be found here:

And PARI code that lists infinitely many elliptic curve with each torsion subgroup is here.

Torsion points of elliptic curves

From Torsion Points of Elliptic Curves Over Number Fields by Christine Croll :

so ours is finite order. Then

hah!

And this is an example:

More about torsion points:

1. ON THE TORSION POINTS OF ELLIPTIC CURVES  & MODULAR ABELIAN VARIETIES by SETH KLEINERMAN
2. ELLIPTIC CURVES WITH A TORSION POINT by TOSHIHIRO HADANO

[head ready to explode]

Comparing elltors

for :

(00:37) gp > a = 1
%1 = 1
(00:37) gp > b = 1
%2 = 1
(00:37) gp > E = ellinit([0,0,0,a,b])
%3 = [0, 0, 0, 1, 1, 0, 2, 4, -1, -48, -864, -496, 6912/31, [-0.6823278038280193273694837397, 0.3411639019140096636847418698 - 1.161541399997251936087917687*I, 0.3411639019140096636847418698 + 1.161541399997251936087917687*I]~, 3.749942978094342855851406868, -1.874971489047171427925703434 + 1.321720533565204538833995727*I, -1.256789871861911570289134735 + 0.E-29*I, 0.6283949359309557851445673678 - 1.280744177088026904445230577*I, 4.956376633845946955308257251]
(00:38) gp > elltors(E)
%4 = [1, [], []]


for

(00:38) gp > a = 8
%5 = 8
(00:39) gp > b = 9
%6 = 9
(00:39) gp > E=ellinit([0,0,0,a,b])
%7 = [0, 0, 0, 8, 9, 0, 16, 36, -64, -384, -7776, -67760, 3538944/4235, [-1.000000000000000000000000000, 0.5000000000000000000000000000 - 2.958039891549808021283664145*I, 0.5000000000000000000000000000 + 2.958039891549808021283664145*I]~, 2.323573124298217095517745754, -1.161786562149108547758872877 + 0.9328742056162391756323628615*I, -1.773647591593647783280373514 + 0.E-28*I, 0.8868237957968238916401867572 - 2.064141081460241175088749935*I, 2.167601432520942242537573241]
(00:39) gp > elltors(E)
%8 = [2, [2], [[-1, 0]]]