Αποφασίσαμε να δημοσιεύσουμε στη μορφή ενός άρθρου μια απο τις ασχολίες μας κατά την οποία και υλοποιήσαμε το κρυπτοσύστημα Paillier.  Το κρυπτοσύστημα αυτό δημιουργήθηκε απο τον Pascal Paillier το 1999 και ειναι ένας ασύμμετρος αλγόριθμος για κρυπτογράφηση δημοσίου κλειδιού. Η βάση του είναι μια μαθηματική υπόθεση που ονομάζεται decisional composite residuosity assumption (DCRA) και θεωρείται ότι ειναι πολύ δύσκολο να λυθεί.

Η σημαντικότερη ιδιότητα που παρουσιάζει αυτό το κρυπτοσύστημα ονομάζεται ομομορφική πρόσθεση (homomorphic additive cryptosystem) και αυτό στην πράξη σημαίνει ότι ένα έχουμε δυο κρυπτογραφημένα μηνύματα c1 και c2 που προκύπτουν απο την κρυπτογράφηση του m1 και m2, τότε μπορούμε πολλαπλασιάζοντας το c1 με το c2 να πάρουμε το m1+m2.

Για την υλοποίηση του κώδικα χρησιμοποιήσαμε τη βιβλιοθήκη Crypto.Util.number για τον καθορισμό των πρώτων αριθμών που παίρνουμε για κλειδιά και την βιβλιοθήκη gmpy2 για τις πράξεις με τα εκθετικά που χρειάζονται επειδή δουλεύουμε σε <mod n> και επειδή θέλουμε να καλύψουμε και τις περιπτώσεις με αρνητικούς εκθέτες. Ο κώδικας δουλεύει με αρνητικούς και θετικούς αριθμούς.

import math
import random
from random import shuffle
import sys
import gmpy2
from time import time
from Crypto.Util.number import getPrime

# In[2]:

def gcd(a,b):
while b > 0:
a, b = b, a % b
return a

def lcm(a, b):
return a * b / gcd(a, b)

def int_time():
return int(round(time() * 1000))

class PrivateKey(object):
def __init__(self, p, q, n):
#self.l = lcm(p-1,q-1)—-This is added as requested by the setup BUT not used, shortcut is used!
self.l = (p-1) * (q-1)
#self.m = gmpy2.invert(gmpy2.f_div(gmpy2.sub(gmpy2.powmod(n+1,self.l,n*n),gmpy2.mpz(1)),pub.n),n) — Shortcut used instead of it
self.m = gmpy2.invert(self.l, n) #1/fi(n)
def __repr__(self):
return ” % (self.l, self.m)

class PublicKey(object):

@classmethod
def from_n(cls, n):
return cls(n)
def __init__(self, n):
self.n = n
self.n_sq = n * n
self.g = n + 1
def __repr__(self):
return ” % self.n

def generate_keypair(bits):
p_equal_q = True
while p_equal_q:
p = getPrime(bits / 2)
q = getPrime(bits / 2)
if (p!=q):
p_equal_q = False
n = p * q
return PrivateKey(p, q, n), PublicKey(n)

def encrypt(pub, plain):
one = gmpy2.mpz(1)
state = gmpy2.random_state(int_time())
r = gmpy2.mpz_random(state,pub.n)
while gmpy2.gcd(r,pub.n) != one:
state = gmpy2.random_state(int_time())
r = gmpy2.mpz_random(state,pub.n)
x = gmpy2.powmod(r,pub.n,pub.n_sq)
cipher = gmpy2.f_mod(gmpy2.mul(gmpy2.powmod(pub.g,plain,pub.n_sq),x),pub.n_sq)
return cipher

def decrypt(priv, pub, cipher):
one = gmpy2.mpz(1)
x = gmpy2.sub(gmpy2.powmod(cipher,priv.l,pub.n_sq),one)
plain = gmpy2.f_mod(gmpy2.mul(gmpy2.f_div(x,pub.n),priv.m),pub.n)
if plain >= gmpy2.f_div(pub.n,2):
plain = plain – pub.n
return plain

def addemup(pub, a, b):
return gmpy2.mul(a,b)

def multime(pub, a, n):
return gmpy2.powmod(a, n, pub.n_sq)

Τέλος να αναφέρουμε οτι το κρυπτοσύστημα αυτό χρησιμοποιείται στην ηλεκτρονική ψηφοφορίας δεδομένης της ιδιότητάς του που κάθε ψήφος μπορεί να αθροιστεί με το ήδη κρυπτογραφημένο άθροισμα των προηγούμενων ψήφων.

Ελπίζουμε το άρθρο αυτό να βοήθησε έστω και λίγο σε όσους μπορεί να ασχολούνται με το αντικείμενο, δεδομένου οτι χρειάζεται και μια υπάρχουσα γνώση για την κατανόηση του εφόσον δεν ειναι και ιδιαιτέρως αναλυτικό.

Stay Tuned ...

Join our mailing list to receive the latest news and updates from our team.

You have Successfully Subscribed!