22
Nov
09

dectobin

#include <stdio.h>

#define L 32

void dectobin(int);

int main()
{
   dectobin(65535);

   return 0;
}

void dectobin(int d){
   int i;
   int bin[L];

   for (i = 0; i < L; i++)
      bin[i] = 0;

   i = L-1;
   do{
      printf("\nd = %d", d);
      if ((d%2) == 0)
         bin[i] = 0;
      else
         bin[i] = 1;
      d = d/2;
      i--;
   }while (d != 0);

   printf("\n");

   for (i = 0; i < L; i++)
      printf("%d", bin[i]);

   printf("\n");
}

Result:

d = 65535
d = 32767
d = 16383
d = 8191
d = 4095
d = 2047
d = 1023
d = 511
d = 255
d = 127
d = 63
d = 31
d = 15
d = 7
d = 3
d = 1
00000000000000001111111111111111

21
Nov
09

Point multiplication with PARI

Calculating point multiplication with a very big number in PARI

Last login: Thu Nov 19 10:29:35 on ttys002
CGs-MacBook:~ chika$ gp
Reading GPRC: /sw/etc/gprc ...Done.

                  GP/PARI CALCULATOR Version 2.1.7 (released)
                             unknown 32-bit version
                (readline v5.0 enabled, extended help available)

                       Copyright (C) 2002 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and
comes WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.

   realprecision = 28 significant digits
   seriesprecision = 16 significant terms
   format = g0.28

parisize = 4000000, primelimit = 500000
(13:50) gp > ? ellpow
ellpow(e,x,n): n times the point x on elliptic curve e (n in Z).

(14:00) gp > ellpow(E,z,10)
%9 = [Mod(4180294501348368083809563235021370057375591405930992803205, 6277101735386680763835789423207666416083908700390324961279), Mod(1227781623738814009517798297176766391967714436501424281520, 6277101735386680763835789423207666416083908700390324961279)]
(14:00) gp > u=ellpow(E,z,10)
%10 = [Mod(4180294501348368083809563235021370057375591405930992803205, 6277101735386680763835789423207666416083908700390324961279), Mod(1227781623738814009517798297176766391967714436501424281520, 6277101735386680763835789423207666416083908700390324961279)]
(14:00) gp > ellisoncurve(E, u)
%11 = 1
(14:01) gp > ellpow(E,z,x)
  ***   sorry, powell for nonintegral or non CM exponents is not yet implemented.
(14:01) gp > x
%12 = Mod(602046282375688656758213480587526111916698976636884684818, 6277101735386680763835789423207666416083908700390324961279)
(14:02) gp > z
%13 = [Mod(602046282375688656758213480587526111916698976636884684818, 6277101735386680763835789423207666416083908700390324961279), Mod(174050332293622031404857552280219410364023488927386650641, 6277101735386680763835789423207666416083908700390324961279)]
(14:02) gp > n = 602046282375688656758213480587526111916698976636884684818
%14 = 602046282375688656758213480587526111916698976636884684818
(14:02) gp > ellpow(E,z,n)
%15 = [Mod(4013698849075654558075584527424681810007648214270260418090, 6277101735386680763835789423207666416083908700390324961279), Mod(849673542270026574908323327879249398221278430546058704302, 6277101735386680763835789423207666416083908700390324961279)]
(14:02) gp > u=ellpow(E,z,n)
%16 = [Mod(4013698849075654558075584527424681810007648214270260418090, 6277101735386680763835789423207666416083908700390324961279), Mod(849673542270026574908323327879249398221278430546058704302, 6277101735386680763835789423207666416083908700390324961279)]
(14:03) gp > ellisoncurve(E, u)
%17 = 1
(14:03) gp > d = n
%18 = 602046282375688656758213480587526111916698976636884684818
(14:04) gp > Q = ellpow(d,z)
  ***   expected character: ',' instead of: Q=ellpow(d,z)
                                                        ^-

(14:04) gp > Q=ellpow(E,z,d)
%19 = [Mod(4013698849075654558075584527424681810007648214270260418090, 6277101735386680763835789423207666416083908700390324961279), Mod(849673542270026574908323327879249398221278430546058704302, 6277101735386680763835789423207666416083908700390324961279)]
(14:05) gp >
20
Nov
09

Is it on curve? (on prime fields)

