# Finite Fields- Number Theory

This blog post covers one of the most important Mathematical Structures for Cryptography- Fields. It is used in both Symmetric and Asymmetric key Cryptography. This blog post gives a basic introduction to Finite Fields and arithmetic operations on it, but I hope the purpose of it is served- to make people, who don’t have basic knowledge about this, understand a few upcoming CTF write-ups, that are based on Finite Fields.

## Field

A set F of elements with an operation o that combines two elements of F using the following criteria:

1. Closure: If A and B are two elements belonging to Field F, then the result of the operation A o B must also belong to F.
2. Associative: If A, B and C are elements belong to F, then (A o B) o C = A o (B o C)
1. Identity Element: There exists an element e in F such that for any A belonging to F, A o e = A, where o can be + or *
2. Additive Inverse: For every element A in F, there exists A-1 in F such that                  A + A-1 = 0
3. Multiplicative Inverse: For every element A except 0 in F, there exists A-1 in F such that A * A-1 = 1
4. Distributive

Theorem of Finite Fields: Finite Fields only exist if they have pm elements, where p is a prime number and m is a positive integer → p>=2

1. For example: GF(11**1), GF(81) = GF(3**4), GF(256) = GF(2**8)
2. Note that finite fields with p = 2 are of very importance
3. GF(256 = 2**8) is used in AES

Classification of Finite Fields:

1. m = 1, GF(p) → Prime Fields
2. m > 1, GF(pm) → Extension Fields

Extension Fields are of importance in crypto (For example GF(2**8))

### Prime Field Arithmetic:

1. Elements of a prime field GF(p) are the integers {0,1,…,p-1}, where is a prime number
1. For a,b belonging to GF(p) = {0,1,…,p-1}
2. a o b congruent to c over mod p, where o can be +,-,*
3. Inversion
1. For a belonging to GF(p), then a-1 must satisfy a o a-1 congruent to 1 mod p (Multiplicative Inverse). Multiplicative inverse can be calculated using Euclid’s Extended Algorithm
2. For a belonging to GF(p), then a-1 must satisfy a o a-1 congruent to 0 mod p (Additive Inverse)

### Extension Field Arithmetic GF(2m):

1. Element Representation
1. The elements of GF(2m) are polynomials am-1xm-1 + … + a1x + a0
2. ai belongs to the prime field GF(2) = {0,1}
3. Example: GF(23) = a2x2 + a1x + a0 = (a2, a1, a0) → A vector
1. Since the value of ai can only be 0 or 1, we can enumerate all the possible values to get the Galois Field.
2. GF(23) = {0, 1, x, x+1, x2, x2+1, x2+x, x2+x+1}
2. Computing the polynomials i.e. the elements of Galois Field
1. Addition and Subtraction in GF(2m)
1. Let A(x) and B(x) be elements belonging to GF(2m). Then
1. C(x) = A(x) +/- B(x) = cix, for i = 0,…,m-1,                                                   ci = (ai +/- bi) mod 2 = (ai + bi) mod 2
2. GF(23): A(x) = x2 + x + 1, B(x) = x2 + 1, Compute A(x) + B(x)
1. C(x) = ((1+1)%2)x2 + ((1+0)%2)x + ((1+1)%2)
2. C(x) = x
2. Multiplication in GF(2m)
1. Let A(x) and B(x) be elements belonging to GF(23). Then
1. C’(x) = A(x)*B(x) = (x2+x+1)*(x2+1)
2. C’(x) = x4+x3+x2+x2+x+1 = x4+x3+x+1
3. The present C’(x) we have does not belong to the Galois Field, so we divide it by a polynomial that behaves like a prime (so that it cannot be factored). These polynomials are called irreducible polynomials.
4. P(x) = pixi, pi belongs to GF(2)
1. C(x) = A(x).B(x) mod P(x) where P(x) is an irreducible polynomial.
2. P(x) in this case is x3+x+1
3. Therefore, C(x) = x2+x is congruent to A(x).B(x) mod P(x)
2. For every field, GF(2m) there are several irreducible polynomials. Therefore, the irreducible polynomial has to be given in the first place.
3. Inversion in GF(2m)
1. For A(x) in GF(2m), A-1(x) can be calculated by Extended Euclidean Algorithm

# ASIS Finals CTF 2017- Gracias Writeup

