I am looking at A SAT-based Public Key Cryptography Scheme and got inspired to challenge myself to write an implementation of this Cryptography Scheme on Python.
A part of the cipher encoding would be to generate random Boolean functions in Algebraic Normal Form in a certain set of binary variables. I am new to coding and I can not figure out how to generate the required random functions.
EDIT
I have already written some code in sage (and made several runs in Python as well) for the key generation. Since I can’t put the code in a comment I am putting it here. While I am conscious that the code might be naive I have checked with small examples and it looks okay to me.
#n-number of binary variables
#m-number of clauses
#k-number of literals in each clause
def key_gen(n,m,k):
print("the list of variables")
print([var('x'+str(n)) for n in range(n+1)]) #listing the variables
print("")
priv=[randint(0,1) for x in range(n)] #choose randomly the private key
pub=matrix(m,k,0) #store the variables used as a m*k matrix
signs=matrix(m,k,0) #store the signs as a m*k matrix
i=0
j=0
while j<m:
clause=sorted((sample(xrange(0,n),k))) #choose k variables at random
sgn=[randint(0,1) for x in range(k)] #choose their signs at random
value=0
for i in xrange(0,k):
value += (mod(sgn[i]+priv[clause[i]],2)) #check the truth value of the clause
if value!=0: #the clause is accepted iff there is
pub[j]=clause #at least one literal with truth value one
signs[j]=sgn
j=j+1
i=i+1
print("")
print("private key")
print(priv)
print("")
print("the matrix of variables ")
print(pub)
print("")
print("the matrix of signs")
print(signs)
I have tried to do something regarding encryption.
#encryption
#n-number of variables
#pub is a m*k-matrix, where in its rows are stored the clauses
#signs-a m*k matrix where are stored the signs of literals
#y-bit to be encrypted
#alpha, beta encryption parameters
def encrypt(n,pub,signs,alpha,beta,y):
if ((beta > len(pub.rows())) or (beta >= alpha)):
print("Encryption is not possible")
else:
m=len(pub.rows())
k=len(pub.columns())
g_alpha=0
for i in xrange(0,alpha):
block=matrix(beta,k,0) #store the tuples of clauses as beta*k matrix
nr=sorted((sample(xrange(0,m),beta))) #choose at random beta clauses
g_beta=0
for j in xrange(0,beta):
block[j]=pub[nr[j]] #store clauses according to their position
B=BooleanPolynomialRing(n,'x')
used_var=[B.gens()[pub[nr[j]][i]] for i in xrange(k)] #store the
c_j=0 #used variables
for i in xrange(0,k):
c_j+=(B.gen(pub[nr[j]][i]) + signs[nr[j]][i]+1) #calculate the negation
zero_list=[0 for x in xrange(k)]
dict={key:value for key,value in zip(used_var,zero_list)}
f=B.random_element()
R=f.subs(dict) #generate R
g_beta+= c_j*R
g_alpha+=g_beta
g=y+g_alpha
print("the encrypted bit is",g)
Decryption:
#priv- a list of numbers
#g-a symbolic expression-the cipher
def decrypt(priv,g):
n=len(priv)
B=BooleanPolynomialRing(n,'x')
A=[B.gen(i) for i in xrange(n)]
f=B(g) #get a Boolean Polynomial from symbolic expression
dict={key:value for key,value in zip(A,priv)}
s=f.subs(dict) #evaluate g(priv)
print('decrypted bit is',s)
0
I’m basing this off of the Algorithms section of the paper, which is kind of hard to understand, so I would appreciate someone else checking this. Also, I hope you’re doing this for fun and not planning on using this for real cryptography without thorough analysis by professionals and academics,
The public Boolean function (13) is a series of clauses ANDed together, x -> ^ c_j(x). Each clause is a series of subclauses ORed together, x -> V(...). And each subclause is an element of the input x_[I(i, j)] XORed with some sign s(i, j).
The signs come from a matrix of Booleans and are chosen randomly as 1 or 0, which is pretty straightforward, but picking the elements out of the input is trickier. The input is a vector of Booleans, and we want a random way to choose which one to put in each subclause. So, we make a matrix of integers size m, k and call it I. For each row in this matrix, c_j(x) has to be true for the private key (since they will be ANDed together). So, generate a row of random integers (from 1 to n so we don’t go out of bounds of the input) and a row of random signs. Each of these should be k items, since they will be rows of their matrices.
Once we’ve come up with candidate rows, we need to make sure they satisfy the private key. So, for each index in the row, we derive a subclause for the function c_j and make sure at least one is true (since they will be ORed together). For example, the first elements might be 5 and 1, so we XOR the 5th element of the private key with 1 and see if it is true. Continue down the rows until at least one is true, and if it is, add the rows to your matrices.
Thinking in the other direction, if you have the matrices I and s, you can check a candidate key pretty easily. For each row of the matrices, make sure that with the integer from I indexing the key, you get a value that can be XORed with the Boolean from s.
Let’s take the rows [1, 3, 2] and [1, 0, 0], and a candidate key [1, 1, 0]. First, take the first element from the key (1) and XOR it with 1. This gives you 0, so continue on. Take the third element from the key (0) and XOR it with 0. This gives 0, so keep going. Finally, we XOR the second element (1) and the third sign (0) to get 1. Since we got a 1, these rows work with this key.
4