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


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 >

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]

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


List of journals

1. ITB Journal
2. Jurnal Telekomunikasi ITTelkom
3. Jurnal Ilmiah Teknologi Informasi ITS
4. International Journal of Computer Science and Network Security (IJCSNS)
5. International Journal of Computer Science and Information Technology (IJCSIT)
6. Academy & Industry Research Collaboration Center (AIRCC)
7. IAENG International Journal of Computer Science
8. Inderscience

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


P1363 A.2.1 Modular exponentiation

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

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.

El-Gamal with Pari

Encrypt – decrypt successful.

Paper – Bali

Another paper,
more here.