Points: 287    Solves: 9    CategoryCrypto
Description: Some people think that combination of cryptographic systems will definitely improve the security. That’s your turn to prove them wrong.

This challenge is a bit simpler than it looks like. It is a multi-prime RSA challenge where we are given an encryption script, which has two functions, one that generates public and private keys and another that encrypts using the public key generated from the first function.

The function that generates public and private keys:

def make_pubpri(nbit):
p, q, r = [ getPrime(nbit) for _ in xrange(3)]
n = p * q * r
phi = (p-1)*(q-1)*(r-1)
l = min([p, q, r])
d = getPrime(1)
e = inverse(d, phi)
a = gensafeprime.generate(2*nbit)
while True:
g = getRandomRange(2, a)
if pow(g, 2, a) != 1 and pow(g, a/2, a) != 1:
break
return (n, e, a, g), (n, d, a, g)


There are three-512 bit primes- p, q, r being generated in this RSA Encryption instead of two. The decryption exponent d, is generated as a 256-bit prime. The function is returning n, e, a, g as the public key.

The following is the encryption function:

def encrypt(m, pub):
n, e, a, g = pub
k = getRandomRange(2, a)
K = pow(g, k, a)
c1, c2 = pow(k, e, n), (m * K) % a
return c1, c2


Unlike the conventional RSA encryption, here the message is not encrypted using RSA; instead of that, k is encrypted using the public key exponent e, the ciphertext of which is c1. There is another ciphertext variable returned in the function along with c1 that is:

c2 = (m * K) % a

K = pow(g, k, a)

So, the flow of attack on this challenge is as follows:

1. Decrypt the ciphertext c1 to get k.
2. Use this to generate as given in the code and then simply multiply c2 with multiplicative inverse of over modulus a, to get the message m.

Here are the values of public key variables given:

n = 1696852658826990842058316561963467335977986730245296081842693913454799128341723605666024757923000936875008280288574503060506225324560725525210728761064310034604441130912702077320696660565727540525259413564999213382434231194132697630244074950529107794905761549606578049632101483460345878198682237227139704889943489709170676301481918176902970896183163611197618458670928730764124354693594769219086662173889094843054787693685403229558143793832013288487194871165461567L

e = 814161885590044357190593282132583612817366020133424034468187008267919006610450334193936389251944312061685926620628676079561886595567219325737685515818965422518820810326234612624290774570873983198113409686391355443155606621049101005048872030700143084978689888823664771959905075795440800042648923901406744546140059930315752131296763893979780940230041254506456283030727953969468933552050776243515721233426119581636614777596169466339421956338478341355508343072697451L


The first thought that comes to my mind to solve step-1 in the flow of attack is Wiener’s Attack. By just looking at n and e values, we can suspect it to be vulnerable to Wiener’s Attack (Number of digits in each is almost the same, consider it a guess). I verified the criteria for it to be vulnerable to Wiener’s Attack (i.e. d<(1/3)*(N1/4)  or   e>N3/2) and found that e, i.e. the public key exponent, is a few bits smaller than N3/2, which made me conclude that d, i.e. the private key exponent, must be a few bits greater than (1/3)*(N1/4). So, the values fail to fall under the conventional criteria of Wiener’s Attack, by a few bits. But I wrote this script implementing Wiener’s Attack in python-sage to check if it really works.

Note that k is encrypted instead of message m, thus I used a temporary message m=12345, encrypted it using the same public key exponent e and modulus n, and finally tried Wiener’s Attack on this; thus the script:

from sage.all import continued_fraction, Integer
def wiener(e, n):
m = 12345
c = pow(m, e, n)

list1 = continued_fraction(Integer(e)/Integer(n))
conv = list1.convergents()
for i in conv:
d = int(i.denominator())
m1 = pow(c, d, n)
if m1 == m:
return d
pubkey = (1696852658826990842058316561963467335977986730245296081842693913454799128341723605666024757923000936875008280288574503060506225324560725525210728761064310034604441130912702077320696660565727540525259413564999213382434231194132697630244074950529107794905761549606578049632101483460345878198682237227139704889943489709170676301481918176902970896183163611197618458670928730764124354693594769219086662173889094843054787693685403229558143793832013288487194871165461567L, 814161885590044357190593282132583612817366020133424034468187008267919006610450334193936389251944312061685926620628676079561886595567219325737685515818965422518820810326234612624290774570873983198113409686391355443155606621049101005048872030700143084978689888823664771959905075795440800042648923901406744546140059930315752131296763893979780940230041254506456283030727953969468933552050776243515721233426119581636614777596169466339421956338478341355508343072697451L, 171012227587318507773834753911094468358648971527111097308935888531930900156798659257578479378777764146070352809723708236353390208094909385240006920137781562826981091183813955039359863361624869703055918575613667858215532572602435432258750639197322091887713402631456113333645709142822182724397962837201266977523L, 96969753191136466007366303619618019752521508403657426306543836447071659732926802256183021740376016065813234292694535879838415771865207311953800116203362150588941093508091412441933752168889516206420588410478242229762908362637083786338280959547015086176046206126019992386890758970740552952647510652431386064722L)
n, e, a, g = pubkey
print wiener(e, n)


As expected, the function did not return anything. I could not find any other vulnerability in the code except the Wiener’s Attack and the close values of e and n suggested that there must be some kind of a Wiener’s Attack vulnerability, although not the conventional one. I found another variant of Wiener’s Attack upon searching more about it. There is a paper by Andrej Dujella on a variant of Wiener’s Attack and it works well when the size of d is just a few bits greater than N1/4.

You can check the paper here: A Variant of Wiener’s Attack on RSA

Here is a conclusion of the paper which is significant in our attack:

1. Along with d being the denominator of the convergent of the continued fraction of (e/n), the decryption exponent can also be written in the form:
1. a.    d = r*qm+1 + s*qm

Here qm+1 and qm are the (m+1)th and mth denominators of the convergents of the continued fraction of (e/n) respectively.

I assigned q0 = 1 and q1 as the first denominator of the convergent of continued fraction of (e/n). Here is the exploit for Step-1 where I implemented the Wiener’s Attack using the conclusion from the paper I described above:

def wiener(e, n):
m = 12345
c = pow(m, e, n)
q0 = 1

list1 = continued_fraction(Integer(e)/Integer(n))
conv = list1.convergents()
for i in conv:
k = i.numerator()
q1 = i.denominator()

for r in range(20):
for s in range(20):
d = r*q1 + s*q0
m1 = pow(c, d, n)
if m1 == m:
return d
q0 = q1

pubkey = (1696852658826990842058316561963467335977986730245296081842693913454799128341723605666024757923000936875008280288574503060506225324560725525210728761064310034604441130912702077320696660565727540525259413564999213382434231194132697630244074950529107794905761549606578049632101483460345878198682237227139704889943489709170676301481918176902970896183163611197618458670928730764124354693594769219086662173889094843054787693685403229558143793832013288487194871165461567L, 814161885590044357190593282132583612817366020133424034468187008267919006610450334193936389251944312061685926620628676079561886595567219325737685515818965422518820810326234612624290774570873983198113409686391355443155606621049101005048872030700143084978689888823664771959905075795440800042648923901406744546140059930315752131296763893979780940230041254506456283030727953969468933552050776243515721233426119581636614777596169466339421956338478341355508343072697451L, 171012227587318507773834753911094468358648971527111097308935888531930900156798659257578479378777764146070352809723708236353390208094909385240006920137781562826981091183813955039359863361624869703055918575613667858215532572602435432258750639197322091887713402631456113333645709142822182724397962837201266977523L, 96969753191136466007366303619618019752521508403657426306543836447071659732926802256183021740376016065813234292694535879838415771865207311953800116203362150588941093508091412441933752168889516206420588410478242229762908362637083786338280959547015086176046206126019992386890758970740552952647510652431386064722L)
c = (1569733526826523065259704222721381245770313117205865099913421859731162526943498524936251685846967970606251353344665893442015804015671457823645874503670136308040791285744658847419176471348768113798503897694020110157476679833746227801224812046930570487233225157924912272791212802495997329083436189937249314855532400635293522270501567950040825794060896420481676398789310029592608176167251882124182145471818654414925639589921023176070657483148482403065241178276749773L, 139537660044872985880471632333334179976891152860359271230202507995985566816703080930428310461057387079799847266510420206696052591677854190150642820963140050439023069266243433278700748622126726137374130247097863526461696642750021196138340072411724739383716017406022211953417323065831672315854246554523225039827L)

