Is RSA-OAEP secure against Shor's factoring algorithm I've seen in this answer Can Shor's algorithm compromise RSA when both the public and private key are secret? that if textbook RSA is used (deterministic) the Shor's algorithm can reak it. However, if RSA is used with OAEP then Shor's algorithm cannot break it. The reason is that the known-plaintext pair doesn't include the randomness in the OAEP;
rfc8017 section-9.2

d.  Generate a random octet string seed of length hLen.

rfc8017 B.2.1.  MGF1

maskLen intended length in octets of the mask, at most 2^32 hLen

Then one needs $2^{31}$ try to break the RSA on average if they are able to produce enough Q-bits.

Is my understanding correct?

If so, then make the seed >128-bit and be safe from Shor. Then, why there are so much fear of Shor's algorithm for RSA?

If so, then make the seed >128-bit and be safe from Shor. Then, why there are so much fear of Shor's algorithm for RSA?

Well, remember that the assumption in the original question was that we kept the RSA public key secret.  That is a nonstandard assumption; we generally assume that the attacker knows the RSA public key (and in practice with most uses of RSA, he can easily learn it).
And, with knowledge of the RSA public key, Shor's algorithm can efficiently break it (assuming a reasonable sized Quantum Computer, of course); that is, he can learn the private key (and then do anything that the legitimate owner of the RSA private key can do) - the RSA padding mechanism does not offer any additional protection.


Is this discrete log generalization a well known cryptographic assumption? Assume you have a finite group $\mathbb{G}$ and an integer $n$. Given $g_1,\dots,g_n,t$ chosen uniformly from $\mathbb{G}$, consider the problem of finding a vector $(a_1,\dots,a_n)\in \mathbb{Z}^n$ such that
$$g_1^{a_1}\cdot \ldots \cdot g_n^{a_n} = t $$

Is there any class of groups where the problem is known to be computationally hard? Does the computational assumption have a well established name?

For $n=1$, the problem is equivalent to discrete log, and in general it is easier than discrete log (meaning that solving DL immediately gives a solver for this problem).

Actually, that problem is exactly equivalent to the standard DLOG problem (assuming that you know the group order, and that it is prime).

Here's the reduction: suppose that we have an Oracle that can solve your problem with nontrivial probability.  Then, given a value $g$ and $h$, we can find $x$ with $g^x = h$ with nontrivial probability by:

Create random values $r_1, r_2, ..., r_n$ and $s$ between 0 and the group order (except that $s$ cannot be 0).
Compute $g_i = g^{r_i}$ and $t = h^s$.  Note that the values $g_i$ and $t$ are uniformly distributed (except that $t$ is not the identity).
Give the values $g_i$ and $t$ to your Oracle, which computes the values $a_i$ with nontrivial probability.
$x = s^{-1}\ \sum\  a_i r_i$

The only reason we needed to assume that the group order was prime was to be precise in the assumption that the elements be chosen randomly; if we relax that restriction on $t$, we can handle composite group orders as well.


Using Shor's algorithm to solve the discrete logarithm problem I have read about Shor's algorithm and my understanding is that it can be used to factor large numbers efficiently. Can Shor's algorithm, though, be used to solve this problem:

Find the number $e$ given the following information (Assume that $P$, $C$, $N$ and $e$ are all large, say 2048-bit integers):

the integers $P$ and $N$
the integer $C$ where  $C = P^e \bmod N$

If so, how does this algorithm work? Please explain it simply as I am not familiar with quantum mechanics.

Shor's method relies on a period finding routine on a quantum computer.

A function $f: (x_1, \dots, x_n) \mapsto f(x_1, \dots, x_n)$ is periodic, of period $(\omega_1, \dots, \omega_n)$, if $f(x_1 + \omega_1, \dots, x_n + \omega_n) = f(x_1, \dots, x_n)$ for all tuples $(x_1, \dots, x_n)$ in the domain of $f$.

Factorization problem  Given an RSA modulus $N = pq$, find primes $p$ and $q$.

Choose a random integer $a \in \mathbb{Z}_N$ (without loss of generality, we assume $\gcd(a,N) = 1$ —otherwise, this yields the factorization of $N$ and the factorization problem is solved).
Consider the univariate function $f: x \mapsto f(x) = a^x \bmod N$.
The period finding routine finds an $\omega$ such that $f(x + \omega) = f(x)$.  As a consequence, $\omega$ is a multiple of the order of $a$ modulo $N$.  Indeed, one has $f(x+\omega) = f(x) \iff a^\omega \equiv 1 \pmod N$.

If $\omega$ is a multiple of $\lambda(N)$ —where $\lambda(N)$ denotes Carmichael's function, then Miller's algorithm yields the factorization of $N$.  Otherwise, repeat the process with another $a$, get the period $\omega_a$, and update $\omega$ as $\omega \gets \operatorname{lcm}(\omega, \omega_a)$, until $\omega$ is a multiple of $\lambda(N)$.

