Lujmina's profile - activity

Hey guys,

I was wondering if there is any padding module/function in Sagemath for OAEP padding.

OAEP is used with RSA, but I am trying to check whether I can use it with a different public key cryptosystem.

Cheers

Hi all,

Is there an implementation in Sagemath for the F4 and F5 algorithms that relates to Grobner bases? I found something about libsingular:slimgb, however I am not 100% sure if it is the right algorithm. Could you please let me know?

Thanks

@rburing any idea on this?

Also, just to make it easier: https://github.com/miguelmarco/DME/tr.... The implementation I am trying it taken from the file find m1 and m2

I am following the author's code so should be simillar from my point of view

Sure, it can be found here: https://www.mat.ucm.es/~iluengo/DME/p.... Also, it has a section Code where you can see the C code.

I have to add that normally, I would want both M1 and M2 to be invertible, which it is the case when e > 9. Although when e < 9 M1 or M2 are sometimes invertible, they are not both invertible at the same time. Best to try with e = 4

Hey guys,

I am working on a project and I am trying to find a matrix that is invertible using the following code:

e = 5;
n = 2;
m = 3;
s = 2;
t = 2;
b = 2;


mon = (b * n^s)^t
mon2 = b * n^s
#F_q is F_2/{irreducible element in F_2}
F.<r> = GF(2)[];

for p in F.polynomials(e):
    if p.is_irreducible():
        break;

K.<q> = GF(2^e, name='q', modulus=p);

Zn = Integers(2^(e*n)-1);
Zm = Integers(2^(e*m)-1);

R = PolynomialRing(K,'X');
R.inject_variables();

M1 = matrix(K,mon,mon);
M2 = matrix(K,mon,mon);
M1inv = matrix(K,mon,mon);
M2inv = matrix(K,mon,mon);
pt_sec2pub = matrix(K,mon,m*n);
#Constructing matrix A using the variables mentioned in the paper
A = matrix(Zn,m,m);

while True:
    for i in range(0,m):
        for j in range(0,m):
            if(s<m):
                if j==s-i:
                    A[i,j] = 0;
                else:
                    A[i,j] = 2^(ZZ.random_element(0,n*e));
            else:
                A[i,j] = 2^(ZZ.random_element(0,n*e));
    det = A.determinant();
    if gcd(det,2^(e*n)-1) == 1:
        break;
Ainv = matrix(Zn,m,m);
Ainv = A.inverse();

print A * Ainv
print Ainv * A
#Constructing matrix B using the variables mentioned in the paper
B = matrix(Zm,n,n);

while True:
    for i in range(0,n):
        for j in range(0,n):
            if(t<n):
                if j==t-i:
                    B[i,j] = 0;
                else:
                    B[i,j] = 2^(ZZ.random_element(0,m*e));
            else:
                B[i,j] = 2^(ZZ.random_element(0,m*e));
    det = B.determinant();
    if gcd(det,2^(e*m)-1) == 1:
        break;
Binv = matrix(Zm,m,m);
Binv = B.inverse();
print Binv * B
print B * Binv

# This computes the monomials generated when you apply G1 and G2 to the input. Instead of raising polynomials, you raise the elements of the polynomials to their respective element in A and B.
def compute_monomials_for_public_key(x):
    row = matrix(K,t,mon2)
    vector_result = matrix(K,mon*2,1)

    # This is the vec1^(A[0][0]).lift() * vec2^(A[0][1]).lift() from G1
    row[0,0] = x[0][0]^A[0][0].lift() * x[2][0] ^ A[0][1].lift()
    row[0,1] = x[1][0]^A[0][0].lift() * x[2][0] ^ A[0][1].lift()
    row[0,2] = x[0][0]^A[0][0].lift() * x[3][0] ^ A[0][1].lift()
    row[0,3] = x[1][0]^A[0][0].lift() * x[3][0] ^ A[0][1].lift()
    # This is the vec1^(A[1][0]).lift() * vec3^(A[1][2]).lift(); from G1
    row[0,4] = x[0][0]^A[1][0].lift() * x[4][0] ^ A[1][2].lift()
    row[0,5] = x[1][0]^A[1][0].lift() * x[4][0] ^ A[1][2].lift()
    row[0,6] = x[0][0]^A[1][0].lift() * x[5][0] ^ A[1][2].lift()
    row[0,7] = x[1][0]^A[1][0].lift() * x[5][0] ^ A[1][2].lift()

    # This is the vec1^(A[1][0]).lift() * vec3^(A[1][2]).lift(); from G1
    row[1,0] = x[0][0]^A[1][0].lift() * x[4][0] ^ A[1][2].lift()
    row[1,1] = x[1][0]^A[1][0].lift() * x[4][0] ^ A[1][2].lift()
    row[1,2] = x[0][0]^A[1][0].lift() * x[5][0] ^ A[1][2].lift()
    row[1,3] = x[1][0]^A[1][0].lift() * x[5][0] ^ A[1][2].lift()
    # This is the vec2^(A[2][1]).lift() * vec3^(A[2][2]).lift(); from G1
    row[1,4] = x[2][0]^A[2][1].lift() * x[4][0] ^ A[2][2].lift()
    row[1,5] = x[3][0]^A[2][1].lift() * x[4][0] ^ A[2][2].lift()
    row[1,6] = x[2][0]^A[2][1].lift() * x[5][0] ^ A[2][2].lift()
    row[1,7] = x[3][0]^A[2][1].lift() * x[5][0] ^ A[2][2].lift()

    #print row
    for i in range(0,mon2):
        for j in range(0,mon2):
            vector_result[mon2*i + j] = row[0][i] ^ B[0][0].lift() * row[1][j] ^ B[0][1].lift()
            vector_result[mon2*i + j + mon] = row[0][i] ^ B[1][0].lift() * row[1][j] ^ B[1][1].lift()

    return vector_result




def generateVectors():
    while True:
        for i in range(0,mon):
            for j in range(0,m*n):
                pt_sec2pub[i,j] = K.random_element();
            transp = matrix(pt_sec2pub[i]).transpose();
            #print "HA"
            vec_transp = compute_monomials_for_public_key(transp);
            for j in range(0,mon):
                M1[j,i] = vec_transp[j][0];
                M2[j,i] = vec_transp[j+mon][0];
            #if i == 0:
                #print vec_transp
        print M1.is_invertible()
        M1inv = M1.inverse()
        print M1inv * M1
        break;

generateVectors()

However, when e < 8, it always gives me that M1 is not invertible and I do not understand whether there is an issue in my logic or not. I am however able to compute the inverse of M1 but when I multiply it with M1, I expect the identity matrix, however this is not the case when e < 8. Please try with different values of e to see this happening. Please let me know if you manage to find anything.

Thanks

The last part was the one I was looking for, thanks man :)

What I am trying to do is to convert the finite field representation into a polynomial ring with boolean coefficients. So let's take a finite field element: x^48 + x^27 +1

What I want to do is to look at this element as a polynomial ring element, so the above element will look like: Polynomial: 1*x^48 + 0*x^47 + ... + 0*x^28 + 1*x^27 + ... + 1.

Is it possible to do it in this way?

Hey guys,

I am trying to compute the groebner basis of a polynomial system that looks like this:

e = 48;
F.<r> = GF(2)[];

for p in F.polynomials(e):
    if p.is_irreducible():
        break;

R.<x> = PolynomialRing(GF(2),name="x").quotient(p)

I = Ideal([R.random_element(),R.random_element(),R.random_element(),R.random_element(),R.random_element(),R.random_element()])
print I.groebner_basis()

However I get an error: 'Ideal_pid' object has no attribute 'groebner_basis'

I am new to Sagemath so sorry if I misunderstand something. Also, how can I possibly make R to become a multivariate system by following the same structure, using an irreducible polynomial from GF(2) as presented in this code.

Thanks guys :)

Hi,

I would like to convert an Integer to a GF, however I do not seem to find anything about this or whether it is possible or not. I am using the following code:

e = 48
n = 2
m = 3

F.<t> = GF(2)[]
K.<q> = GF(2^48, name='q', modulus=t^48 + t^28 + t^27 + t + 1, repr='int')

test = 0x944a58ec1f29
print test
print Integer(test)
print K(test)

Thank you

Thanks for letting me know, solved it :) made my understand that I should look a bit more at my logic. I will mark this as the solution, however, the inverse was not the issue here.

It is not this: (x^n)^k that I am afraid of. I want a and b to be of the following form: a*b = 1 mod 2^96-1 such that when i do (x^a)^b, it will give me x. But if I do the lift on b, then it wont maintain the property that it is the inverse of a in mod 2^96-1

It doesn't help, I want to be able to keep the exponent modulo such that it reduces when I multiply it with its inverse, as in Diffie Helman

K is GF(2^48) and x is a vector of K elements

Edited with the code. Sorry for my code being very messy

I want to raise the polynomial vec1[0] to the power of a number mod x

(vec1[0])^Binv[0][0], however when I do that, I receive the following message:

unsupported operand type(s) for &: 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp' and 'int'

When I change Binv[0][0] to be an integer, everything works fine, however, this is not what I want to achieve. Is there any workaround to this?

Z3 = Integers(2^(e*m)-1);
B = matrix(ZZ,2,2);
F11 = 50;
F12 = 24;
F21 = 7;
F22 = 88;
B[0,0] = 2^F11;
B[0,1] = 2^F12;
B[1,0] = 2^F21;
B[1,1] = 2^F22;

#print B[0][0]
B_mod = B.mod(2^(e*m)-1)
#print B_mod

Binv = matrix(Z3,2,2);
Binv = B_mod.inverse();

R = PolynomialRing(K,'X');
R.inject_variables();
#Find irreducible polynomial of degree 3
while True:
    c = K.random_element();
    d = K.random_element();
    f = K.random_element();

    IP3 = X^3 + c*X^2 + d*X + f;
    if IP3.is_irreducible():
        break;
RRR = R.quotient(IP3,'Y')
RRR.inject_variables()  
vec1 = X^2 * x[0] + X * x[1] + x[2]

result1 = RRR(vec1[0])^Binv[0][0]

I am currently doing some implementation but I have something that I do not seem to find online and bugged me for a few hours:

e = 48;
K = GF(2^e);
KE = GF(2^(e*2));

A = matrix(KE,3,3);
E11 = 24;
E12 = 59;
E21 = 21;
E23 = 28;
E32 = 29;
E33 = 65;
A[0,0] = 2^E11;
A[0,1] = 2^E12;
A[0,2] = 0;
A[1,0] = 2^E21;
A[1,1] = 0;
A[1,2] = 2^E23;
A[2,0] = 0;
A[2,1] = 2^E32;
A[2,2] = 2^E33;

print A[2][1]

When I do this, it print 0, but given that I created it in GF(2^(e*2)), I believe it shouldn't. Because of this, when I try to get the inverse of this matrix, which is invertible, I do not get anything. Please let me know if you have any thoughts.