n, e, a, g = pubkey
c1, c2 = c

d = wiener(e, n)
print d


This finally gave me the decryption exponent:

d = 100556095937036905102538523179832446199526507742826168666218687736467897968451


Now that the significant part of the challenge to get the decryption exponent is done, we can get k, then K and then finally the message m. This is Step-2 and the final step in the exploit:

from Crypto.Util.number import *

k = pow(c1, d, n)
K = pow(g, k, a)
print long_to_bytes(c2 * inverse(K, a) % a)


Which gives us the flag:
ASIS{Wiener_at7ack_iN_mUlt1_Prim3_RSA_iZ_f34sible_t0O!}

Here is the final exploit script:

from sage.all import continued_fraction, Integer
from Crypto.Util.number import *

def wiener(e, n):
m = 12345
c = pow(m, e, n)
q0 = 1

list1 = continued_fraction(Integer(e)/Integer(n))
conv = list1.convergents()
for i in conv:
k = i.numerator()
q1 = i.denominator()

for r in range(20):
for s in range(20):
d = r*q1 + s*q0
m1 = pow(c, d, n)
if m1 == m:
return d
q0 = q1

pubkey = (1696852658826990842058316561963467335977986730245296081842693913454799128341723605666024757923000936875008280288574503060506225324560725525210728761064310034604441130912702077320696660565727540525259413564999213382434231194132697630244074950529107794905761549606578049632101483460345878198682237227139704889943489709170676301481918176902970896183163611197618458670928730764124354693594769219086662173889094843054787693685403229558143793832013288487194871165461567L, 814161885590044357190593282132583612817366020133424034468187008267919006610450334193936389251944312061685926620628676079561886595567219325737685515818965422518820810326234612624290774570873983198113409686391355443155606621049101005048872030700143084978689888823664771959905075795440800042648923901406744546140059930315752131296763893979780940230041254506456283030727953969468933552050776243515721233426119581636614777596169466339421956338478341355508343072697451L, 171012227587318507773834753911094468358648971527111097308935888531930900156798659257578479378777764146070352809723708236353390208094909385240006920137781562826981091183813955039359863361624869703055918575613667858215532572602435432258750639197322091887713402631456113333645709142822182724397962837201266977523L, 96969753191136466007366303619618019752521508403657426306543836447071659732926802256183021740376016065813234292694535879838415771865207311953800116203362150588941093508091412441933752168889516206420588410478242229762908362637083786338280959547015086176046206126019992386890758970740552952647510652431386064722L)
c = (1569733526826523065259704222721381245770313117205865099913421859731162526943498524936251685846967970606251353344665893442015804015671457823645874503670136308040791285744658847419176471348768113798503897694020110157476679833746227801224812046930570487233225157924912272791212802495997329083436189937249314855532400635293522270501567950040825794060896420481676398789310029592608176167251882124182145471818654414925639589921023176070657483148482403065241178276749773L, 139537660044872985880471632333334179976891152860359271230202507995985566816703080930428310461057387079799847266510420206696052591677854190150642820963140050439023069266243433278700748622126726137374130247097863526461696642750021196138340072411724739383716017406022211953417323065831672315854246554523225039827L)

n, e, a, g = pubkey
c1, c2 = c

print "e: ", e
print "n: ", n

d = wiener(e, n)

print "d: ", d

k = pow(c1, d, n)
K = pow(g, k, a)
m = long_to_bytes(c2 * inverse(K, a) % a)
print m


# Blinding Attack on RSA Digital Signatures

This blog primarily focuses on Blinding Attack- an elementary vulnerability in RSA cryptosystem used to forge Digital Signatures. The working and properties of Digital Signatures will be described before directly jumping onto the attack. In the end, we discuss ways to prevent this attack.

# Digital Signature using RSA

RSA is a kind of “Trapdoor One-way Function“. Wikipedia describes a one-way function as a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, “easy” and “hard” are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems. A trapdoor one-way function can only be inverted with the help of a “trapdoor” i.e. our ‘d’, the private key in public key encryption. This method has been used in Digital Transactions and authentication of electronic data.

Let ‘N‘ be the modulus, ‘e‘ be the public key and ‘d‘ be the private key.

The relation between the three is as follows:

ed $\equiv$ 1 mod N -> 1