[ A description of Miller's algorithm can be found in Cryptography: Theory and Practice by Douglas Stinson, http://cacr.uwaterloo.ca/~dstinson/CTAP.html ]

Discrete log problem Let $g$ be a generator of a group $\mathbb{G}$ of prime order $q$.  Given $y = g^k \in \mathbb{G}$, find the value of $k$.

Consider the bivariate function $f : (x_1, x_2) \mapsto g^{x_1} y^{x_2}$.
The period finding routine finds a pair $(\omega_1, \omega_2)$ such that $f(x_1 + \omega_1, x_2 + \omega_2) = f(x_1,x_2)$.
The solution to the discrete logarithm problem is then given by $k = -\omega_1/\omega_2 \bmod q$.  Indeed, one has $f(x_1 + \omega_1, x_2 + \omega_2) = f(x_1,x_2) \iff g^{\omega_1} y^{\omega_2} = 1_{\mathbb{G}} \iff g^{\omega_1  + k\omega_2} = 1_{\mathbb{G}}$ and thus $\omega_1  + k\omega_2 \equiv 0 \pmod q$.


Does there exist a two-pass AKE protocol that is secure in eCK model and also has PFS? As we can know that the best two-pass AKE protocols with DH message can achieve is the weak form of perfect forward security (wPFS) which guarantees security against the passive adversary. But "Strongly Secure One Round Authenticated Key Exchange Protocol with Perfect Forward Security" (Hai Huang) claims that the AKE it proposed can achieve perfect
forward security against active adversary in one round.

Is that correct?  Why?

It is possible to achieve PFS against active adversaries in two messages.
The "as we know" that you mention is incorrect; this misconception seems to stem from over-interpreting Krawczyk's result in his HMQV paper from 2005. At best, the argument seems to hold from protocols that exchange messages of the form g^x, g^y, where x and y are random values: for those protocols it seems you cannot achieve PFS against active adversaries by Krawczyk's example attack. However, his argument does not work against two-message protocols in general (e.g., that exchange messages of a different form).

This misconception is explained in detail in, e.g., the introduction of this paper by Cremers and Feltz, which also includes a full security model and detailed proof of a (construction of a) two-message protocol that achieves a form of security that implies eCK-security and PFS against active adversaries.

There is an earlier protocol (by Gennaro, Krawczyk and Rabin) that achieves PFS against active adversaries in two messages and is also implicitly authenticated, but that does not achieve e-CK security: it is the PKI-based variant described at the end of this paper.

The first description of an eCK-secure variant is found here.

So yes, it is possible to achieve this.


Why is a MAC needed with CBC? I agree that for certain encryption systems or modes of operation, a MAC is indispensible.

The best example are probably stream ciphers (and therefore also block ciphers in OFB or CTR mode) that allow an attacker to arbitrarily flip bits in the ciphertext, resulting in flipped bits at the same position in the plaintext after decryption.

However, I somehow always thought that that wouldn't apply to "modern" block ciphers in some reasonable mode of operation, e.g. AES-CBC. Since there is no clear relation between a bit in the ciphertext and a bit in the plaintext, I thought that any small modification would cause a totally different plaintext.

That in mind, I thought it would be enough to simply concatenate the plaintext with some simple checksum to check for that kind of tampering; a cryptographic hash didn't even seem necessary to me.

But in reality, pretty much every reasonable application of AES-CBC also seems to be using MACs, so I'm almost certain that there is an error somewhere in my reasoning.

To see why CBC mode still needs a MAC to guarantee message integrity, first recall how CBC mode decryption works:

$$P_i = D_K(C_i) \oplus C_{i-1}$$

Here, $D_K$ denotes block cipher decryption using the key $K$, and $C_i$ and $P_i$ denote the $i$-th ciphertext and plaintext blocks respectively.

Now, consider what happens if you modify the encrypted message to replace $C_i$ with $C_i' = C_i \oplus X$ for some $i$.  Now, the corresponding plaintext block $P_i'$ will be garbled, since $D_K(C_i')$ will in general bear no predictable resemblance to $D_K(C_i)$.  However, the next plaintext block $P_{i+1}'$ will now become

$$P_{i+1}' = D_K(C_{i+1}) \oplus C_i' = D_K(C_{i+1}) \oplus C_i \oplus X = P_{i+1} \oplus X.$$

Thus, even with CBC mode, you can still flip arbitrary bits in any given plaintext block, provided that you don't mind the previous plaintext block being garbled.  Whether this is actually practical depends on the what the plaintext is supposed to be, but it's generally not safe to assume that it isn't.

Of course, since the garbled block will, in general, be essentially random and unpredictable by the attacker, it might seem plausible that a simple non-cryptographic checksum could detect such modification.  However, it's not entirely implausible for the attacker to be able to predict $D_K(C_i')$, and thus $P_i'$: for example, if the attacker has access to some known ciphertext/plaintext message pairs, this provides them with a bunch of blocks whose image under $D_K$ is known.  If they choose $C_i'$ to be one of such blocks, they'll be able to predict $P_i'$, and if they can also guess the original plaintext block $P_i$, they may be able to spoof many non-cryptographic checksums.

(In particular, if the IV is sent alongside the message — as is usually done — flipping bits in the first plaintext block is particularly easily done just by flipping the corresponding bits in the IV.  Thus, for the first block, CBC mode is just as malleable as CTR or OFB.)

The bottom line of all this is that, if you want to protect the integrity of your messages, you need to use an encryption mode that is actually designed to be provably non-malleable.  In addition to the generic combination of a classical block cipher mode and a MAC, there also exist several authenticated encryption modes specifically designed for this purpose.


What is the meaning of the overlapping region on OTP-perfect secrecy diagram? I'm new to cryptography. I want to ask about OTP-perfect secrecy diagram like figure below:

On the overlapping region (middle), notated by R(X;Y;Z). R can be calculated by I(X;Y) - I(X;Y|Z). That region is symmetric in X, Y, Z and can be negative. For example when X and Y are independent bits, and Z = X xor Y, then I(X;Y) = I(X;Z) = I(Y;Z) = 0, but I(X;Y|Z) > 0.

What is the "meaning/philosophy" of that region? I mean when the region is negative, when the region is positive, and how to describe that?

I have been trying to find the answer but no result.

Your diagram is a Venn diagram that illustrates the information measures between the correlated random variables $X,Y$ and $Z$.

$H(X)$ refers to a complete circle and is the entropy of $X$,
$H(X|YZ)$ is the entropy of $X$ under the observation of $Y$ and $Z$,
$I(X;Y|Z)$ is the mutual information between $X$ and $Y$ under the observation Z,
$R(X;Y;Z)$ seems to represent $I(X;Y;Z)$, the mutual information between X,Y and Z.

The region $R(X;Y;Z)$ is thus the amount of information that is shared by the random variables $X,Y$ and $Z$. If the random variables are completely independent, then this region is empty.

I don't know exactly how this is related to OTP. I guess that you typically want maximal entropy for OTP, and you don't want to have any mutual information between the variables.

PS: After writing most of this answer I found a wikipedia page about multivariate mutual information, which seems to correspond exactly to this question.


number of active s-boxes in a block cipher? How can we find the minimum number of differentially  active s-boxes in a block cipher (actually a Feistel network with several input cells) in a truncated characteristic form? In a recursive algorithm when we get to the situation that there are binary cases, I don't know what to do? For example when I get a xor of two nonzero characteristics, there are two cases nonzero and zero, How can recursive algorithm be applied in this state?

There many methods to find the number of active sboxes such as:

search algorithm , you input different scenarios , it is time-expensive process.

Matsui algorithm. code

Mixed integer linear programming.
I recommend you to try MIxed integer linear programming

References:
Differential and Linear Cryptanalysis using Mixed-Integer Linear Programming
Automatic Security Evaluation of Block Ciphers with S-bP Structures against Related-key Differential Attacks
New Impossible Differential Search Tool from Design and Cryptanalysis Aspects


Is there a situation where RSA cannot be replaced with ECC + symmetric algorithms? If no, why do we still use it? RSA is both an asymmetric encryption algorithm and a digital signature algorithm.  However, in recent years, many cryptographic protocols (TLS, for example) have moved away from the use of RSA to instead prefer ECC because of forward secrecy.

So, my question is, do we still need RSA?  Is there any situation where it cannot be replaced by an ECC scheme instead?

More specifically, if the answer to the above is no, are there any circumstances in which RSA is better suited than the ECC counterpart?  Why is it still in use from a practical point of view?

Summary: ECC+symmetric algorithms can do almost anything RSA+symmetric algorithms commonly do (plus forward secrecy where RSA struggles). But RSA is often preferred, sometime rightly so, in particular due to it's superior performance for the public-key side.

At common security levels, the public-key RSA operation (used for signature verification, and on the encryption side of public-key encryption) remains significantly more compute-efficient than anything ECC-based has to offer. That's an advantage in some applications, including:

For the signature of a digital certificate: it can be verified many millions times in its active lifetime, when it is generated only once; the cost of its signature can be neglected entirely, while the power or/and time saving by the users of the certificate becomes sizable. That is part of why CAs typically use RSA public/private key pairs.
For data (including code) signature verification by underpowered devices (IoT).
For asymmetric encryption by underpowered devices (IoT), complemented by symmetric crypto for large ciphertext.

To illustrate: with $e=3$, on a CPU with 32×32→64-bit multiplication, a straightforward RSA signature verification with $n$-bit public modulus uses about $4(n/32)^2$ multiplications (e.g. <17k multiplications for $n=2048$), while ECC-based crypto in field $\Bbb Z_p$ with $n$-bit $p$ requires about $k\,n(n/32)^2$ multiplications for some integer $k$ typically 12 or more (e.g. 200k multiplications for $n=256$). In practice, even when using RSA with $e=65537$ (like 8 times slower than $e=3$) perhaps due to diktat by authorities, RSA typically keeps a sizable advantage because it is easier to optimize.

Also, RSA signature with message recovery is sometime what minimizes the size overhead of signing. E.g. for a 350-octet payload to be conveyed signed, the signed message is

384-octet with RSA-3072 per ISO/IEC 9796-2 scheme 3 and SHA-256
398-octet with ECPVS (ANS X9.92-1) and SHA-256
414-octet with ECDSA/EdDSA and SHA-256

Thus when size is a hard limit, RSA signature with message recovery might be the only option. Admittedly, that applies only for a narrow interval of size: the gain is a fraction of the hash size thus becomes proportionally negligible with larger payloads, and ECC wins for smaller ones (because RSA cryptograms have the size of the public modulus). It happens that the interval where RSA wins is close to the maximum practical capacity of a 2D-code (e.g. QR-code).

That answer points another rather specialized use case of RSA where it shines: deterministic, size-preserving public-key encryption.

That answer points yet other practical reasons why RSA remains widely used.


How is a PRP different from PRF? Both can be inverted to get the same input PRP is said to be a bijective function which means that there is a one-to-one mapping with the output. And hence the output can be inverted using the decryption algorithm to get the same input.

Question is how's PRF different from that. If it is not bijective, how are we going to decrypt the message?

In counter mode it is said that we are using a PRF and not PRP (unlike CBC) i.e. we are not using the decryption capabilities of block cipher. What does this mean? We are anyway going to decrypt the message by XORing the IV counter and the key with the cipher text. Then why is it said that we are not using the decryption capabilities? and how is it different from PRP that has to have a decryption algorithm?

Indeed as you noted the primary difference between a PRP and a PRF is that a PRP must be bijective whereas a PRF doesn't have to. This also means that PRFs admit collisions, that is there may exist a key $k$ such that for two different inputs $x,x'$ $F_k(x)=F_k(x')$, whereas this is guaranteed to be impossible for PRPs.

  In counter mode it is said that we are using a PRF and not PRP (unlike
  CBC) i.e. we are not using the decryption capabilities of block
  cipher.

A different way to think about counter-mode is to consider the keystream blinding the message. Then on the receiving end you reproduce the blinding and unblind the message.

Whereas with other modes like CBC you actually run your message through your function, which means you need to have a bijection in order to recover your original message unambigously.


Small roots of bivariate modular linear equation? Say I have a simple affine relationship between two variables $x$ and $y$ in a field $\mathbb{F}_p$ ($p$ is a large security parameter): $ax + by + c = 0$

What algorithm would be appropriate to find all roots $(x,y)$ such that $x < X$ and $y < Y$ for some small $X, Y$ compared to $p$?

Every algorithm I find seems like overkill, dealing with systems of several equations, higher degree or more variables. Would Coppersmith method still be the best here? LLL can be used to find one root but I don't see how to find the other ones.

All solutions of such an equation in $\mathbb{Z}$ are of the form $x=x_0-\frac{ka}{gcd(a,b)}, y=y_0+\frac{kb}{gcd(a,b)}$ for $k\in \mathbb{Z}$, where $(x_0,y_0)$ is any solution.

Look at these numbers modulo $p$ and you'll have a parameterization of a family of solutions to your equation. This might help you find some small solutions, depending on the size of your parameters $X,Y$.

Now, note that the equation $$ax+by=c+p$$ will also give solutions (or replacing $p$ by any $\theta p$ for $\theta\in \mathbb{Z}$), since when in $\mathbb{F}_p$, the equation is the same. I'll let you think if the solutions are the same.


Could randomisation make for a better book cipher? Suppose that the file linux.words is used as the "book".  This is a publicly available list of just shy of half a million words.  And suppose that this book is used, not in its native alphabetic order, but in some randomised order.  The number of possible random arrangements is a decimal which is over two million decimal digits long. The cipher text will be a stream of numbers which index into the chosen random arrangement of the "book".  Does this approach make for an improved book cipher?

From the Wikipedia page on Book ciphers:

  Essentially, the code version of a "book cipher" is just like any
  other code, but one in which the trouble of preparing and distributing
  the codebook has been eliminated by using an existing text. However
  this means, as well as being attacked by all the usual means employed
  against other codes or ciphers, partial solutions may help the
  cryptanalyst to guess other codewords, or even to break the code
  completely by identifying the key text. This is, however, not the only
  way a book cipher may be broken. It is still susceptible to other
  methods of cryptanalysis, and as such is quite easily broken, even
  without sophisticated means, without the cryptanalyst having any idea
  what book the cipher is keyed to.

So you would effectively have a very weird book that would be unknown to the attacker, but that isn't enough to make it secure.  In particular, (link)

  If you know 1,000 words, you will be between a functional beginner and
  conversational level in English.  In most of the world’s languages,
  500 words will be more than enough to get you through any tourist
  situations and everyday introductions.

Randomizing the word order wouldn't change the frequency clues.  Not being able to guess the book would add a small amount of additional security, but not enough to give it any meaningful improvement over a traditional book cipher.


Text in random image encoder: is it flawed? I have created a small cryptographic programme:

You input your text
A random image is generated
Random coordinate pairs in number equal to the chars of the message are generated.
The red component of the points at the coordinates given above is modified to become equal to the ASCII value of the letter.
The text can now be read only knowing which points actually encode the letters and which other points are just noise.

Can you tell me any flaws in the approach that would make my message crackable (having only the image and not knowing the key used)?

If you are wondering about the implementation details, the actual programme is provided down below:

from __future__ import print_function
from PIL import Image
import random

SIZE = 500
MESSAGE = "Boh i don't know what I know to be knowing"
RELEVANT_POSITIONS = [(random.randint(0,SIZE),random.randint(0,SIZE)) for _ in range(len(MESSAGE))]
FILENAME = "Crypted.png"

IMAGE = Image.new("RGB", (SIZE,SIZE))

def from_letter_to_colour(letter):
    value = ord(letter)
    return (value,random.randint(0,256),random.randint(0,256))

def from_colour_to_letter(colour):
    return chr(colour[0])

def draw(position,colour):
    IMAGE.putpixel(position,colour)

def random_colour():
    return (random.randint(1,256),random.randint(1,256),random.randint(1,256))

def all_positions():
    return ( (x,y) for x in range(SIZE) for y in range(SIZE) )

def get_pixels(image_name):
    image = Image.open(image_name)
    pixels = image.load()
    return pixels

def create_random_image():
    for position in all_positions():
        draw(position,random_colour())

def encode_message(message):
    create_random_image()
    for index,position in enumerate(RELEVANT_POSITIONS):
        try:
            draw(position,from_letter_to_colour(message[index]))
        except IndexError:
            break
    IMAGE.save(FILENAME)

def test_encode_decode():
    for char in ( chr(i) for i in range(1,128)):
        assert from_colour_to_letter(from_letter_to_colour(char)) == char

def decode_message():
    message = []
    pixels = get_pixels(FILENAME)
    for position in RELEVANT_POSITIONS:
        x,y = position
        message.append(from_colour_to_letter(pixels[x,y]))
    return ''.join(message)

def main():
    print("The key is: {}".format(RELEVANT_POSITIONS))
    encode_message(MESSAGE)
    print(decode_message())

if __name__ == "__main__":
    test_encode_decode()
    main()

This is flawed:

Cracking: The format leaks information on how often specific characters occur.
For instance, if input message contains 6 o letters, there is likely much more 111 values than the most other values present. Such a small biases are sufficient for cryptoanalysis to break the message in many cases.

Also, random.randint does not return random number suitable for cryptographic purposes, it means the scheme can be possibly broken. (See https://docs.python.org/2/library/random.html for guidance, which tells the function shall not be used for cryptographic purposes). In current versions of Python, the generator is Mersenne Twister, which is easy to reverse (break). (See http://b10l.com/reversing-the-mersenne-twister-rng-temper-function/). Long story short, an attacker can easily use the produced image to find the original seed of the random number generator and thus, be able to generate the key.

The system is not very space efficient: there is large overhead, the produced message is much larger than the input. (The technique primarily sounds more like steganography instead of cryptography.) Also, the key is longer than the message, and variable length.


Is there a standard padding/format for RSA Blind Signatures? I'm working on a RSA blinded signature scheme. RSA Blind signatures are discussed in Chaum's original paper and other places like wikipedia.

The descriptions of RSA blind signatures are straight forward, but they seem to use the original message rather than a formatted or padded message. According to Rabin (1979) we should be using at least H(m).

My question is, is there a standard covering RSA Blind Signatures we should be using? Is there an accepted way to format the message when used in a RSA Blind Signature scheme?

I know the question has some open ends, like security goals being under specified. But we are looking for something that provides intractability of signature-forgery and enjoys some interoperability. I'd like to say we want all the security properties detailed by Bernstein in RSA signatures and Rabin–Williams signatures: the state of the art, but I won't go that far.

Related, here are two questions that explain how to provide a padding function at the author (as opposed to the signer). Both appear to be ad hoc methods.

Usability of padding scheme in blinded RSA signature?
RSA blind signatures in practice

There are random oracle model security proofs for RSA-PSS and RSA-FDH.  There are standards for RSA-PSS but it requires randomness from the signer and thus does not work for blind signatures.  RSA-FDH works with blinding.

RSA-FDH might appear in some standard somewhere, but honestly "full domain hash" is kinda self explanatory to a cryptographer.  As an FDH example see  https://git.gnunet.org/gnunet.git/tree/src/util/crypto_kdf.c#n113 for the RSA code in https://git.gnunet.org/gnunet.git/tree/src/util/crypto_rsa.c used in GNU Taler.

There is afaik no standard for blind signatures per se, but you must use a full domain hash for both the message and the blinding factor, well formally the blinding factor is a FD-PRF, but that's the same code.

If you use too small a hash function for the message, then an adversary can factor message hashes, find enough colliding factors, and forge messages.   Or worse since even the basic signature scheme security proof requires FDH.  All the security proofs that protect against such "one more forgery" attacks require both FDH and the non-standard RSA-KTI "known target inversion" assumption.

If you do not use a FD-PRF for the blinding factor then you'll leak enough information with each message that an adversary can deanonymize you after well under 100 messages.

I'll emphasize:  If you have a 2048 bit RSA key n then your domain for the hash is [0,n) so you must generate a 2048 bit number r, test if it is less than n, and repeat if not.  You do not have an FDH if you merely generate one 2048 bit or 2027 bit number and use it directly.  RSA is not forgiving about this because an RSA modulus lands roughly half way between powers of two, unlike say elliptic curve group orders which are chosen very close to a power of two.


Determine AES key given encrypted and unencrypted files Given an encrypted file, the original unencrypted (cleartext) file, and knowledge of which AES encryption algorithm was used, is it possible to determine the key that was used to encrypt the data in a reasonable period of time?

I am not looking for details on how AES works, just a simple answer.

The simple answer is no, known plaintext attacks should not be possible on an AES-encrypted file, assuming that AES is applied correctly. No information about the encrypted file or key should be leaked even if the adversary can guesss  the contents of "the original unencrypted (cleartext) file".

Beware that any mistake into a protocol specification or implementation may negate the security of AES - and this could include the security of the key used. Point in case: some "AES encrypted" USB devices stored the key next to the ciphertext, in case somebody forgot the password.


Proof that MAC is insecure I've just started studying MACs and I faced the following challenge:

Let $F$ be a PRF over $(\mathcal{K,R,X})$ where $\mathcal{X} = \{0,1\}^{32}$

Let $\mathrm{CRC32}(m)$ be a function that takes inputs $m \in \{0,1\}^{\le \ell}$ and output a 32-bit string and

$\mathrm{CRC32}(m_1) \oplus \mathrm{CRC32}(m_2) = \mathrm{CRC32}(m_1 \oplus m_2)$.

Let's define a MAC system $(S,V)$ as:

$\quad S(k,m) = \{r \small\xleftarrow[]{R}\mathcal{R},\quad t \leftarrow F(k,r) \oplus\mathrm{CRC32}(m), \quad \text{output} \;(r,t)\} $
$\quad V(k,m,(r,t)) = \{ \mathtt{accept} \; \text{if} \;\; t = F(k,r) \oplus\mathrm{CRC32}(m), \quad \mathtt{reject} \; \text{otherwise}   \}  $

How can I prove that this MAC is insecure?

After thinking a lot about how an attacker could send queries (sending messages $m_i$ and receiving its correspondent tags $t_i$) to find an existential forgery, I read that although the attacker can send several queries, they may not help, so I wonder what else can I try in order to break it.

Fix $k$, $r$, and $m$.  Consider $t = F(k, r) \oplus \operatorname{CRC32}(m)$.  Can you relate it to $t' = F(k, r) \oplus \operatorname{CRC32}(m \oplus \delta)$?


what is meaning of operator " := " in cryptography? I've seen := used in several cryptography papers where the this symbol has been used instead of assignment operator ($  \leftarrow $ ) or equal sign (=), but never with an accompanying explanation. It's not exactly possible to search the precise meaning of operator ":= ". What is the exact meaning of this symbol in terms of mathematics in  cryptography is concerned.

Lindell and Katz, in their book Introduction to Modern Cryptography, use;

$\leftarrow$ as possibly probabilistic process assignment.
Some others use $\stackrel{r}{\gets}$, $\stackrel{\\\$}{\gets}$, $\gets_{R}$, and $\gets_{\\\$} $
Actually, the $\gets_{\\\$}$ fairly common.

$:=$ for the deterministic process assignment.
In some context, the $\leftarrow$ can be the same as Lindell and Katz 's $:=$. This former is more common. In some contexts, it is $=$

$=$ for equality

$\stackrel{def}{=}$ for defining a variable.

More on $\leftarrow$ and variants

When $X$ is a value, the $x \leftarrow X$ is used for  deterministic assignment, and

When $X$ is a probability distribution, the $x \leftarrow X$ is used for sampling.

When $X$ is a set, the  $x \leftarrow_R X$  is used to denote sampling from the uniform distribution over the set $X$.

Note:

In reading books, one needs to check the existence of the notation page(s) or the notation section. Many good books have a section like L&K's Index of Common Notation section (page #533 in the second edition).
In the articles, the authors usually define them where they first occur, therefore, look for the first occurrence of the symbol.


Am I correctly understanding TLS 1.2 PRF (Pseudorandom Function)? According to RFC 5246 Section 5

PRF(secret, label, seed) = P_<hash>(secret, label + seed)

and

P_hash(secret, seed) = HMAC_hash(secret, A(1) + seed) +
                       HMAC_hash(secret, A(2) + seed) +
A(0) = seed
A(i) = HMAC_hash(secret, A(i-1))

According to my understanding first iteration of P_hash is

P_hash(secret, seed) = HMAC_hash(secret, A(0) + seed) and A(0) = seed

So,

P_hash(secret, seed) = HMAC_hash(secret, seed + seed)

Is it correct? Or is the first iteration rather

P_hash(secret, label) = HMAC_hash(secret, A(1) + Seed)

and

A(1) = HMAC_hash(secret, A(0))

Simply by substituting A(0) in A(1), and then A(1) in P_hash, one obtains your second suggestion. I don't understand how you came up with the first one?


Security of N bit HMAC Lets say that I am using 128 bit HMAC. How many operations are needed to find a "non secure" message. Is a birthday attack possible?

The short answer is: $2^{128}$ operations, no known birthday-like attack.

The long answer: when HMAC was first published, it came with a security proof, tailored for iterated constructions like Merkle-Damgård. In a MD hash function (MD4, MD5 and the whole SHA family are MD hash functions), the data to hash is processed by blocks with a compression function: the compression function takes as input the block and the current state (the state is a 128-bit value for a function with a 128-bit output), and produces the new state (which will be used as input for the processing of the next block). The final state is the function output.

The original proof claimed that if the compression function is a PRF (i.e. the choice of a block value "selects" the compression function as if randomly among functions which take the state as input and produce the corresponding output) and the hash function is collision-resistant (in a "weak" way; it needs not be resistant to all kinds of collisions) then HMAC is secure. That proof worked up to $2^{n/2}$ invocations of the compression function (for a hash function with a $n$-bit output). Later on, Bellare published a new security proof which removes the condition on weak collision resistance, and enhances proven security up to $2^{n}$ .

Now the fine print: the security proof works only as long as the PRF assumption holds. However, if the PRF assumption holds, then the hash function which uses that compression function in the MD construction is necessarily resistant to collisions up to $2^{n/2}$. Therefore, if a MD-like hash function is proven not to be collision resistant up to $2^{n/2}$, then this implies that its underlying compression function is not as PRF as it should. This is true, in particular, for MD4, MD5, SHA-0 and SHA-1. For these functions, the PRF assumption cannot be held, hence the HMAC security proof is not applicable to HMAC/MD4, HMAC/MD5, HMAC/SHA-0 and HMAC/SHA-1. This does not mean that we know a way to turn collision attacks into attacks on HMAC. Indeed there is no known attack faster than $2^{128}$  on HMAC/MD5. However, there is a known forgery attack on HMAC/MD4. Note that this attack has cost $2^{58}$, which is quite a lot (and explains why the attack was never actually demonstrated), whereas resistance of MD4 to collisions is, by itself, zero (generating the collision takes less time than simply hashing the two messages to verify that it works).

Also, all these proofs are for MD-like constructions and do not apply, directly, to non-MD functions. However, one can say that HMAC is defined as it is, with its two nested hash function invocations, precisely to overcome some shortcomings of the MD construction. So there is "no reason" why a non-MD hash function would not do fine in HMAC. Most SHA-3 candidates include statements and/or proofs of security of the hash function when used in HMAC.


Threshold Signatures for RSA and DSA I have a few questions relating to threshold signatures: a scheme where $n$ participants hold a key share and any $t$ of them can conduct a protocol using their shares that results in a valid RSA or DSA signature being applied to a known message.

Questions

Several techniques exist for threshold RSA (1,2) that seem reasonably efficient. Is there any impedance to using these protocols with a standards-compliant version of an RSA signature (such as RSA as used in X.509 for SSL/TLS certificates)?
Are there any techniques for threshold DSA (aside from this 2-out-of-2 case)?
Are there any tools available that implement a threshold signature scheme? A tool that would allows each participant to contribute to the DKG, and would later generate their contribution to the final signature on a shared message given their key share?

It is my belief that (1) is standards-compliant as padding can be done prior to signing without reference to the signing key, (2) does not exits, and (3) does not exist either. But now that this site exists, I figure why not ask?

EDIT: Regarding (2), there are techniques for DSA. I missed them because they are proposed for "DSS" instead.

Regarding your first question, it is my understanding that DKG techniques are in practice mainly used for offline signing, such as when a certificate authority issues new intermediate CA certificates. Using DKG for online signing, such as server side SSL/TLS, is not a problem that is solved by the papers you refer to, since the threat scenario is significantly different from that of offline signing. More precisely, to guard yourself against unauthentic signing requests in the online case, the front end server has to authenticate itself to the back end key share servers, but if it is able to do that, it is able to store a private (or secret) key securely and doesn't really need DKG in the first place.


Difference between hierarchical and multi level secret sharing In this paper, the definitions are simply as follows.

Multi-Level secret sharing: Higher level participants can help lower participants to get the secret.

Compartmented secret sharing: Each level participants has to get its own secret. (No help from higher level participants)

According to this paper

I found that Disjunctive Multi-Level secret sharing is identical to Multi-Level secret sharing and Conjunctive Multi-Level secret sharing is identical to Compartmented secret sharing.

Is above statement true?

My doubt is what is the difference between hierarchical secret sharing  and multi-level secret sharing?

Is hierarchical secret sharing same as Disjunctive Multi-Level secret sharing?

If I add a restriction to the compartmented secret sharing that 'participants at level $i$ can recover its secret only if participants at level $i-1$ recovers their secret', then what we can call this type of secret sharing?

In a multilevel secret sharing scheme there is only one secret $S$ that all levels seek to find. In a compartemnted scheme we can have multiple secrets that correspond to each level that must be found before $S$ can be recovered. In a compartmented scheme a set of compartments must work together to recover the secret, where each compartment contains a number of participants. In a hierarchical scheme participants from different levels can work together to discover the secret, but they don't have to.

As far as I know hierarchical is interchangeable with multilevel. A disjunctive scheme is indeed simply a hierarchial scheme where participants from different levels can work together but can also find the secret by cooperating with participants on their own level. However a conjunctive scheme is what Tassa terms a hierarchial threshold scheme (see: http://www.openu.ac.il/personal_sites/tamirtassa/download/journals/htss.pdf).

To give an example of this type imagine we have a scenario where there is a safe at a bank that must be opened by employees, however they cannot do this without being in the presence of two senior employees or a manager. This type of scheme is not the same as a compartmental scheme as not all levels must cooperate together to find the secret.

Additionally I think Nojoumian and Stinson have done something similar to what you propose: http://isyou.info/jisis/vol5/no2/jisis-2015-vol5-no2-02.pdf

Hope this helps.


Is there any recent cryptographic algorithm especially designed for low-level processors? Most modern algorithms require relatively large amount of resources.
Is there any recent (and freely usable) encryption/decryption algorithm which is specially designed for low-level microcontrollers in mind? This means it has to run fast, (on a very simple, 8 or 16 bit, 10-20 MHz processor), be small (few hundred bytes to few kilobytes) and use as little RAM as possible.

The key is "modern" because if I took something designed in the 1970's (which would satisfy the requirements for a simple and low-level processor) it might have big security vulnerabilities.

If only the decryption part satisfies the requirements, it's also enough.

In the context, one option would be AES in CTR mode with the XOR between ciphertext and keystream on the PC side (saving most of the bandwidth in the PC to Low-level processor direction). CTR mode allows direct access to any portion of the plaintext. AES is easy to implement on an 8-bit CPU, reasonably fast, and low on resources. As a bonus, protecting AES against side-channel attacks is well studied (although the weakest point likely will be different: obtaining the whole plaintext or keystream once, and storing that).

If AES is not fast enough, and about 260 bytes of RAM are available, and the plaintext can be divided into relatively large blocks (like 1024 bytes or more), and we replace recent by tried and tested, there is RC4 with an appropriate key setup (e.g. append 32-byte key to 8-byte block address, use that as the RC4 key, discard the first 256 bytes produced by RC4).

Update: beware that both methods allow the user to change bits of plaintext just by flipping the corresponding bits of ciphertext; see that other answer if the integrity of plaintext is required (this also requires assuming the program on the PC is not altered).


Delayed tag checks in AES-GCM for streaming data There is currently a GitHub discussion on .NET not supporting AES-GCM for any streaming data since releasing decrypted data prior to tag checks somehow reveals the plaintext or the AES key (or some such undocumented catastrophic failure). A lot of chatter between two choices:

1. Allowing AES-GCM for streaming data

Release data as it is decrypted and alert caller if / when tag check fails. Most popular AEAD constructs (e.g. AES-CBC-HMACSHA256) are encryption and authentication as two separate pipelines. So one can at least momentarily downgrade to privacy-only mode during decryption (i.e. AES-GCM => AES-CTR mode) but upgrade back to privacy and authentication mode after the GHASH tag checks out. The caller is responsible for alerting users or buffering data if situation demands.

2. Permanently disallow AES-GCM for all streaming data

This eliminates AEAD (or specifically AES-GCM) from streaming and limits them to regular privacy-only mode permanently. Or forces users to bolt-on authentication themselves, which revisits the original problem. Or worse, users consider streaming as a dead-end case and skip any encryption at all.

Question: Assuming everything else is ok (fresh keys, unique iv, long tags, under GCM limit etC), is allowing streaming (#1) with AES-GCM ok? If not, what's the catastrophic failure and what choice other than AEAD does streaming have? If the case for AES-GCM differs significantly from generalized AEAD, please address that too.

The Windows 'kernel' crypto layer (bcrypt), OpenSSL, Bouncy Castle (C#) and Java Cryptography Architecture all allow for streaming/continuation.

Also, the scope of this is the crypto API itself, NOT a high level protocol.

You can have AES-GCM and streaming at the same time.  But:

Do not operate on unauthenticated data!

Treat unauthenticated data like nuclear waste.

The fact that the AES-CTR out of which AES-GCM is built technically can provide access to data before the authentication tag is verified is a red herring.  Allowing access to the data before verifying the tag, and requiring a separate API call to verify the tag, is a loaded semiautomatic foot-pointed gun.  Don't do it!

Do not allow arbitrarily long messages before you verify authentication tags!

Arbitrarily long messages will tempt you to act on the content of the message before you can verify the authentication tags.

Resist the temptation!  Al you have to do is break long messages into chunks of bounded size so that you aren't even tempted to do this.  You can even use a chunk sequence number for the AES-GCM nonce, or you can use a scheme like miscreant that handles chunking for you.

Fogeries are bad news!  Every program is an interpreter for a programming language that is its input—sometimes that language is Turing-complete, or even if not you may still enable an adversary to control a weird machine you never even thought existed in ways you never imagined.  The cryptography lets you ensure that only the peer you're trying to have a conversation with gets to program your program, and not anyone else on the internet.

If the governor of Arkansas acted on a series of forged execution orders, and only afterward checked all the judges' signatures on them, people would be even more upset than they already are about the lethal carceral state.  Don't let your program be that governor!

See an earlier answer about xsalsa20poly1305 for elaboration on the performance and denial-of-service implications of bounded-size chunks in a cryptosystem of the same type as AES-GCM.


Parameter $f(x)$ in binary ECDH exchange protocol In the binary case of Elliptic-Curve-Diffie-Hellman (ECDH) exchange protocol the domain parameters are $T = (m,f(x),a,b,G,n,h)$. What is the meaning of parameter $f(x)$?

You may find the definition of the protocol in wikipedia I've gone trough other books and materials but found nothing.

This Wikipedia article is simply not complete. They refer to the NIST Special Publication 800-56A (http://csrc.nist.gov/publications/nistpubs/800-56A/SP800-56A_Revision1_Mar08-2007.pdf), which is now replaced by a new version (http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Ar2.pdf).

It seems the Wikipedia article refers to the domain parameters as indicated on page 41 for ECC CDH, of the form $\left(q,FR,a,b,G,n,h\right)$. The explanation of $FR$ is stated on page 10 of the same document:

"Field Representation indicator (an ECC domain parameter); an indication of the basis used for representing field elements. FR is NULL if the field has odd prime order or if a Gaussian normal basis is used. If a polynomial basis representation is used for a field of order $2^m$, then FR indicates the reduction polynomial (a trinomial or a pentanomial)."

As SEJPM commented, this is the polynomial which defines the field $GF(q)$. Note that up to isomorphism there is only one field $GF(q)$, but there are many ways to represent it (by choosing different $FR$). Hence it is important to specify which $FR$ was chosen for compatibility.


Why verify padding at all? Whenever a ciphertext is decrypted using a block-cypher, we need to remove the padding. There are different ways to add padding, but they usually set the last byte of the last block to the number of padding bytes that were added and need to removed (e.g. we added 5 bytes, so we set the last byte to 0x05).

My question is: why do we need to verify padding? Why not read the last byte, remove that many bytes from the message, and be done with it?

Emitting a padding error sometimes catch integrity problems, but opens one to attacks like Padding Oracle, which is able to retrieve the entire plaintext in certain situations. It seems to me this is a terrible trade-off. What's the reasoning behind padding verification?

First of all, a more usual padding scheme would add 5 times the same byte 0x05 (in your example) so the check not just removes 5 bytes, but also checks that the 4 bytes before it have the same value. But let's assume your scheme (which is underspecified: what to put in the bytes before? Zeroes, or random values?) for now.

What if you cannot remove that many bytes? Do you allow for final bytes that exceed the block length (so remove more than one block)? (TLS does do this.) Do you just discard the data? But that's also observable, probably. And if the length of the final output is somehow observable, you leak the final byte of the last block which could also be used for a padding oracle style attack.

In general, use a cryptographic MAC to protect your ciphertext, and verify it first. Emit those errors. Then padding errors should not occur at all.


What information to include is the 'info' input for HKDF? The RFC states the following:

  3.2.  The 'info' Input to HKDF

  While the 'info' value is optional in the definition of HKDF, it is often of great importance in applications.  Its main objective is to bind the derived key material to application- and context-specific information.  For example, 'info' may contain a protocol number, algorithm identifiers, user identities, etc.  In particular, it may prevent the derivation of the same keying material for different contexts (when the same input key material (IKM) is used in such different contexts).  It may also accommodate additional inputs to the key expansion part, if so desired (e.g., an application may want to bind the key material to its length L, thus making L part of the 'info' field).  There is one technical requirement from 'info': it should be independent of the input key material value IKM.

I'm still a little bit unclear on how to use this input.  Does the 'info' input function as somewhat of a salt?  If I'm developing a multi-user application, and each user:

uses HKDF to expand 16+ psuedo-random byes into a larger key
has a unique email address
uses the expanded key for a specific algorithm of their choosing

Would it be appropriate to use the user's email address, and the name of the algorithm for which the key will be used? Any analogies for better understanding the usage of this input would be appreciated.

No, the info is not a salt. The input key material for a KBKDF (key based key derivation function) should already be pseudo-random, and should therefore contain enough entropy to not need a salt.

If the user already has a unique 16+ pseudo-random bytes key then there is little reason to use the email address as part of the info. The email address could be used to make the derived key specific to the user, but that is already the case (in your example).

The main reason for a KBKDF is to create more keys or longer keys. You would need to use the algorithm name as part of the info when the algorithms would otherwise use the same key material.

The info is the key derivation data. You use identical input key materials to create multiple derived keys. The info makes the distinction between the keys. The KBKDF makes sure that the keys are indistinguishable from pseudo random numbers (and thus independent of each other).

Example uses: create a encryption and mac key from the same input key material (info is ASCII encoding of "ENC" and "MAC" or a counter value 1 or 2).

Another example: encrypt files with the same key without using an IV: input of the info part is the UTF-8 encoding of the file name.


Is AES-GCM suitable for per chunk encryption? I was looking through Google's encryption flow and noticed that they split each file into chunks and then encrypt each chunk individually with AES-GCM with its own key.

Since AES-GCM starts to get vulnerable around $2^{48}$ messages (though, some people suggest $2^{36}$), how can they keep things secure if they have millions of users uploading files constantly?

I'm new to cryptography, so excuse my ignorance. Does the $2^{48}$ limit only actually matter on a per user basis or is it in general? I wanted to do try something similar using AES-CBC with a SecureRandom IV and HMAC for per chunk encryption since you don't have to worry about the collision. However, seeing their encryption flow, I wanted to learn more about what is the proper way of going about things.

The limit is on a per-key:nonce basis. As long as the key or nonce are changed between messages before the limit, there will not be any problems. Different users are using different TLS sessions (which uses 96-bit nonces), which means different keys and nonces. From Wikipedia's page on GCM:

  GCM has been proven secure in the concrete security model. It is secure when it is used with a block cipher that is indistinguishable from a random permutation; however, security depends on choosing a unique initialization vector for every encryption performed with the same key (see stream cipher attack). For any given key and initialization vector combination, GCM is limited to encrypting 239−256 bits of plain text (64 GiB). NIST Special Publication 800-38D includes guidelines for initialization vector selection.

If TLS is not the protocol in use, then it depends on a few factors such as the size of the nonce (bigger is better) and whether or not it is random or sequential (sequential is better). In general, a competent cryptographer will not select insecure parameters. If you are trying to design your own encryption utility, you should be using an easy to use and foolproof library, such as libsodium.


Does still make sense to use SHA1? I'm working with Arduino and hash-based signatures which are signature schemes that use only hash functions. Due to the constraints of an Arduino I was thinking about using SHA1 as the underlying function of my hash-based signature. But I'm not sure if it still makes sense to use SHA1 due to its vulnerabilities. Is there a scenario in which would be acceptable to use SHA1?

No, use SHA256.

If you look at https://bench.cr.yp.to/results-hash.html it seems that SHA256 would probably be the better choice concerning speed as well. Therefore I don't see a good reason to go with SHA-1.


Static vs ephemeral diffie-hellman I feverishly searched the web and couldn't find a clear explanation about what exactly is "Ephemeral diffie-hellman". Let's briefly recall how diffie-hellman basically works:

Bob and Alice agree publicly on a generator ($g$) and a prime modulo ($p$)
Bob selects a private integer ($b$) and computes $B=g^b \bmod p$. He then passes $B$ publicly to Alice
Alice selects a private integer ($a$) and computes $A=g^a\bmod p$. She then passes $A$ publicly to Bob.
Bob computes $K = A^b\bmod p$
Alice computes $K = B^a\bmod p$

So now Bob and Alice both have $K$.
The explanations I see on the web are all sorts of:

Ephemeral Diffie-Hellman (DHE in the context of TLS) differs from the static Diffie-Hellman (DH) in the way that static Diffie-Hellman key exchanges always use the same Diffie-Hellman private keys. So, each time the same parties do a DH key exchange, they end up with the same shared secret.

First to verify some issue: Are "private keys" in the context of diffie-hellman refer to the private $a$ and $b$ that Alice and bob privately select respectively? I'll assume they do, if not - correct me please.
Now, what I don't understand here is, what does it mean that "static DH exchanges always use the same Diffie-Hellman private keys."? I mean:

What is considered an exchange? A session of information exchanging between to parties?
If so, does static DH refer to exchanges between the same two parties?
If not so, considering that, seemingly, using static DH also requires the use of the same $g$ and $p$, how does using static DH will always generate the same $K$?

It'll be great if someone could clarify this whole subject. Thanks

Are "private keys" in the context of diffie-hellman refer to the private $a$ and $b$ that Alice and bob privately select respectively?

Yes, correct. Similarly, $A=g^a\bmod p$ and $B=g^b\bmod p$ are also called the "public keys".

What is considered an exchange? A session of information exchanging between to parties?

An exchange is an execution of the Diffie-Hellman protocol. This happens whenever either a party feels like it or a party has forgotten the resulting shared secret from the last execution. In the context of the internet this usually means that if you connect to, say, Stack Exchange today it will run a Diffie-Hellman exchange. Then when you shutdown your computer it will "forget" the resulting shared secret $K$ and tomorrow when you connect to Stack Exchange again, it will have to run another Diffie-Hellman exchange.

If so, does static DH refer to exchanges between the same two parties?

In a static exchange usually both parties always reuse their private keys, which implies that if they re-run the Diffie-Hellman exchange more than once with each other they always get the same shared secret $K$.
Indeed getting a shared secret the same shared secret between Alice and Bob and Alice and Charlie has a negligible probability if everyone involved picked their private keys properly and the protocol was followed.


Is there a quick method of listing certain elements of a cyclic group? I'm studying applied cryptography and stumbled upon the following question to practice the knowledge about Congruence, Groups etc.

"List all Elements $x$, where $x^2 = 2$ in $\mathbb{Z}_{31}$

Okay, so the naive approach would be to iterate the group, multiply the element with itself and check if its residue modulo $31$ would be $2$.

So we are searching for every element which has a quadratic residue of $2$ in $\mathbb{Z}_{31}$.

Is there any "pen and paper" solution to do this, without having to iterate every element? Is there a theorem which could be used here?

Since this is a field, you know that the polynomial $x^2-2=0$ may have up to 2 roots, no more. You could use the quadratic formula (since the polynomial ring over a field is an integral domain) but this would require the extraction of a square root. But it is certainly more efficient than checking all elements.

Also if if $a$ in $x^2-a$ is a square then you can factor $(x^2-a)=(x-b)(x+b)$ where $b^2=a.$


Good Diffie Hellman Encryption Method I've just made my own implementation of Diffie Hellman in nodejs (its for a project of mine). However the shared keys are integers, I want to use those integers as a key to encrypt data. This is an example output:

Publicly Shared Variables:

    Publicly Shared Prime:  9811

    Publicly Shared Base:   844

Private Variables:

    Alice Secret:   6

    Bob Secret:   15

Alice Sends Over Public Chanel:  905

Bob Sends Over Public Chanel:  1168

------------

Privately Calculated Shared Secret:

    Alice Shared Secret:  3793

    Bob Shared Secret:  3793

What would be the best encryption method, using the key of those integers. Sorry this is a bit hard to explain. Thanks alot!

What would be the best encryption method[...]?

The standard approach is quite simple. You have a Diffie-Hellman shared secret $K$. Because $K$ is not actually uniformly distributed you run $K$ through a key-based key derivation function (KBKDF) like HKDF (or even a "simple" hash), this is your key $k$ then. Then you use $k$ to symmetrically encrypt (and authenticate) data using a unique nonce for each data packet. You can also derive multiple different keys from the shared secret, e.g. one for each transmission direction.

You may want to note though that your current parameters are a bit on the insecure side being only 12-bit long as opposed to the current standard 2048-bit length.


Sematically Secure McEliece I am read the Lemma 2 (pp13) in the paper "Kazukuni Kobara and Hideki Imai: Semantically Secure McEliece Public-Key Cryptosystems –Conversions for McEliece PKC– (PKC 2001)".

Related to the question "Why… for any $Hash_z$ and any $Gen$?", the author of the paper replies;

  The reason why "for any $Hash_z$ and any $Gen$" is that if the sentence is
    not included the cryptosystem may be broken due to weak $Hash_z$ or $Gen$.

I know the hash strong definition:

There exist no x and x' with x != x' so that h(x) = h(x')

In this case are $x=Hash_z$,  $x'=Gen$" and $h=A$?
Are the $Hash_z$ and $Gen$" from Lemma 2 the same that $Hash_z$ and $Gen$" of Figure 5 of that paper?

I assume that the paper you have read is the paper by Kobara and Imai in PKC 2001 (or its journal version), which proposed a padding scheme for the McEliece PKE scheme. In Lemma2, the authors showed CPA security of the padded scheme.

The first answer is NO. They are not.
Let $C(n,t) = \{z \mid z \in \{0,1\}^n, Hw(z) = t\}$, where $Hw(z)$ denotes $z$'s Hamming weight.
As the authors defined in Section 4.1, $Hash_z: \{0,1\}^* \to C(n,t)$ is a cryptographic hash function and $Gen: C(n,t) \to \{0,1\}^*$ is a PRG.
The second answer is YES. They are same.

In Lemma 2, the authors assume that there exists an adversary A "for any $Hash_z$ and $Gen$" breaking the padded scheme. Here, the authors assume that the adversary works even if we separate $Hash_z$ and $Gen$ as oracles (instead of giving their codes to the adversary). Indeed, the authors modeled $Hash_z$ and $Gen$ as the random oracles in the proof.


Why the differential cryptanalysis complexity is linear with inverse of the probability while linear cryptanalysis is quadratic with the bias inverse? I am trying to understand the analysis of the complexity of Differential Cryptanalysis versus the complexity of linear cryptanalysis.

In differential cryptanalysis the number of required texts is $\mathcal{O} {\left( \frac{1}{p} \right)}$ where $p := Pr(\alpha \to \beta)$ for some differences $\alpha$ and $\beta$

In linear cryptanalysis the number of required texts is $\mathcal{O} {\left( \frac{1}{\epsilon ^ 2} \right)}$ where $\epsilon$ is the bias of some masks, i.e. $\epsilon = | Pr(\lambda \to \gamma) - 1/2|$

What I don’t get is why the complexity became quadratic in linear case? e.g. what if we used the probabilities in linear cryptanalysis instead of biases, why the complexity is not proportional to  $\frac{1}{Pr(\lambda \to \gamma)}$.
I tried to read Ali Aydın Selçuk’s paper On Probability of Success in Linear and Differential Cryptanalysis but I still don’t have an intuition why.

What I don’t get is why the complexity became quadratic in linear case?

Well, in linear cryptanalysis, for each input, we get a bit with a bias of $0.5 \pm \epsilon$, and we need to determine if that bias is $0.5 + \epsilon$ or whether it is $0.5 - \epsilon$
If we were to query a random bit (that is, one with no bias) $n$ times and sum the results, we're going to get a value $0.5n + \lambda \sqrt{n}$, for some distribution $\lambda$ with a standard deviation around 1 [1]; it'll take around $\epsilon^{-2}$ samples for the bias that we're trying to measure to be detectable over the $\lambda \sqrt{n}$ noise that's inherent in the system.
This 'we need to get over the noise within the system' effect doesn't occur with differential cryptanalysis, because in DC, we expect the differential to hold over a number of bits, and so we can essentially ignore the case that the differential didn't hold internally, but the differential just happened to hold on the output.
Actually, if we're working with a truncated differential, this may not be quite as true, and in that case, we may need to worry about false positives, giving us an analysis that's closer to the linear cryptanalysis case...

[1]: Actually, the standard deviation is $0.5$; the slightly smaller expected amount of noise doesn't change the analysis.


AES-ECB as an authentication mechanism ECB is considered to be insecure when used for confidentiality because identical plaintext result with identical ciphertext. But what if we use ECB for authentication?

Assume A wants to transmit an authenticated message X to B. A and B have a shared key. What if A encrypts the plaintext X using AES-ECB and outputs Y as the ciphertext and appends it next to the plaintext X as a MAC? Would that be secure?

Confidentiality is not of importance here. We only need to authenticate the data.

It is not secure, because an attacker can "mix and match" the output blocks from different authentication tags on different input messages, or repeat output blocks for repeated input blocks.

For example, if the attacker knows the tag $F_k(m)$ for a one-block message $m$, then it can forge the correct tag $F_k(m) \mid F_k(m)$ for the two-block message $m \mid m$.

Another attack: suppose the attacker learns the tag $F_k(m_1) \mid F_k(m_2)$ for the message $m=m_1 \mid m_2$, and the tag $F_k(n_1) \mid F_k(n_2)$ for the message $n=n_1 \mid n_2$.  Then it can forge the correct tag $F_k(m_1) \mid F_k(n_2)$ for the message $m_1 \mid n_2$.  More generally, it can forge a correct tag for any message that is made by arbitrarily concatenating blocks from $m$ and $n$.


Fiat-Shamir for $(2n + 1)$ Consider the following $(2n+1)$ protocol:

$\mathcal{P}$ and $\mathcal{V}$ engage in an interaction where $\mathcal{P}$ consecutively sends a message $a_i$ answered by $\mathcal{V}$ with a random challenge $b_i$ for $i = 1,\dots,n$. Finally $\mathcal{P}$ gives a final answer $z$ and $\mathcal{V}$ outputs either $1$ or $0$ (i.e., accepts or rejects the proof) checking the conversation $(x,\{a_i\}_{i=1}^n,\{b_i\}_{i=1}^n,z)$.

The protocol verifies the following properties:

Completeness: If an honest prover $\mathcal{P}$ knows a valid witness $w$ and follows the protocol, then an honest verifier $\mathcal{V}$ always accepts the conversation.
$k$-Special Soundness: From $k$ valid conversations $\{(x,\{a_i^j\}_{i=1}^n,\{b_i^j\}_{i=1}^n,z^j)\}_{j=1}^k$, and  $\{b_i^j\}_{i=1}^n \neq \{b_i^{j'}\}_{i=1}^n$ for all $j \neq j'$, it is possible to efficiently extract a witness $w$.
Honest-Verifier Zero-Knowledge: There exists a polynomial-time simulator that takes $x$ and random $\{b_i\}_{i=1}^n$ and output a valid conversation $(x,\{a_i\}_{i=1}^n,\{b_i\}_{i=1}^n,z)$ with the same probability distribution as conversations between honest $\mathcal{P}$ and $\mathcal{V}$.

This is a non-standard zero-knowledge protocol which I am trying to apply the Fiat-Shamir Heuristic to turn it into non-interactive. I am struggling  with the soundness property, since is quite different from a typicial protocol.

Is there anything in the literature that generalizes the Fiat-Shamir Heuristic to finite $(2n+1)$ protocols? Maybe that can help to solve this problem.

You can find the security proofs for 5-round Fiat-Shamir:

Ming-Shing Chen and Andreas Hülsing and Joost Rijneveld and Simona Samardjiska and Peter Schwabe: From 5-pass MQ-based identification to MQ-based signatures. Asiacrypt 2016. https://eprint.iacr.org/2016/708
Özgür Dagdelen, David Galindo, Pascal Véron, Sidi Mohamed El Yousfi Alaoui, and Pierre-Louis Cayrel. Extended security arguments for signature schemes. Designs, Codes and Cryptography, 78(2):441–461, 2016. https://link.springer.com/article/10.1007/s10623-014-0009-7

Their proof (may) contain (2n+1)-round Fiat-Shamir.


Uniform distribution/randomness of characters in the SHA-256 hash? I'm using the SHA-256 algorithm to generate a number in one of my programming projects. A SHA-256 hash is calculated from three strings: one the user can edit, one the user can view but not edit and one the user cannot view or see until it is changed to a new string.

From the hash, the first two characters are looked at to determine the number. Each of the 256 combinations of two letters/numbers that can appear in a sha256 hash are arbitrarily assigned a value with the following pattern.
aa=1, ab=2, ac=3...fd=84, fe=85, ff=86...97=254, 98=255, 99=256: In the project a number from 1-100 is needed so all of the combinations of two characters are looked at from left to right until a number in that range is found.

After testing this by generating thousands of hashes from seemingly random inputs (with php I made the input md5(uniqid(rand()))) multiple times, the average number from 1-100 was around 51.

Any idea what is causing the number to be weighted more towards combinations from "dc" to "0d" (51-100) compared to "aa" to "da" (1-49)? Is this a flawed way to determine a random number even if the input is random? What if the player has control over one of the strings added to the input like described in the first paragraph?

Note: I don't study cryptography so explanations without intense cryptography jargon would be the most useful!

It may be that you did not actually observe an unexpected deviation from the desired mean of 50.5 for a uniform distribution over integers in [1,100].  However, you say that all combinations of two characters are considered, which I assume to mean that first you look at characters 0 and 1, then characters 1 and 2, and so on.  This means that when you look at characters 1 and 2, since you've already rejected characters 0 and 1, the distribution of character 1 is necessarily biased (there are 156 combinations that lead to rejection, and 16 does not divide this evenly).

To obtain an unbiased sample, you should not reuse any characters.  If you used your same scheme but didn't reuse any characters, you would most of the time generate an unbiased sample but with probability $(156/256)^{32}$ (about 1 in 8 million) you would run out of characters before accepting.  To reduce your chance of running out of characters, you can accept numbers 1 to 200 (but then divide by 2, rounding up).  This reduces your chance of running out of characters to $(56/256)^{32}$ (about 7.56e-22).  You can improve on this by considering blocks of 8 characters (32-bits) or 16 characters (64-bits) at a time.

You can also simplify your method by using the usual hexidecimal convention and relying on existing hex string to integer conversion, or better yet, avoid the conversion completely since the SHA256 hash is always computed as a sequence of bytes, and then converted to a hex string.


LLL - Lattice Reduced Basis Algorithm question? I have two related questions:

Version 1: Let $B=\{b_1,b_2,\dots,b_n\}$ be an orthogonal basis for $R^n$. What is the associated reduced basis obtained by applying LLL algorithm to $B$?

I know how to apply LLL algorithm and I can apply it for  $R^3$  case.  (Since for $n=3$ it takes reasonable time in the exam, this is an exam question by the way.)

But this case is general case for $n$, so I don't know what to do? is there a shortcut to find the reduced basis when the vectors are orthogonal ?

another version of this question is the following:

Version 2: Let $B=\{b_1,b_2,\dots,b_6\}$ be an orthogonal basis for $R^6$ .

Having $||b_1||=||b_3||=1$, $||b_2||^2=||b_6||^2=2$, $||b_4||^2=3,||b_5||^2=4$

What is the associated reduced basis obtained by applying LLL algorithm to this ordered basis $B$?

LLL algorithm has two main parts:

the reduction step: which recomputes the basis vectors aiming to reduce the values of the Gram-Schmidt coefficients to some value smaller than one half. This condition is usually written as $|\mu_{i, j}| < \frac{1}{2}$.
the swap step: which swaps basis vectors aiming to achieve the Lovász condition, that is $ \delta \Vert \mathbf{b}^*_{i}\Vert^2  \leq \Vert \mathbf{b}^*_{i+1}\Vert^2+ \mu_{i+1,i}^2\Vert
 \mathbf{b}^*_{i}\Vert^2$.

Notice that the swap step just changes the order of the vectors, so, if somehow the reduction step is not executed, the output is just a reordering of the input basis...

Now, what is the Gram-Schmidt orthogonalization of a basis that is already orthogonal? Answering this will give you a trivial relation between $\mathbf{b}_i$ and the corresponding GS vector $\mathbf{b}_i^*$. And what are the values of $\mu_{i, j}$ given that $\mathbf{b}_i$ and $\mathbf{b}_j$ are orthogonal?

With these information, you can see that, for an orthogonal basis, the reduction step is ignored and the LLL algorithm just reorder the basis vectors according to whether $ \delta \Vert \mathbf{b}_{i}\Vert^2  \leq \Vert \mathbf{b}_{i+1}\Vert^2$ or not.

And to answer your second question, you just have to run this "simplified LLL" that you will have found in the first question and get the correct reordering.


AES-- Brute force attack versus Known plain text attack I am taking a codes and cryptography course and the following is a questions on a past exam that I could not and still can't solve:

Suppose that $E_k$ denotes the function that encrypts a message $M$ with AES where $K$ is the 128-bit key. Suppose that a cryptographer discovers a function $F$
so that $E_k(M) = F_{k_1}(F_{k_2}(M))$, where $k_1$ and $k_2$ are each 64-bits, and $K$
is easily computable from $k_1$ and $k_2$.

Explain how one would use this to mount a known
plain text attack on AES that is faster than brute-forcing the 128-bit key.

If someone could provide a step by step explanation of how to do this, it would be greatly appreciate! Thanks in advance!

I believe this question is only answerable if $F_k$ is easily invertible. In other words, if you can compute $M=F^{-1}_k(F_k(M))$. Then a standard meet-in-the-middle attack applies.

Given message $M$, ciphertext $C = E_k(M)$ for unknown $k \in \{0,1\}^{128}$, an efficiently-computable function $X$ such that $k = X(k_1, k_2)$ for some $k_1, k_2 \in \{0,1\}^{64}$, and an invertible function $F$ such that $E_k(m) = F_{k_1}(F_{k_2}(M))$ when $k = X(k_1, k_2)$, do the following:

Let set $K_1 = \{F_{k_1}(M):k_1\in\{0,1\}^{64}\}$. Computing and storing this requires on the order of $2^{64}$ steps and $2^{64}$ memory.
Let set $K_2 = \{F^{-1}_{k_2}(C):k_2\in\{0,1\}^{64}\}$. Computing and storing this requires on the order of $2^{64}$ steps and $2^{64}$ memory.
Find for $k_1\in K_1$, $k_2 \in K_2$ s.t. $k_1 = k_2$. We know that some such pair must exist based on the definitions of the functions $F$ and $X$. A simple way to do this is to simply sort the sets $K_1$ and $K_2$ ($2 \times\left(2^{64} \times \log(2^{64})\right)$ operations) then you can use a linear algorithm to find a matching pair ($2 \times 2^{64}$ steps).
Compute $k = X(k_1, k_2)$.

If you add together the time complexities given, it is easy to see that this algorithm requires on the order of $2^{75}$ operations and on the order of $2^{65}$ memory.


Fast forwarding hash functions We know that a good hash function is a one way/trapdoor function.  Easy to calculate one way, harder to work out a previous state.
I was wondering if anyone knew a good hashing system that allowed you to calculate an arbitrary number of steps into the state future.
E.g. instead of running the hash function 10,000 times to find out the h^10000(X), you could use a function to calculate what that would be , e.g.  H(X,10000).
Thus, having a "fast forwarding" hash function that is fast in one direction, but provably hard in the other.
Anyone have knowledge/experience/ideas here?  Much appreciated.

Follow up to the answer (to some degree).
Using a hash function in this way is somewhat equivalent to fast forwarding a pseudorandom number generator.
A linear congruential generator (LCG) can be skipped ahead [link], in fact many PRNG's can be skipped/jumped ahead [link].
The problem with fast-forwarding any hash/prng, is that if you know the cycle period (which you do with most PRNGs),
by fastforwarding the period-1, you effectively move back 1 state.
Thus if we found a way to say move forward quickly with a SHA256, the first person to correctly estimate its cycle period would also have the ability to move backward as well.
The only fix for this is to have a system with a huge number of varied cycles.  E.g. having 256 bits worth of different cycles lengths, which each cycle being 64-256 bits in cycle length, fitting in 512 bits of state.
No known way of doing this, but should one be found, you've solved multiple comp-sci and cryptology problems, and made efficient signing of messages trivial.
tl;dr - if you can go forward and calculate its cycle length, you can go backward.


What systems of robust steganography are out there? By robust, I mean resistant to common image transforms (reversal, crop a non-multiple of 8 pixels off and recompress, blur, solarize to 64 levels, then interpolate, and sharpen, change compression levels, optimize for download, scale...

Suppose you are trying to embed ownership/copyright info in an image.  How do you do so in a way that survives all of the above singly or in combination? And has sufficient parameters that it is non-obvious that it has been done.

You need to build in a lot of redundancy, and error correction systems.  But that is short of workable system.

Ideally such a system is somewhat holographic in that other systems could also put data into an image, without compromising the original data.

Edit:  While the use mention is one similar to watermarking, I normally consider a watermark to be visible in the image.  Digital rights management has the addition of having various hidden attributes/data.

This came up in a discussion about Facebook putting tracking codes in images. In their case using an uncommonly used metadata field.  So take it a step further:  Can you put data into an image that is not readily recoverable without knowing a bunch of specific additional information, and that is proof against normal image operations.

Keeping the data secret is easy.  Encrypt before encoding the ciphertext into the image.  Keeping the data recoverable is harder.  I'm inquiring about the latter.

The field of research that deals with robustness is watermarking. There are hundreds of techniques to deal with the different existing attacks (resize, crop, recompress, etc).

Currently there is no system that overcomes all possible attacks. But there are some approaches that solve a lot of attacks under certain circumstances.

For example, this is a classic paper for solving RST (Rotation, Scale, Translation) attacks.

But I think the most robust current methods are based on zero-bit schemes. Check, for example, this paper.

I suggest that you define the most important attacks for your application, and try to find papers that deal with these attacks. But it is quite complicated to implement these techniques for non-experts in the field.

The alternative is to try to deal with the different attacks by using simple techniques. For example, use a copy of the original image for mark extraction. This keeps things easy.

Use a DCT transform of the image. Then hide information by modifying the DCT coefficients. You can recover the original DCT coefficients from the original image and the mark from the differences between the original and the marked image.

This resists the resizing process to some degree. If the user makes a crop, use the original image to find the same crop in the original image. Then you can recover the mark as before. The same procedure can be used to deal with rotation.

This approach has many problems, but it provides you with an easy starting point.


Compromise between HMAC and Digital Signature, by encrypting and sending secret key? For achieving stateless authentication tokens (like JWT), is there a compromise between the performance of HMAC, and public key distribution of Digital Signature?

Scenario:

Sender is a centralized authentication server.
Receiver is an
distributed/elastic pool of stateless web services.
The issue I have with HMAC alone is distributing the secret key to the receivers.
Receivers only store Public Key in long-term storage.
The issue I have with Digital Signature alone is the performance for
large messages.

Could the sender somehow generate the HMAC secret key dynamically for each token, and then encrypt it using Private Key?
That way receiver could decrypt HMAC secret key with the Public Key, and then verify the signature.

Something like:

JWT = BASE64(header).BASE64(M).BASE64(HMAC(K,M))
M = Claim || Encrypt(K)

What are the drawbacks?
What are the other approaches to distributing the HMAC secret key with receivers?

No, this will not work, for two fundamental reasons:

You cannot "encrypt with the private key and decrypt with the public key" in any meaningful sense.*  And if you could, it would be totally useless, because the public key is, by definition, public — if you could decrypt with the public key, so could anyone else.

In particular, in your scheme, anybody with access to a "signed" message could decrypt the MAC key (which they need to verify the message, anyway), use that key to forge other messages, and attach the same encrypted MAC key to them.
Even if you scheme worked, it would provide no performance improvement over conventional signature schemes.  Specifically, the standard way to sign messages of arbitrary length is to hash them with a cryptographic hash function, and then sign the hash value.  Thus, for long messages, the performance of conventional signatures is dominated by the time needed to compute the hash value, which is approximately the same as (and, in fact, strictly less than) the time needed to apply HMAC to the same message using the same hash.**

*) Yes, I'm aware that, for the RSA cryptosystem, signature generation and verification are very similar to encryption and decryption, except with the public and private exponents swapped.  This duality is peculiar to RSA, and does not extend to most other public-key cryptosystems.  And even for RSA, the duality breaks once you introduce message padding, which is needed to turn "textbook RSA" into an actual secure cryptosystem.

**) HMAC does place somewhat lower security requirements on the hash function than signatures do (in particular, it does not require the hash to be collision resistant), so you could potentially use a faster and less secure hash for HMAC.  That is, assuming your scheme worked in the first place, which it does not.  And, given that there exist plenty of modern hash functions that are both fast and secure, you'd still be trading a lot of precious security margin for, at best, a very modest gain in speed.


Key renewal when the sequence counter is only 32-bit If we look at the use-case that our sequence counter within our TLS communication is only 32-bit, would an automatic key re-newal be necessary a lot more frequently? We're going to use state-of-the-art algorithms consisting of AES-GCM (at least 128-bit keys) and HMAC-256. I'm referring to the answer posted here - https://security.stackexchange.com/questions/55454/how-long-does-an-https-symmetric-key-last - where it states that key renewal would not be necessary due to the substantial amount of data that can be encrypted with AES without the necessary need for a key renewal.
The sequence counter is not the one used within TLS but a protocol specific one. We're not sure if we continue with the "normal" TLS handling after the handshake has been done. We're going to use EAP-TLS for the handshaking. So we don't know if we make use of the implicit 64-bit sequence counter of TLS - would this make a difference for the question asked above?

The standard rule is simple: Re-key whenever the sequence counter would (likely enough) repeat. For incrementing sequence counters this should be the case when they overflow.
If you're using AES-GCM and you were to pick the (96-bit) nonces randomly, re-keying after $2^{32}$ messages would be recommended. However given that you appear to use an actual counter and feed it into GCM's nonce input re-keying on wrap-around is good enough - which incidentally for 32-bit counters would also happen around $2^{32}$ messages.
If you used a 64-bit counter, the previous thought would extend somewhat and a re-key would be required at last every $2^{64}$ messages. However for reasons of the security proof you should really re-key after hitting $\sigma+q=2^{48}$ with $q$ being the number of nonces encrypted and $\sigma$ being 1/16th of the total number of bytes encrypted while not encrypting more than 64GiB per nonce-key pair.


Two way encryption with random IV I'm attempting to encrypt some information into our database to be later pulled back out and displayed to the user. Searching and reading up on different methods I found a post over at stack exchanged with example code for doing AES Encryption.

https://stackoverflow.com/questions/165808/simple-2-way-encryption-for-c-sharp

Reading through the comments and some different articles I've come to realize that using a static IV for your encryption is generally poor form. That using a random IV is better. This would make sense, but to my understanding I need a way to find that IV again in order to be able to decrypt the information.

I would believe that I can't store the IV in my DB as well, since that would defeat the whole purpose of this. The only thing I can think of is to use something in the row (e.g. a Datetime) as a seed for a random number generator. Which would generate the same IV every time, but that doesn't seem that secure to me either if anyone figured that out.

What are the best practices for situations like this?

Using a static IV isn't simply "poor form" — it introduces crippling weaknesses to the security of your ciphertexts. Likewise, using correctly-generated IVs (the requirements differ from mode-to-mode, but cryptographically random IVs almost always meet those requirements) isn't "better"; it's absolutely necessary.

That said, there is absolutely no requirement of security for IVs. They can be stored safely alongside your ciphertexts.

However, I would strongly caution against using the implementation in the linked post. It uses CBC mode without authenticating the validity of the ciphertext (e.g., with an HMAC), and so will likely (depending on your particular use) make you susceptible to padding oracle attacks.

You should use something like KeyCzar or NaCl if at all possible. As a non-cryptographer, trying to use cryptographic primitives yourself is a bit like trying to build a car engine from parts. You're overwhelmingly likely to miss an important but crucial detail, and have the whole thing blow up in your face.


Calculation of the order of the cosets used in defining the Tate Pairing I'm working through Pairings for Beginners by Craig Costello, and am trying to understand the preamble to the Tate pairing. (See p. 70 ff., section 5.2 of of the PDF.). I'm having trouble following a few arguments and would really like some help please.
The setting is curves of embedding degree $k > 1$, $r∥\#E(F_q)$ (where $∥$ means divides, but just once).

Since there are $r^2$ points in the the $r$-torsion subgroup $E(F_{q^k})[r]$ we usually have $r^2∥\#E(F_{q^k})$.

Ok so far.

Thus, let $h = \frac{\#E(F_{q^k})}{r^2}$ be the cofactor that sends points in $E(F_{q^k})$ to points in $E(F_{q^k})[r]$.

I don't follow this part. Presumably he's asserting that with this $h$, we can take any point $P ∈ E(F_{q^k})$, and we will get $hP ∈ E(F_{q^k})[r]$? I don't see how $hP$ would necessarily be a point of order $r$?

Let $rE(F_{q^k})$ be the coset of points in $E(F_{q^k})$ defined by $rE(F_{q^k}) = \{[r]P : P ∈ E(F_{q^k})\}$.
The number of elements in $rE(F_{q^k})$ is $h$

I don't see why the order of this 'coset' is $h$?

and it contains the point at infinity; from here we will simply denote this coset as $rE$. Following [Sco04], we can obtain another distinct coset of $E(F_{q^k})$ by adding a random element $R$ (not in $E[r]$) to each element of $rE$. In this way we can obtain precisely $r^2$ distinct, order $h$ cosets.

Without knowing the answer to my previous question ("why does $rE$ have order $h$") I can't yet accept this step. I believe it will follow from Lagrange's Theorem directly, if I can be convinced that the order of $rE$ is $h$.

Try doing some examples. Sage (free and open source software) is very helpful here.

I think the simplest example is $E : y^2 = x^3 + 1$ over $\mathbf{F}_5$. This curve has embedding degree $k=2$.

sage: q = 5
sage: k = 2
sage: F.<z> = GF(5^2, modulus = x^2 + 2)
sage: E0 = EllipticCurve(GF(5), [0,1])
sage: E = EllipticCurve(F, [0,1])
sage: E0
Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 5
sage: E
Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in x of size 5^2
sage: E0.order()
6
sage: E.order()
36

Here $E_0$ denotes the curve over $\mathbf{F}_5$, and $E$ denotes the curve over $\mathbf{F}_{25}$. (Sage distinguishes between these two objects, so you need different symbols for them.) We can take $r=3$; note that $r$ divides the order of $E_0(\mathbf{F}_5)$ exactly once, so the requirements are satisfied.

Let's list the points in $E(\mathbf{F}_{25})$:

sage: E.points()
[(0 : 1 : 0), (0 : 1 : 1), (0 : 4 : 1), (1 : 2*z : 1), (1 : 3*z : 1), (2 : 2 : 1), (2 : 3 : 1), (3 : z : 1), (3 : 4*z : 1), (4 : 0 : 1), (z : 2*z + 2 : 1), (z : 3*z + 3 : 1), (z + 2 : 2*z : 1), (z + 2 : 3*z : 1), (z + 3 : 0 : 1), (2*z + 1 : z : 1), (2*z + 1 : 4*z : 1), (2*z + 2 : 2*z + 2 : 1), (2*z + 2 : 3*z + 3 : 1), (2*z + 3 : 2*z + 2 : 1), (2*z + 3 : 3*z + 3 : 1), (2*z + 4 : 2 : 1), (2*z + 4 : 3 : 1), (3*z + 1 : z : 1), (3*z + 1 : 4*z : 1), (3*z + 2 : 2*z + 3 : 1), (3*z + 2 : 3*z + 2 : 1), (3*z + 3 : 2*z + 3 : 1), (3*z + 3 : 3*z + 2 : 1), (3*z + 4 : 2 : 1), (3*z + 4 : 3 : 1), (4*z : 2*z + 3 : 1), (4*z : 3*z + 2 : 1), (4*z + 2 : 2*z : 1), (4*z + 2 : 3*z : 1), (4*z + 3 : 0 : 1)]

Let's find their orders:

sage: max([P.order() for P in E.points()])
6

This last computation indicates that the maximum order of any single point in $E(\mathbf{F}_{25})$ is 6, even though the order of $E(\mathbf{F}_{25})$ itself is 36. Hopefully you know enough group theory to understand how this is possible; if not, you should review your group theory.

Let's pick a point in $E(\mathbf{F}_{25})$ of order 6. By trial and error, I find:

sage: P = E(3,z)
sage: P
(3 : z : 1)
sage: P.order()
6

Let's multiply $P$ by $h$ and see what happens (note that I have to convert $h$ from a rational number to an integer in order to do the multiplication):

sage: r = 3
sage: h = Integer(E.order()/r^2)
sage: h
4
sage: h*P
(1 : 2*z : 1)
sage: (h*P).order()
3
sage: (h*P).order() == r
True

We see that the order of $hP$ equals $r$, as expected.

Let's compute the "coset" $rE(\mathbf{F}_{25})$. Note that we convert the list of points to a dictionary and back to a list to remove duplicates:

sage: list(dict.fromkeys([r*P for P in E.points()]))
[(4 : 0 : 1), (0 : 1 : 0), (z + 3 : 0 : 1), (4*z + 3 : 0 : 1)]

Note this coset contains the point at infinity $(0:1:0)$, as claimed. Of course, this coset has $h=4$ elements, as expected:

sage: len(list(dict.fromkeys([r*P for P in E.points()]))) == h
True

I haven't answered any of your theoretical questions in your post. This is very much intentional. If you understand enough examples, the theory is obvious. If you don't understand examples, then no amount of theory knowledge will help you. Do not focus overly on the theory. Please, work with lots and lots of examples. Understand those examples and understand them well. Then, if you still have questions, ask your questions using examples to illustrate your questions. There is no shortcut to enlightenment. You MUST work with examples.


What does encryption with RSA public key provide? I want to know if encryption with RSA public key provides confidentiality and integrity. I'm quite sure that it provides confidentiality but I have concerns about integrity.
If an attacker would scramble ciphertext what would be the result I get?
Do I need to put some kind of MAC at the end of messages before encryption?

If I have to be more specific about my problem, I want to use RSA for sending tiny requests to a server. I am thinking of encrypting requests with server's public key. Server will also know my public key and send back responses encrypted with my public key. I'm not sure if I'm using these correctly since I'm a beginner in these topics.

Any help would be appreciated.

Properly done encryption with the RSA public key of the server provides confidentiality of the request, but not integrity or proof of origin (anyone can forge a request with any desired content).

There must be some secret on the sender's side to prove integrity. That can be an RSA private key used for RSA signature (with sender public keys known to the server either by transmission over a channel with integrity, or by way of a digital certificate). Other signature schemes also work (DSA, ECDSA..).

Symmetric crypto also works for integrity, if it is acceptable that the server holds the client's secrets (or a master key allowing the server to re-compute the  secrets of all clients).

Symmetric crypto can provide both integrity and confidentiality (e.g. Salsa20-Poly1305 per RFC 7539), but asymmetric encryption has a superiority: the confidentiality that it offers does not depend on the client's ability to keep a key secret on the long run; only integrity does.


TLS handshake proof of private key posession At what stage in below TLS connection setup did the server prove to client that it possesses the private key corresponding to its public RSA key.

I have used TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384
Cipher suite to successfully setup a server client mutually authenticated connection. I am just curious how it works. I have a rough idea about Diffie Hellman key generation(I believe it is independent of authentication, and just for generation of secret to create symmetric key) but I could not understand in below sequence diagram, where did the server prove its possession of private key(I know that only private key decrypts what public key encrypts, but any hacker could send a copy of public certificate of any server)

I have used TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384

That means that client and server are using ECDHE for the key exchange and RSA for verification of the server sent parameters. This is what perfect secrecy does, every time that a TLS handshake occurs, the servers sends with the certificate a list of parameters used for the key exchange along with a digital signature over these, in this case RSA signature. These parameters + signature are contained in the ServerKeyExchange field.

  but any hacker could send a copy of public certificate of any server)

You as a client can validate if the presented certificate matches the entity that you want to connect to. This is done by validating that the received certificate on ServerCertificate field belongs to the entity that you are connecting to (CN & SubjectAltName fields) and that the certificate chain is valid (the Root CA has sign the intermediate CA that has sign the leaf certificate AKA the entity's certificate).

So if the validation is successful you proceed to validate the ECDHE parameters sent by the server in ServerKeyExchange field to prove that the server posses (as you ask) the private key associated to the RSA public key. Just take the RSA public key of the leaf certificate and verificate the digital signature of those parameters. If the digital signature matches the digest (hash) of the parameters + ClientHello.random + ServerHello.random, then you know that those ECDHE parameters have been sent by the server and not by an eavesdropper that tries to establish a symmetric key to impersonate the server.