Sample parameters (from Guide to Elliptic Curve Cryptography #262)

P-192: p = 2^192 − 2^64 − 1, a = −3, h = 1
S = 0x 3045AE6F C8422F64 ED579528 D38120EA E12196D5
r = 0x 3099D2BB BFCB2538 542DCD5F B078B6EF 5F3D6FE2 C745DE65
b = 0x 64210519 E59C80E7 0FA7E9AB 72243049 FEB8DEEC C146B9B1
n = 0x FFFFFFFF FFFFFFFF FFFFFFFF 99DEF836 146BC9B1 B4D22831
x = 0x 188DA80E B03090F6 7CBF20EB 43A18800 F4FF0AFD 82FF1012
y = 0x 07192B95 FFC8DA78 631011ED 6B24CDD5 73F977A1 1E794811

The variables:
x = 602046282375688656758213480587526111916698976636884684818
y = 174050332293622031404857552280219410364023488927386650641
b = 2455155546008943817740293915197451784769108058161191238065

Calculating in PARI:

Last login: Thu Nov 19 10:29:35 on ttys002
CGs-MacBook:~ chika$ gp
Reading GPRC: /sw/etc/gprc ...Done.

                  GP/PARI CALCULATOR Version 2.1.7 (released)
                             unknown 32-bit version
                (readline v5.0 enabled, extended help available)

                       Copyright (C) 2002 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and
comes WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.

   realprecision = 28 significant digits
   seriesprecision = 16 significant terms
   format = g0.28

parisize = 4000000, primelimit = 500000
(13:41) gp > p = 2^192-2^64-1
%1 = 6277101735386680763835789423207666416083908700390324961279
(13:42) gp > a = Mod(-3,p)
%2 = Mod(6277101735386680763835789423207666416083908700390324961276, 6277101735386680763835789423207666416083908700390324961279)
(13:44) gp > b = Mod(2455155546008943817740293915197451784769108058161191238065,p)
%3 = Mod(2455155546008943817740293915197451784769108058161191238065, 6277101735386680763835789423207666416083908700390324961279)
(13:46) gp > E = ([0,0,0,a,b])
%4 = [0, 0, 0, Mod(6277101735386680763835789423207666416083908700390324961276, 6277101735386680763835789423207666416083908700390324961279), Mod(2455155546008943817740293915197451784769108058161191238065, 6277101735386680763835789423207666416083908700390324961279)]
(13:47) gp > ? isoncuve
  ***   isoncuve: unknown identifier.
(13:47) gp > ?isoncurve
  ***   obsolete function: isoncurve
                           ^---------
For full compatibility with GP 1.39, type "default(compatible,3)" (you can
also set "compatible = 3" in your GPRC file).

New syntax: isoncurve(e,x) ===> ellisoncurve(e,x)

ellisoncurve(e,x): true(1) if x is on elliptic curve e, false(0) if not.

(13:47) gp > ellisoncurve
  ***   expected character: '(' instead of: ellisoncurve
                                                        ^

(13:47) gp > ?isoncurve
  ***   obsolete function: isoncurve
                           ^---------
For full compatibility with GP 1.39, type "default(compatible,3)" (you can
also set "compatible = 3" in your GPRC file).

New syntax: isoncurve(e,x) ===> ellisoncurve(e,x)

ellisoncurve(e,x): true(1) if x is on elliptic curve e, false(0) if not.

(13:47) gp > x = Mod(602046282375688656758213480587526111916698976636884684818,p)
%5 = Mod(602046282375688656758213480587526111916698976636884684818, 6277101735386680763835789423207666416083908700390324961279)
(13:48) gp > ellisoncurve(E, x)
  ***   bad argument for an elliptic curve related function
(13:48) gp > ellisoncurve(E, x)
  ***   bad argument for an elliptic curve related function
(13:48) gp > ellisoncurve(E,x)
  ***   bad argument for an elliptic curve related function
(13:49) gp > y = Mod(174050332293622031404857552280219410364023488927386650641,p)
%6 = Mod(174050332293622031404857552280219410364023488927386650641, 6277101735386680763835789423207666416083908700390324961279)
(13:49) gp > z = (x,y)
  ***   expected character: ')' instead of: z=(x,y)
                                                ^---

(13:49) gp > z=(x,y)
  ***   expected character: ')' instead of: z=(x,y)
                                                ^---

(13:49) gp > z = (x,y)
  ***   expected character: ')' instead of: z=(x,y)
                                                ^---

(13:49) gp > z=[x,y]
%7 = [Mod(602046282375688656758213480587526111916698976636884684818, 6277101735386680763835789423207666416083908700390324961279), Mod(174050332293622031404857552280219410364023488927386650641, 6277101735386680763835789423207666416083908700390324961279)]
(13:49) gp > ellisoncurve(E,z)
%8 = 1
(13:50) gp >

[editing is on progress]

16
Nov
09

Another simple hash function

Another simple example:

/*
   Simple Hash Example
   CG - 15112009
*/      

#include <stdio.h>

#define L 32     //the length of the message is 32 bit
#define N 8      //the length of the message block is 8 bit 

int main(){
   char M[L] = {1,0,1,0,1,0,1,0,1,0,0,1,0,1,1,0,1,1,0,0,1,1,0,0,1,1,1,1,0,0,1,1};
   int x = L/N;
   int i, j, k;

   char m[x][N];
   int c[N];

   j = 0;
   k = 0;
   for (i = 0; i < L; i++){
      m[j][k] = M[i];
//      printf("\nm[%d][%d] = %d", j, k, m[j][k]);
      k++;
      if ((i != 0) && ((i % N) == 0)){
         j++;
         k = 0;
      }
   }   

   printf("\nM = ");
   for (i = 0; i < L; i++)
      printf("%d ", M[i]);

   for (j = 0; j < x; j++)
      for (k = 0; k < N; k++){
         printf("\nm[%d][%d] = %d", j, k, m[j][k]);
      }
   printf("\n");

   for (i = 0; i < N; i++)
      c[i] = 0;

   for (k = 0; k < N; k++)
      for (j = 0; j < x; j++)
         c[k] = c[k] ^ m[j][k];

   printf("\nThe N-bit hash code : \n");
   for (i = 0; i < N; i++)
      printf("%d ", c[i]);

   printf("\n");
}

The result is:


M = 1 0 1 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1 1
m[0][0] = 1
m[0][1] = 0
m[0][2] = 1
m[0][3] = 0
m[0][4] = 1
m[0][5] = 0
m[0][6] = 1
m[0][7] = 0
m[1][0] = 0
m[1][1] = 0
m[1][2] = 1
m[1][3] = 0
m[1][4] = 1
m[1][5] = 1
m[1][6] = 0
m[1][7] = 1
m[2][0] = 1
m[2][1] = 0
m[2][2] = 0
m[2][3] = 1
m[2][4] = 1
m[2][5] = 0
m[2][6] = 0
m[2][7] = 1
m[3][0] = 1
m[3][1] = 1
m[3][2] = 1
m[3][3] = 0
m[3][4] = 0
m[3][5] = 1
m[3][6] = 1
m[3][7] = 0

The N-bit hash code :
1 1 1 1 1 0 0 0

11
Nov
09

List of journals

10
Nov
09

Simple Hash Function

A very simple hash function. Take input from stdin.

The perl version is available here.

#include <stdio.h>
#include <stdlib.h> 

int main() {
    int             count = 0;  /* number of characters seen */
    FILE *in_file;  /* input */
    int modulus = 256;

    int ch;
    int total = 0;

    in_file = fdopen(0, "r"); /* 0 is stdin */
    if (in_file == NULL) {
        printf("Error input%s\n");
        exit(8);
    }

    while (1) {
        ch = fgetc(in_file);
        if ((ch == EOF) || (ch == 10))
            break;
        ++count;
        printf("\n%c %d",ch, ch);
        total += ch;
        total = total % modulus;
    }
    printf("\nNumber of characters of input is %d\n", count);
    printf("\nResult : %d\n", total);
    fclose(in_file);
    return (0);
}

The result of the code


CGs-MacBook:Desktop chika$ ./a.out
elliptic curve cryptography

e 101
l 108
l 108
i 105
p 112
t 116
i 105
c 99
32
c 99
u 117
r 114
v 118
e 101
32
c 99
r 114
y 121
p 112
t 116
o 111
g 103
r 114
a 97
p 112
h 104
y 121
Number of characters of input is 27

Result : 231

For a slight different input:

Elliptic curve cryptography

E 69
l 108
l 108
i 105
p 112
t 116
i 105
c 99
32
c 99
u 117
r 114
v 118
e 101
32
c 99
r 114
y 121
p 112
t 116
o 111
g 103
r 114
a 97
p 112
h 104
y 121
Number of characters of input is 27

Result : 199

02
Nov
09

P1363 A.2.1 Modular exponentiation

Picture 2

Next will be A.2.5 Finding Square Roots Modulo a Prime

29
Oct
09

Generating EC parameters

… is not as easy as generating random numbers.

P1363 Section 1.9.5 mention that

The most difficult part of generating EC parameters is finding a base point of prime order

So the next things to do is finding a random point in an elliptic curve (prime case A.11.1/binary case A.11.2), and use A.2.5 to find a square root modulo p and use A.2.1 to calculate modular exponentiation.

In the text book, algorithm for elliptic curve key pair generation is only 5 lines. But implementing one line requires many hours understanding P1363.

Now let’s start with A.2.1.

21
Oct
09

El-Gamal with Pari

Picture 3Encrypt – decrypt successful.

19
Oct
09

Paper – Bali

Another paper,
more here.




Blog Stats

  • 653 hits

 

November 2009
M T W T F S S
« Oct    
 1
2345678
9101112131415
16171819202122
23242526272829
30  

tweet tweet cg