Digital Signature is used for authentication of electronic data. Let Alice and Bob be two generic parties wishing to communicate with each other and Marvin be the eavesdropper, trying to tamper the data transfer between the two parties. The scenario here is as follows: Alice is trying to get signature of Bob over a message ‘M$\in$ Z*N. To get a signature Alice sends the message ‘M‘ where Bob signs the message M as follows:

S = Md mod N -> 2

Here S becomes the signature of the message M. In the above step, Bob applies his private key to the message and obtains a signature S. Bob then sends this S to Alice or any other authentic party which needs the signature of Bob on M. Since public key of Bob, as the name suggests, is known to the parties, the signature can be easily verified if it is generated from Bob or not by simply calculating

Se = M mod N -> 3

We have used two simple properties, 1 and 2 to arrive at 3. Only Bob has his private key and so the parties can conclude that the signature is authenticate and legible. In the next session we discuss some vulnerabilities in the above method.

# Blinding Attack

Consider the same scenario here, except for the fact that this time Marvin wants the signature of Bob over a message M which Bob refuses, being no fool knowing the significance of Digital Signature. So instead of the signature on M, Marvin asks for the signature of “innocent looking”  M’ which is calculated as following:

M’ = reM mod N

Bob agrees to sign this message M’. Let S’ be the signature generated in case of M’. We can write S’ as:

S’ = (M’)d mod N

Upon receiving the signature S’, Marvin can then easily forge the signature to get the signature for message M as follows:

Step 1: Se = (S’)e/re

Step 2: (S’)e/re = (M’)ed/re

Step 3: (M’)ed/re $\equiv$ M’/re = M mod N
(from 1, ed $\equiv$ 1 mod N )

Step 4: Se = M mod N

Here r is any random integer in the same interval as M. The term re mod N is known as blinding factor.

So without actually getting the signature on M, Marvin could successfully manipulate the signature S’ to gain the signature of M i.e. S. This technique allows an attacker to get signature on a message of his choice without the consent of the one who is signing it.

The question which arises now is, what could be the possible measures to prevent such attacks? If you closely look at the way Blinding Attack is implemented, you will get the catch in Step #3. If the signatory signs the Hash of the message M instead of signing the message itself, all the four steps in the attack would make no sense since M’ would then be replaced by H(M’) (The hash function) and hence it cannot be divided by blinding factor to get back M. Another advantage of using hash of the message instead of using the message is that a cryptographic hash can take an arbitrarily long message, and ‘compress’ it into a short string, in such a way that we cannot find two messages that hash to the same value. Hence, signing the hash is just as good as signing the original message, without the length restrictions we would have if we didn’t use a hash. This overcomes the size problem in RSA operation where the key has to be very large in order to sign smaller messages!

# RC3 CTF Writeup – Salad(Crypto 100)

Being a part of bi0s, this was the first time I was able to decode a cipher while the CTF was still going on and the feeling was amazing! I feel extremely lucky to be a part of bi0s with such great seniors who are experienced exploit experts and mentor like Vipin Sir!

Its been more than a month I have joined bi0s, and I am pretty sure that Cryptography will the field I am going to focus upon in Computer Science for the rest of my life, I mean for my Masters and if possible then PhD. My blog from now will primarily focus upon the new ideas that emerge in the field of Cryptography, along with the topics which I learn.

Of Course, I won’t stop writing critical thoughts and ideas of mine!

The question stated:

Category: Cryptography              Points: 100

Description:

“The fault, dear Brutus, is not in our stars, but in ourselves.” (I.ii.141) Julius Caesar in William Shakespeare’s Julius Caesar

Cipher Text: 7sj-ighm-742q3w4t

At the first glance, the question looks like one encoded with Caesar(Shift) cipher but it is kinda not so. It involves applying Substitution cipher along with Caesar to get the flag.

So here we go,

Since each flag in the CTF had to start with RC3-2016, it struck me at a point of time if even the encoded message contains RC3-2016, but in encoded form! This forced me to find a relation between the letters and the digits using the first 7 encoded digits and RC3-2016. The pattern that I could make out was this:

0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ
KLMNOPQRSTUVWXYZ0123456789ABCDEFGHIJ

7sj-ighm-742q3w4t
RC3-2016-ROMANGOD


Here is the flag: RC3-2016-ROMANGOD

Looking forward to exploring and solving more questions in Cryptography!