The text below is selected, press Ctrl+C to copy to your clipboard. (⌘+C on Mac) No line numbers will be copied.
Guest
El
By Guest on 7th February 2019 11:26:07 AM | Syntax: TEXT | Views: 3



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