The text below is selected, press Ctrl+C to copy to your clipboard. (⌘+C on Mac) No line numbers will be copied. El
By Guest on 7th February 2019 11:26:07 AM | Syntax: TEXT | Views: 78 New paste | Download | Show/Hide line no. | Copy text to clipboard
1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <stdbool.h>
4.
5. unsigned long hcf(unsigned long a, unsigned long b) {
6.     if(b==0) {
7.         return a;
8.     } else {
9.         return hcf(b, a%b);
10.     }
11. }
12.
13.
14. /* 'Fast modular exponentiation'. This method runs in linear time (w.r.t size of x) as to number of operations in the loop
15.  * is log x base 2. Therefore complexity is O(2^(logx base 2))=O(x);
16.  */
17. unsigned long fme(unsigned long g, unsigned long x, unsigned long p) {
18.     unsigned long d=g;
19.     unsigned long e=x;
20.     unsigned long s=1;
21.
22.     while(e>0) {
23.         if(e%2==1) {
24.             s=(s*d)%p;
25.         }
26.         d=(d*d)%p;
27.         e=e/2;
28.     }
29.
30.     return s;
31.
32. }
33.
34.
35. /* This method returns the discrete log, i.e. the value of x for which y=g^x mod p. */
36. unsigned long dl(unsigned long y, unsigned long g, unsigned long p) {
37.     unsigned long x=1;
38.     unsigned long modVal=0;
39.     while(x<p) {
40.         modVal=fme(g, x, p);
41.         if(modVal==y) {
42.             return x;
43.         }
44.         x=x+1;
45.     }
46.
47.     return 0;
48.
49. }
50.
51.
52. /* This method returns inverse modulo prime, i.e. the value of x for which
53.  * x.y `= 1 mod p.
54.  */
55. unsigned long imp(unsigned long y, unsigned long p) {
56.     unsigned long x=1;
57.     unsigned long modVal=0;
58.     while(x<p) {
59.         modVal=(x*y)%p;
60.         if(modVal==1) {
61.             return x;
62.         }
63.         x=x+1;
64.     }
65.
66.     return 0;
67. }
68.
69.
70.
71.
72. int main(int argc, char **argv) {
73.
74.
75.     /* a is first value of recieved message.
76.            b is second value of recieved message.
77.            g is primative root.
78.            x is power.
79.            p is prime.
80.            y is return value of methods.
81.            m is message.
82.            k is a random number in rank 1-p
83.          */
84.
85.     unsigned long int a, b, g, x, p, y, m, k, s, sInv;
86.     char choice;
87.     p=65537;
88.     g=3;
89.
90.     printf("Prime modulus is %lu\n", p);
91.     printf("Primitive root wrt %lu is %lu\n", p, g);
92.
93.
94.     while(true) {
95.         printf("\nChoose: e (encrypt) | d (decrypt) |k (get public key) | x (exit)? ");
96.         scanf("%s", &choice);
97.
98.         switch(choice) {
99.             case 'k':
100.                 printf("Type private key: ");
101.                 scanf("%lu", &x);
102.                 printf("Public key is: %lu\n", fme(g, x, p));
103.                 break;
104.             case 'e':
105.                 printf("Type secret number to send: ");
106.                 scanf("%lu", &m);
107.                 printf("Type recipient's public key: ");
108.                 scanf("%lu", &y);
109.                 k=rand()%(p-1)+1;
110.                 a=fme(g, k, p);
111.                 b=(m*fme(y, k, p))%p;
112.                 printf("The encrypted secret is: (%lu, %lu)\n", a, b);
113.                 break;
114.             case 'd':
115.                 printf("Type the recieved message in the form (a,b): ");
116.                 scanf("%lu %lu", &a, &b);
117.                 printf("Type in your private key: ");
118.                 scanf("%lu", &x);
119.                 s=fme(a, x, p);
120.                 sInv=imp(s, p);
121.                 m=(sInv*b)%p;
122.                 printf("The decrypted secret is: %lu\n", m);
123.                 break;
124.             case 'x':
125.                 return 0;
126.         }
127.     }
128.
129.     return 0;
130. }

• Recent Pastes