The Rabin cryptosystem is an asymmetric cryptographic technique, whose security, like that of RSA, is related to the difficulty of factorization. However the Rabin cryptosystem has the advantage that the problem on which it relies has been proved to be as hard as integer factorization, which is not currently known to be true of the RSA problem.
Rabin cryptosystem has the disadvantage that each output of the Rabin function can be generated by any of four possible inputs; if each output is a ciphertext, extra complexity is required on decryption to identify which of the four possible inputs was the true plaintext.
This article do not cover algorithm behind the Rabin cryptosystem. We suggest to go through very simple explanation given on Wikipedia for detailed explanation on Key generation, Encryption and Decryption.
Following is the implementation of the Rabin cryptosystem in C.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 |
#include <stdio.h> #include <stdlib.h> #include <ctype.h> #include <math.h> #include <limits.h> int e = 2, n; int p, q; int gcd(int a, int b) { int q, r1, r2, r; if (a > b) { r1 = a; r2 = b; } else { r1 = b; r2 = a; } while (r2 > 0) { q = r1 / r2; r = r1 - q * r2; r1 = r2; r2 = r; } return r1; } int PrimarityTest(int a, int i) { int n = i - 1; int k = 0; int j, m, T; while (n % 2 == 0) { k++; n = n / 2; } m = n; T = FindT(a, m, i); if (T == 1 || T == i - 1) return 1; for (j = 0; j < k; j++) { T = FindT(T, 2, i); if (T == 1) return 0; if (T == i - 1) return 1; } return 0; } int FindT(int a, int m, int n) { int r; int y = 1; while (m > 0) { r = m % 2; FastExponention(r, n, &y, &a); m = m / 2; } return y; } int FastExponention(int bit, int n, int* y, int* a) { if (bit == 1) *y = (*y * (*a)) % n; *a = (*a) * (*a) % n; } int KeyGeneration() { do { do { p = rand() % 500; } while (!((p % 2 == 1) && (p % 4 == 3))); } while (!PrimarityTest(2, p)); do { do { q = rand() % 500; } while (!((q % 2 == 1) && (q % 4 == 3))); } while (!PrimarityTest(2, q)); n = p * q; printf("p = %d, q = %d, n = %d\n\n", p, q, n); } int Encryption(int PlainText) { printf("PlainText is %d\n", PlainText); int cipher = FindT(PlainText, e, n); fprintf(stdout, "Cipher Text is %d\n", cipher); return cipher; } int inverse(int a, int b) { int inv; int q, r, r1 = a, r2 = b, t, t1 = 0, t2 = 1; while (r2 > 0) { q = r1 / r2; r = r1 - q * r2; r1 = r2; r2 = r; t = t1 - q * t2; t1 = t2; t2 = t; } if (r1 == 1) inv = t1; if (inv < 0) inv = inv + a; return inv; } int Decryption(int Cipher) { int P1, P2, P3, P4; int a1, a2, b1, b2; a1 = FindT(Cipher, (p + 1) / 4, p); a2 = p - a1; b1 = FindT(Cipher, (q + 1) / 4, q); b2 = q - b1; P1 = ChineseRemainderTheorem(a1, b1, p, q); P2 = ChineseRemainderTheorem(a1, b2, p, q); P3 = ChineseRemainderTheorem(a2, b1, p, q); P4 = ChineseRemainderTheorem(a2, b2, p, q); printf("\nP1 = %d\nP2 = %d\nP3 = %d\nP4 = %d\n", P1, P2, P3, P4); } int ChineseRemainderTheorem(int a, int b, int m1, int m2) { int M, M1, M2, M1_inv, M2_inv; int result; M = m1 * m2; M1 = M / m1; M2 = M / m2; M1_inv = inverse(m1, M1); M2_inv = inverse(m2, M2); result = (a * M1 * M1_inv + b * M2 * M2_inv) % M; return result; } int main(void) { int PlainText; KeyGeneration(); do { PlainText = rand() % (n - 1) + 1; // PlainText belongs to the group Zn } while (gcd(PlainText, n) != 1); // PlainText belongs to the group Z*n int Cipher = Encryption(PlainText); Decryption(Cipher); return 0; } |
Output:
p = 383, q = 59, n = 22597
PlainText is 12419
Cipher Text is 7036
P1 = 10944
P2 = 10178
P3 = 12419
P4 = 11653
Thanks for reading.
Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply