What problems might you encounter if you use a block size much greater than AES? What problems might you encounter if you use a block size much greater than AES (1000 bits, say)?

It may be very tricky to have a good distribution / diffusion of the input bits for each round. That would mean that you would either require a very intricate design for each round, or a lot of rounds to make up for it.

Furthermore it will also mean that you need to perform an operation of at least 1000 bits to perform any kind of calculation. This is not a desirable property in most circumstances. For some modes of operation such as CBC, it will mean that the minimum message size would be 1000 bits - and the IV would take up another 1000 bits. For counter (CTR) mode your message will not grow as only part of the output can be used. However, that still means doing 1000 bit calculations for possibly much smaller messages.

Most modes of operation function quite well for block sizes of 128 bits, although 256 bits would be beneficial for modes such as CTR (because the IV is split between a nonce and the counter).

Although a large block size is desirable for use in the design of hash functions, the avalanche effect does require a good diffusion of bits. Threefish - the block cipher used for Skein, one of the SHA-3 finalists - however does support a block size of 1024 bits, so ~1000 bits is certainly not unheard of (quite often the internal hash state is at least double the intermediate / output size). Skein 512 however requires 80 (!) rounds of Threefish1024 so it certainly wasn't the fastest algorithm out there.

A relatively fast large block cipher may also be beneficial for some format preserving encryption, by the way. In principle a single block encrypt of a unique value is secure, so having a large block size may be helpful avoid repetition of blocks. You could build a cipher with a larger block size from a block cipher with a small block size, but those kind of constructs are generally not all that efficient.


Chosen-Ciphertext Attack on Rabin: Factorize n At the end of this Wikipedia section, you can see that $$\gcd(|r-s|,n)=q$$ or $$\gcd(|r-s|,n)=p$$ holds. I don't understand why.

By following the above advice (taking the equations for r and s given in the article and writing r-s) you will notice that q is  a divisor, therefore GCD(|r-s|,n) cannot be 1. There are only two options left since n is only divisible by q and p.


Is MAC algorithm same at both sender and receiver end The MAC algortihm which is used along with a secret key to generate a MAC tag on the sender end ,is it same at the receiver end also who again uses a MAC algorithm to generate a tag?

If yes, then how is the MAC algorithm generated. Is it just a function(a mathematical function to compute)??

If no, then how does the tag get matched to preserve the data integrity??

Is the MAC algorithm, is present as a layer inside of SSL????

Yes, the MAC algorithm works the same way on both sides. It is a mathematical function that computes the tag from the key and the message. On the sender side, the message is processed as follows:

Calculate T = MAC(key, raw_message).
Send the raw_message and the tag value T. Many communication protocols append them in this order but anything will do as long as the receiver agrees on the format.

On the receiver side, the processing goes as follows:

Parse the received data is parsed as a raw message and a tag value.
Calculate T' = MAC(key, received_raw_message).
Compare T' with received_T. If the values are equal then the message is authentic, otherwise it is not.

SSL does use a MAC to verify data integrity. Strictly speaking, the MAC itself only ensures authenticity, not integrity: a MAC alone does not protect against replay attacks, whereby an adversary repeats a legitimate message. To protect against replay attacks, protocols such as SSL include a nonce in the authenticated message: if the message is genuine and contains the expected nonce, then it hasn't been modified or switched in transit.


PQ Key Exchange based on Elliptic Curve Isogenies I was reading the Wikipedia article on Post Quantum Cryptography and was interested in opinions as to whether the Supersingular Elliptic Curve Isogeny Diffie-Hellman listed there would be a good Post Quantum replacement for Elliptic Curve Diffie-Hellman that is being implemented today?

The Supersingular Elliptic Curve Isogeny Key Exchange that you refer to was first published in 2011 by DeFeo, Jao, and Plut.  It builds on but is quite distinct from earlier work by Rostovetsev and Stolbunov in 2006.  As a Post Quantum/Quantum Safe replacement for Elliptic Curve Diffie-Hellman (ECDH) it has several good properties:

The number of bits that need to be exchanged over the communications channel is roughly the same as a normal Diffie-Hellman key exchange.  Not as small as an ECDH but not nearly as large as in other Post Quantum schemes like McEliece or NTRU.
It uses the very well studied mathematics of elliptic curves rather than the more recently accepted lattice approaches to secure cryptography.  If you look in the literature you will see that lattice cryptography has been prone to insecurity in the past.
It offers forward secrecy, just like Diffie-Hellman and ECDH.  McEliece and NTRU need to add an additional exchange to provide forward secrecy.
It uses elliptic curve arithmetic in a finite field which has been widely implementd.
Most importantly, it has withstood 4 years of academic analysis.  Two notable papers which are relevant to the security of this key exchange are:

Computing Isogenies between Supersingular Elliptic Curves over Fp by Delfs and Galbraith
    http://arxiv.org/pdf/1310.7789v1.pdf

A Quantum Algorithm for Computing Isogenies between Supersingular Elliptic Curves by Biasse, Jao and Sankar
    http://cacr.uwaterloo.ca/techreports/2014/cacr2014-24.pdf

Both papers support the basic security of the Supersingular Isogeny Key exchange though it should be noted that one of the authors (Jao) is also one of the inventors of the key exchange.

There seem to be no patents on the key exchange.

However there is a shortcoming:

Computing Isogenies of Supersingular Elliptic curves and composing these isogenies is computationally harder than other post quantum schemes being considered like McEliece, NTRU, or the Ring-LWE schemes.

In the paper which presented the key exchange, the authors present algorithms which require over 100ms of computation on a 2.5GHz computer for each side of the exchange. Half of that can be done offline but it is worth noting.  There has been further work by Shumow and Shumow and Moody on creating more efficient computational models.  Both the original inventors of the key exchange and Shumow have posted their code online.  It is a good bet that if people became more interested in actually using this key exchange, there could be some significant improvements in computation like Dan Bernstein and Tanja Lange have done for standard Elliptic curve cryptography.  A coding contest for the fastest Elliptic Curve Isogeny computations for 768-bit supersingular curves would be an good way to test the performance limits.

Does that answer your question?


How to compute a discrete logarithm modulo a power of 2? This question is related to this one. Specifically, assume that we have $p$ = 2048, $m$ = 13 and $c$ = 357.

In this case, $c\ =m^e\ \bmod \ p$.

I know that many algorithms rely on the difficulty of computing the discrete logarithm. I have read however that discrete log across powers of 2 is weak. Could someone explain to me why and how you would compute it in my example?

There are a couple reasons that the discrete log is weak across powers of two, the most basic reason is because it is only considered strong when the modulus is some large prime, p.

This is a good link about how to find the mod inverse, and in it you will find their function for computing it.
https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/

Basically, for your example, the program would solve the mod inverse problem in a very short amount of time (which is bad!). That is why if you use larger values of m and p, the calculations done in the pow function will take much longer than it did with the previous numbers.

As for why powers of 2 specifically are weak, I would recommend looking at the Chinese Remainder Theorem, just know that this requires a lot of math and is just based on the fact that any power of two is comprised solely of factors of 2. https://en.wikipedia.org/wiki/Chinese_remainder_theorem.


Forward Secrecy when using non-ephemeral DH In context SSL/TLS, reading up on various sites, I find forward secrecy in DH key exchange being linked to its ephemeral use i.e. DHE. I don't fully understand this link, where does following reasoning break?

If non-ephemeral use (plain DH) would not provide forward secrecy, and ephemerality refers to a new session key being made each time a new session is set up. Then the use of SSL/TLS Session IDs/Session Tickets would make DH-use non-ephemeral.

But how can the compromise of server public/private keys result in the compromise of an earlier established DH session key? I should presume that the nonces which were used are already discarded; and the storage associated to Session IDs/Session Tickets is not necessarily compromised if the server public/private keys are compromised?

Ephemerality does not refer to "a new session key being made each time a new session is set up", it refers to both parties' key pairs (and group elements) being freshly chosen. These Diffie-Hellman key pairs are should be ephemeral for forward secrecy; the session key is always ephemeral, even if static-static Diffie-Hellman is applied.

Any nonces are used as part of the session key calculation should be known at both sides. This means they have to be communicated in plain or they should be part of the key agreement algorithm. That means that the nonces are either known to the attacker or that they can be retrieved by reapplying the DH calculations (in the future, when the static DH private key is leaked). If ephemeral key pairs are used then DH cannot be reapplied because the private exponents are lost.

So the nonces may become available to an attacker for static-static and ephemeral-static Diffie-Hellman even when the sender and receiver have discarded the values long ago.

Note that there is a difference between the raw/textbook DH calculation and the DH scheme specified in e.g. NIST 800-56A: "Scheme Using No Ephemeral Key Pairs".

If you just apply the calculation then two static keys would result in a static key seed. The NIST scheme on the other hand includes a nonce send in plain so the resulting key seed will be ephemeral.

The answer assumes that the key seed is ephemeral.


Rainbow Table - Number of Chains and Chain Length Is there a difference between having 10,000 of chains (with 1,000 chain length) and 10,000 chain length (with 1,000 of chains)? How does it affect the success rate of the rainbow table?

I understand that only start point and end point are kept in the table. The more chains you have, the disk space increases. Whereas the higher number of chain length would mean longer computing time is required to run through them.

You can't compute these without a lot of other parameters, the most basic being the size of the keyspace you are searching, are you using perfect vs non-perfect rainbow tables, etc. See, e.g., this paper on eprint for the gory details.


Secret Sharing: Is this simplification secure? I am a mathematician with no background in crypto or security. For work, I had to read up Chap.13 "Secret Sharing Schemes" in Stinson's Cryptography (3rd ed). My question is about a simplification of the so-called Monotone Circuit Construction.

In Sect. 13.2 Stinson discusses the case that you have $w$ participants $\mathcal{P} = \{ P_1, \ldots, P_w \}$ and you want to realize the access structure $\Gamma \subseteq 2^{\mathcal{P}}$, which is just an arbitrary set of subsets of $\mathcal{P}$. This means, exactly the subsets in $\Gamma$ should get access to the secret and no other group.

The method he presents was invented by Benaloh & Leichter (CRYPTO '88) and is called (by Stinson) the Monotone Circuit Construction. The idea is simple: You build a monotone Boolean circuit that "recognizes" $\Gamma$ and then compute the shares based on the wiring of the circuit (see Algorithm 13.1).

All this is fine, but it seems a bit overblown. Why not do the following? For each group of $\Gamma$ with $t$ participants you just "split" the secret number randomly among them (meaning, you use a $(t,t)$-Threshold Scheme) -- and you're done. This even should be a special case of the Monotone Circuit Construction.

I have two questions about this:

Is the above suggestion secure?
What's the advantage of the more general approach as presented by Stinson?

Is the above suggestion secure?

Sure; for any group that doesn't have a subset that's a group in $\Gamma$, they don't have enough information to reconstruct the shared secret.

Your approach is indeed a subset of Benaloh's, where you constrain the circuit to be a layer of AND gates, followed by a single OR gate.

  2.What's the advantage of the more general approach as presented by Stinson?

The size of the shares; your scheme requires a share size for an individual that is proportional to the number of groups it's a member of.  For example, if the access structure is "any of 1000 members of group A, plus any of 1000 members of group B, plus any of 1000 members of group C", then everyone's shares will be 1,000,000 times the size of the shared secret; with Benaloh's method, each share need not be any larger than the shared secret.

Of course, if the access structure is "any 500 of the 1000 member groups", you're far better off with Shamir's method, rather than either of these two...


Why is not there any ideal S-Box? i read about linear cryptanalysis and about S-Box that there is not any ideal S-Box (ideal S-Box is a random S-Box in another words S-Box that bias of input and output bits is zero) then i read about implementation of S-Box in this post and understand that S-Box is implementing with Lookup tables,then read this post (e-sushi's answer) about non-linearity and randomness aspects of S-Box:

  And you can trust in the fact that the chances that you’ll manage to create a good s-box randomly by using your current criteria are very minimal… very, very minimal!

but i don't understand that why is not there any random(ideal) S-Box? why can't lookup tables implement a random S-box? what is restriction(limitation) for it?

It is important to understand that although a very large random function will only have linear biases with very low probability, this is simply not true of small random functions. If you choose a small random function, then it is unlikely that you will get one that is suitable for block cipher constructions. In addition, it is not enough to construct an S-box with low linear biases; one must also take into account differential cryptanalysis, and more.

Having said all of the above, this does raise an interesting question. Can we even define an ideal S-box? This doesn't necessarily mean we could find one; for example, the AES S-box has an 8-bit input and 8-bit output. This means that there are $2^{128}$ possible functions of this type, and this cannot be enumerated. Nevertheless, I would be interested to know if an "ideal" construction even exists, in terms of our best cryptanalysis knowledge.


What is the meaning of the notation $\langle a, b\rangle$ in certain cryptography papers? I'm trying to understand a paper from Brakerski and Vaikuntanathan. In it, they use the notation $\langle a,b \rangle$ but they don't explain what that means.

The answers on this question say that it's just another way to write a tuple, but I don't think that's right in this case since the authors use the regular $(a,b)$ notation in the rest of the paper to denote a tuple.

Does anyone know what else $\langle a,b \rangle$ could mean?

In mathematics, $\langle a,b \rangle$ represents the inner product of two vectors and this is a generalization of the dot product. It is one of the multiplications of the vectors in a Vector space and the result is a scalar.

An inner product satisfies these properties

$\langle c+a,b\rangle =\langle c,a\rangle +\langle a,b\rangle $.
$\langle \alpha a,b\rangle = \alpha\langle a,b\rangle$ where $\alpha$ is a scalar.
$\langle a,b\rangle =\langle b,a\rangle$.
$\langle a,a\rangle = 0 $ and equal if and only if $v=0$.

The fourth condition is the positive definite condition. Some authors define the inner product with only the first 3 conditions with a weaker 4th condition $\langle a, b \rangle =0$ for all $b$ then $a=0$.

As noted in the comments by @levgeni, if the field is $\mathbb{F}_2$ then

$$\langle (1,1),(1,1) \rangle = 1 \cdot 1 + 1 \cdot 1 = 2 = 0$$ and
$$\langle (1,1),(1,0) \rangle = 1 \cdot 1 + 1 \cdot 0 = 1 = 1$$ therefore, the weaker condition is required.

The inner product definition changes according to the vector space. In the context of the paper, let

$$a =(a_1,\ldots,a_n)$$
$$b =(b_1,\ldots,b_n)$$

be two n-dimensional vectors then;

$$\langle a, b \rangle = a_1 \cdot b_1 + \cdots + a_n \cdot b_n $$


What happens if an RSA key pair has identical public and private exponents? Rather, is it possible for big prime numbers?

Classroom examples usually involve smaller primes, so for example if you are given a prime number pair $p = 3$, $q = 13$ you would get $n = 39$ and $e = d = 5$, making encryption and decryption the same for a message $x$ or ciphertext $x$.

This can be a big problem, e.g. if a server sends you cipher $x$, you can decrypt it and get the message, then you encrypt the cipher $x$ itself and if you get the message again then you know the public key is the same as the private key.

Is this possible in industry?

No, the public and private exponents will never be the same for real (that is, not toy) RSA keys.

The public exponent is almost always be deliberately chosen as a small value (with 65537, 3 and 17 being the most popular choices).  In contrast, the private exponent will always be a huge value; always at least $(p-1)/e$ (where $p$ is the larger prime factor of the modulus, and $e$ is the public exponent), and will generally (almost always) be much larger than that.  This implies that if you have a 1024-bit RSA key, and a public exponent of 65537, then the private exponent will be at least 495 bits long.

Even if you (for some unknown reason) select a random large public exponent, then it is still extremely unlikely.  If we look into the conditions that allow $d = e$, we see that both of the following must hold:

$e^2 \bmod (p-1) = 1$

$e^2 \bmod (q-1) = 1$

Having even one of $e^2 \bmod (p-1)$ and $e^2 \bmod (q-1)$ to be 1 is extremely unlikely; having both conditions happen is not something to worry about.


How exactly to concatenate two differential trails to form a boomerang disguisher in practice? I've been reading many papers on boomerang/rectangle attacks. The general strategy is to find two trails for a small number of rounds and then concatenate them to form a longer distinguisher. Specifically, they decompose the cipher $E$ to $E = E_1 \circ E_m \circ E_0$, and employ some ladder/sbox switch at the connecting point $E_m$ and/or use the BCT to determine the probability of $E_m$.
I am having trouble understanding how exactly one defines $E_m $ given two short trails $E_0$ and $E_1$. For example, let $S$ denote the S-box layer, $L$ denote the linear layer and $X$ denote the key addition of some toy cipher:
$E_0$ 2 round trail trail:
0 0 0 1 --S--> 0 0 0 6 --L--> 0 0 6 0 --X--> 0 0 6 1 --S--> 0 0 d 6 --L--> 0 6 1 0 --X--> 0 6 1 1

$E_1$ 2 round trail trail:
3 1 1 1 --S--> 1 0 0 0 --L--> 0 0 0 1 --X--> 0 0 0 0 --S--> 0 0 0 0 --L--> 0 0 0 0 --X--> 0 0 0 1

Where/how would one define $E_m$ between these two trails? Assuming the transitions $(0 \rightarrow 3), (1 \rightarrow 1)$ have $pr = 1$ and $(6 \rightarrow 1)$ has $pr = 0.5$ from the BCT

In this case because the trail $E_1$ begins at the stage in the cipher directly after the trail $E_0$ ends you can use $E_m$ as the identity map which preserves all differences with probability one.
Thus to generate data to exploit the distinguisher, start with an arbitrary plaintext, say 0x0123 and call the chosen plaintext resource for both this and its paired $E_0$ input (in our example 0x0122). Both of these will lead to outputs after four rounds, say 0xdead and 0xbeef. Now call the chosen ciphertext resource the paired $E_2$ outputs of these ciphertexts (in our example 0xdeac and 0xbeee). If any we fall off either difference trail these won't produce anything useful, but a positive proportion of the time they should decrypt to a pair with the input difference of $E_0$, say 0xf00d and 0xfooc.
To understand the interaction in the middle, suppose that all difference trails are followed precisely. Suppose also that our initial input 0x0123 reached the state, say 0x3141 after two rounds; by the $E_1$ path our input 0x0122 would have moved to state 0x3750. Now consider the states 0x0050 and 0x0641 after two rounds. The (0x3141, 0x0050) states are a $E_1$ input pair and the (0x3750,0x0641) are another $E_1$ input pair, which would both indeed lead us to an $E_1$ output pair (0xdead,0xdeac) and (0xbeef,0xbeee) respectively. Likewise (0x0050,0x0641) represents an $E_0$ output pair which should back up to a $E_0$ input pair (0xf00d,0xf00c) in our example.
Four difference trails have to be respected for this observation to be causal: 2 copies of $E_0$ and two copies of $E_1$. Thus if the probability that $E_0$ is followed is $p_0$ and the probability that $E_1$ is followed is $p_1$, the probability of the boomerang observation is $p_0^2p_1^2$.
The above contains a subtle assumption of independence. In differential trails we can usually assume independence of the individual steps by assuming that round key has a randomising effect. In boomerangs attacks we are tracking four trails and assuming that they behave more or less independently. The assumption of independence is strongest where the upper and lower trail meet and, say, in our example we assume that the probability that $F(x\oplus\Delta_{0,i})$ equals $F(x)\oplus\Delta_{0,o}$ is independent of the probability that $F(x\oplus\Delta_{1,i}$ equals $F(x)\oplus\Delta_{1,o}$ and also the probability that $F(x\oplus\Delta_{0,i}\oplus\Delta_{1,i})$ equals $F(x)\oplus\Delta_{0,o}\oplus\Delta_{1,o}$ when we're talking about the same input value $x$ for all three probabilities instead of randomising each $x$ with round key. This interdependence can greatly inflate or reduce the probability of observing the boomerang statistic and modern developments such as the Boomerang Connectivity Table try to account for this dependence by generating a single probability to account for all three events. To separate out this interdependent step, we can make it a separate stage of our encryption $E_m$. In our case, linear steps can be passed through with probability 1 and independence and we'll extend to that $E_0$ ends immediately before an $S$-box (as it already does) and $E_1$ starts immediately after an $S$-box (for this we pass back through $X^{-1}$ and $L^{-1}$ and append these to the start of our $E_1$ trail). We can now call $E_m$ the transition through our $S$-box and use the BCT to estimate the interdependent probability of transitioning between $E_0$ and $E_1$.


Output a pad (un-keyed, variable length) from an input seed (fixed value for same seed) I want a function $y = f(x, len)$:

$x$ is the seed. $y$ is the output. $len \in \mathbb{Z^+}$ is the length (bytes) of $y$
Select a seed string $x$ to generate a string $y$.
For each same pair of $x$ and $len$, the value of $y$ is same.
seed should have a reasonable short length. $y$'s length may support a certain range (*remark)
Every byte value of $y$ should be uniformly (or close to uniformly) distributed

Remark of 4 - please consider two possible functions:

$y$ length is a multiple of $16$ (block length $16$). If I use hash function, the problem is that the length options are limited and not consecutive (e.g., $16 \cdot n$, $n=1, 2, 3,\ldots$).
$y$ can be any length within a range

(No need to protect $f(x)$ as a secret)

It sounds like the SHAKE functions (there are two flavors, SHAKE-128 and SHAKE-256) are designed to do exactly what you're asking for.

SHAKE takes a value ($x$ in your case), and generates an arbitrarily long output from it.  You can take the first $len$ bytes from it, and that's your $y$

As for your requirements:

  For each same pair of $x$ and $len$, the value of $y$ is same.

For any input seed $x$, SHAKE always generates the same key stream.  This does mean that (for example) $\text{SHAKE}( \text{"abc"}, 128 )$ is a prefix of $\text{SHAKE}( \text{"abc"}, 256 )$.  Your requirements didn't mention that as a concern, but if it is, you can always use $x || len$ as the input to SHAKE

  seed should have a reasonable short length.

SHAKE can handle any seed length you want.

  4a. $y$'s length may support a certain range (*remark)

SHAKE can generate any length of output

  Every byte value of $y$ should be uniformly (or close to uniformly) distributed

As far as we know, the output of SHAKE is uniformly distributed.

And while it's not difficult at all to generate the same functionality from a fixed length hash function, the nice thing about SHAKE is that all the logic about generating multiple hashes and truncating the last one is already done for you.

Here is the standard implementation of SHAKE (as well as a number of related functions)


Is this a secure implementation of password reset email? I am redesigning a password reset email mechanism because the existing implementation scares the hell out of me. My goal is to generate reset codes that are:

Expired
Tamper Resistant
Single Use
Resistant to replay attacks

The format of the reset code I have come up with is:

B64( B64( iv ) || B64( E( uid || timestamp ) ) )

Where B64 is base64 encoding and E is for symmetric encryption. The iv is the initialization vector used for encryption (randomly generated), and is in the clear. The || indicates concatenation and I actually use the string "||" as the separator. The uid is an opaque identifier of the user so I can look them up in the database.

The timestamp allows for a code to be expired.

I am using AES 256 in Galois Counter Mode which should provide protection from modified ciphertext attacks.

The encryption key is stored on the server, and used to perform the encryption.

The iv has a dual use. When the reset code is generated the iv is stored with the user in the database. This is used to enforce single-use of a reset code (it gets cleared when a reset code is processed) as well as prevent use of reset codes generated previously. If the iv in the database does not match the iv used to decrypt the reset code, the request is refused. This may also help with security in the event that the encryption key on the server is somehow compromised, as the attacker has to inject the iv into the database as well to make it work. Of course if the attacker is on the host we are pretty much toast...

Are there any weaknesses in this design I am not seeing, or does it needs additional improvement?

What you describe looks secure to me, but excessively complicated.  The following simpler procedure should suffice:

When a password reset token is requested:

Generate a secure random token and save it (or a cryptographic hash of it) in the database, along with a timestamp.  Overwrite the previous token, if any.
Send the token to the user by e-mail (suitably encoded).

When the user submits a token:

Check that it matches the token in the database, and that the corresponding timestamp is not too old.

The only part of the process which needs to involve any cryptography at all is generating the random token, and optionally hashing it.  You can usually offload the former task to the OS; on Unixish systems, for example, you can read the token from /dev/urandom.  Alternatively, if you're using a decent crypto library, it should provide a routine for generating secure random numbers (which may call the OS random number generator internally).

Ps. The one situation where you might want to go with a more crypto-heavy solution would be if you didn't have access to a convenient database for storing the tokens.  In that case, you could, for example, compute the token as MACK(userid || timestamp), where MACK is a message authentication code keyed by the secret key K, and have the user submit the timestamp along with the token.  (You could also include a random number in the MAC input, but that's not really necessary — without the key K, an attacker won't be able to forge the MAC.)  However, since you do have a database available, this doesn't really apply.


Creating a small number from a random octet string I'm trying to figure out the best way to generate a cryptographically secure random number between 0 and 200 (inclusive) from a cryptographically secure random string of bytes (ie. read from /dev/urandom or some such).

I could do random[0] % 201 but then numbers 0-54 would be more likely than 55-200 which would make the resulting number more predictable than it should be.

How can I use the random octet string to create a number in a range 0...k-1 (where k is 201)?

The method given in this other answer is correct: to choose a uniformly random integer in range $[0,k-1]$ given a string of uniformly random integers in range $[0,n-1]$ with $1<k≤n$, get one integer $x$ from the string until $x<⌊n/k⌋⋅k$, then output $y=x\bmod k$. If we have $k≤n<2k$ (as in the question where $k=201$, $n=256$), that simplifies to: get one integer $x$ from the string until $x<k$, then output $x$.

However, that's not the best method, as asked: it consumes more from the input string than strictly needed. Otherwise said, when the input string is of limited length, odds that the algorithm fails are higher than needed. If there are $m$ values in the input string, odds of failure are $(1-⌊n/k⌋⋅k/n)^m$. For $k=201$, $n=256$, $m=3$, that's nearly $1\%$. It can get much worse: for $k=129$, $n=256$, $m=3$, odds of failure are over $12\%$.

We can modify the algorithm to improve on that; and also remove the $k≤n$ requirement.

Set $r←0$, $s←1$.
Get one new $x$ from the random string, set $r←r⋅n+x$ and $s←s⋅n$.
If $r≥⌊s/k⌋⋅k$, set $r←r-⌊s/k⌋\cdot k$ and $s←s-⌊s/k⌋⋅k$, and proceed to step 2.
Output $y=r\bmod k$, and stop.

Sketch of proof of correctness: by induction, before step 2 and before step 3, $r$ is a uniformly random integer with $0≤r<s$.

The integers $r$ and $s$ never exceed $(k-1)⋅n$, and thus the algorithm does not require arbitrary-precision arithmetic. It minimize odds of failure for a given input string of length $m$, to the bare minimum possible for exactly uniform output: $(n^m\bmod k)/n^m$; that is $≈0.0009\%$ (rather than $≈1\%$) for $k=201$, $n=256$, $m=3$; or $≈0.0007\%$ (rather than $≈12\%$) for $k=129$, $n=256$, $m=3$.

The algorithm works if the input string contains bits, or dice rolls with any number of faces, including variable (just change $n$ at step 2 according to the $x$ extracted from the input string).

If we need to generate more than one output $y$, there are several options:

The easiest is to start over; but that's clearly sub-optimal, especially when $n≫k$.
We can change "stop" at step 4 to: "set $r←⌊r/k⌋$, set $s←⌊s/k⌋$ (then, if desired, change $k$ for the next output); and proceed to step 3". The resulting algorithm still produce uniformly distributed output (the recurrence in the proof sketch holds), drastically reduce the consumption from the input string when $n≫k$, but I'm uncertain about optimality is not optimal (that's blatant for $k=2$, $n=3$).
If we know the number $j$ of desired outputs $y$ in advance, we can set $\hat k=k^j$, generate one $\hat y$ uniform in $[0,\hat k-1]$ using the optimal algorithm, then split $\hat y$ into $j$ outputs by expressing $\hat y$ as a $j$-digit number in base $k$. That's back to optimal, but is not a sequential algorithm, and requires arbitrary precision arithmetic when $j$ grows, with $O(j)$ extra memory.
We can generate any number of outputs using several batches of $j$ as in the previous tweak, but using the suboptimal sequential algorithm described above. That allows using bounded extra memory, and becomes close to optimality as $\hat k=k^j$ grows. However this is not a sequential algorithm.

I now lean towards belief that any optimum algorithm is bound to require $O(\log m)$ extra memory in some worst case. However it is possible to make a sequential algorithm using bounded extra memory, much less than above, and closer to optimality. I plan to detail such an algorithm (if someone else finds a reference, or otherwise has a suitable algorithm, please tell us!).


SHA256 message schedule examples I need some example values for the message schedule stage of SHA256 to test this part of my implementation.

If possible in binary, for the string 'abc'.


Using a single Ed25519 key for encryption and signature The libsodium documentation contains a function crypto_sign_ed25519_pk_to_curve25519 that converts an Ed25519 key into a Curve25519 one, so it can be used for both key exchange/encryption and signing:

"Ed25519 keys can be converted to Curve25519 keys, so that the same key pair can be used both for authenticated encryption (crypto_box) and for signatures (crypto_sign)."

The same page ends "Notes: If you can afford it, using distinct keys for signing and for encryption is still highly recommended."

My question is whether reusing an Ed25519 keypair for both uses has been proven secure anywhere, for example in the sense of Joint Security of Encryption and Signature or a similar paper?

The two constructions seem to be:

EdDSA signature (i.e. "Schnorr signature done properly")
Ephemeral DH key exchange using a one-time keypair on the sender side and the recipient's public key (mapped to Curve25519).

Both involve a one-time ephemeral keypair and a hash function, I'm fine with the random oracle model (so we can assume the EdDSA nonce, which is actually a function of the key and message, is really random) and one can get domain separation by including a separation tag in the key exchange, i.e. when Alice wants to send a file to Bob whose public key is Q, she picks a pair (r, r.P) and sets the key as k = H(r.Q, "this is a key not a signature") or something similar.

Intuitively this should be fine in the random oracle model; has someone actually (dis)proved it though?

The paper On the Joint Security of Encryption and Signature in EMV is very close. Section 4.4, "On the Joint Security of ECIES and EC-Schnorr", states the following result:

  Theorem 2. In the random oracle model ECIES-KEM and EC-Schnorr are jointly secure if the gap-DLP problem and gap-DH problem are both hard.

Obviously, this does not apply to EdDSA/DH out of the box: ECIES is a certain application of Diffie-Hellman, and EdDSA is a slightly modified variant of elliptic-curve Schnorr signatures.
However, the proof sketches in the paper should be easily adaptable to EdDSA combined with any other reasonable Diffie-Hellman incarnation. (The details of this depend a little on how the DH shared secret is used for symmetric (authenticated) encryption, but it seems possible to modify the proof for all realistic settings.)


find master key given all but last decryption round keys I have all but the last round key in AES-256 CBC decryption, and would like to build the master key, but I am unsure how to go about it.
I have read I can convert decryption roundkeys to encryption roundkeys via forward MixColumns. Then perhaps xor key n-3, n-2 to get n-1 (one i need). Does S-box substitution come into play here?
Or is there a keyschedule generator based on decryption roundkeys rather than encryption... thank you for the help.

Unless you have a non-standard version of AES decryption, the decryption round keys should just be the encryption round keys in reverse order. In the notation of the wikipedia article, it sounds like you have $W_4,\ldots,W_{59}$ and you want to know $W_0,\ldots, W_7$ ($W_4,\ldots W_7$ represent the penultimate decryption round key; $W_8,\ldots W_{11}$ represent the antepenultimate decryption round key and so forth).
$W_4,\ldots W_7$ can be read off directly and (per the linked article) we have
$$W_8=W_0\oplus S(\mathrm{LeftShift}(W_7)\oplus 1\iff W_0=W_8\oplus S(\mathrm{LeftShift}(W_7))\oplus 1$$
and
$$W_9=W_1\oplus W_8\iff W_1=W_9\oplus W_8$$
$$W_{10}=W_2\oplus W_9\iff W_2=W_{10}\oplus W_9$$
$$W_{11}=W_3\oplus W_{10}\iff W_3=W_{11}\oplus W_{10}$$
which allows us to recover $W_0,\ldots,W_7$ which is the same as $K_0,\ldots, K_7$.
Note that the LeftShift function rotates the 32-bit word left by 8 bits and that the $S$-box is the same as used in AES encryption.
ETA if you are using the "T-table" implementation of AES (which is suggested by your MixCol remark), then yes, you will need to apply MixCol to the 32-bit words to get the $W_i$. If you use the standard AES MixCol() then no S-box adjustment is needed; if you use the T-table combined MixCol(Subbytes()) then you'll also need to apply the Inverse S-box as well.


Explain mixing bijection with an example I am reading whitebox AES. "Mixing Bijection" is one of the important definition. For example, I copy one paragraph here:

The look-up tables that incorporate bytes of round keys can be considered miniature block ciphers. The application of concatenated input and output encodings help these components achieve confusion, as defined by Shannon. To help
them achieve diffusion, linear transformations are also composed at their input and output (these compositions are done before the application of the concatenated input and output encodings). An invertible linear transformation is
referred to as a mixing bijection.

I have read the definition of bijection online, which is easy to understand. What means mixing bijection? Explain in "simple" English, better with an example.

What they are referring to as a mixing bijection is the MixColumns step of the AES round function. It functions to improve diffusion by reversibly scrambling the state of each column. Recall that the block state consists of a 4x4 matrix of byte-sized elements (totaling 16 bytes, or 128 bits), so each of the four columns are composed of four vertical elements. The MixColumns transformation is applied to each column in parallel. It is just one step of several. Together with AddRoundKey, ShiftRows, and SubBytes, it makes up a single AES round. Ten to fourteen rounds are applied to the input for a single block.

It is referred to as a mixing bijection instead of just a bijection to imply that the output is random. Not all bijections appear random of course. This isn't standard terminology, which explains the confusion. Just think of it as a bijection whose output appears fairly random, making it useful for diffusion.

I strongly recommend you read A Stick Figure Guide to the Advanced Encryption Standard (AES). It is a wonderful explanation of the intrinsics of AES, including MixColumns, and is very easy to understand.


How modern messengers encryption keys can't be hacked I dont know is this question more like reverse-engineering or cryptographic.
Why governments are hunting for encryptions keys? Aren't they delievering by the network the same as the encypted messages? What doing it end-to-end encrypted?

Aren't they delievering by the network the same as the encypted messages?

No. At least not in the plain.

  What doing it end-to-end encrypted?

Try to search for the key agreement protocol (e. g. Diffie-Hellman ) and asymmetric encryption (e.g. RSA ).

The "asymmetric" encryption allows sending encrypted and signed messages without sharing the private (secret) key.

Very simplistically explained - each actor creates a key pair (with a public and private part) and the actors will exchange their public key. That allows both actors to securely create a shared secret even on an unsecure channel


Are there any authenticated stream ciphers that use the same PRF for MAC and cipher? A PRF can be used both to generate a key stream for use in a stream cipher, and to construct a MAC to authenticate. The two can then be combined e.g. in a generic encrypt-then-MAC construction to create an authenticated stream cipher, using the same PRF for both (with independent keys). Is this actually done in any real-world authenticated encryption scheme? I see constructions like Salsa20/ChaCha20 stream ciphers combined with Poly1305 (a secure MAC, but not a PRF). Presumably you could combine ChaCha20 with Blake2, which is based on the same round function internally, but even here there are differences in the PRF (as I understand it). Are there any real-world cases where exactly the same PRF is used for both? If not, is there a reason why not?

One similar real-world construction I can think of is CCM mode where the same block cipher (e.g. AES) is used both in CBC-MAC and then in CTR mode. This provides some code size advantages as the same code can be used for both operations (and you only need the encrypt direction of AES too). Presumably similar arguments could be made for an authenticated stream cipher that used the same PRF for both key stream generation and MAC.

The Duplex constructions of Keccak (now standardized as SHA-3) work this way.

See:
http://sponge.noekeon.org/SpongeDuplex.pdf

And

http://keccak.noekeon.org/KeccakDIAC2012.pdf

I believe some variant of this is in the process of standardization by NIST, but I haven't seen a draft yet. See:

http://csrc.nist.gov/groups/ST/hash/sha-3/Aug2014/documents/sonmez-turan_sha3_2014_workshop.pdf


Garbled circuits: How can the sender safely retrieve the output? I've read a few papers about how Yao's Garbled Circuit protocol can be made secure against malicious adversaries, but I haven't seen any mentioning how the sender safely retrieves the output of the function after the receiver computes it.

Suppose Alice is the sender, that is to say she garbles the circuit and sends it to Bob. Now suppose the whole protocol goes fine and at the end Bob outputs the right answer. In the context of two-party secure computation, both parties should be able to obtain the right output of the function, but what if Bob is malicious and doesn't simply send back the answer to Alice?

At that point, Bob could either stop the protocol or send a wrong answer to Alice. Does there exist a mechanism which can both prevent Bob from knowing the output until Alice knows it too, and ensure that what Alice obtains is the right output?

There are two separate issues here:

Guaranteed output / fairness: how does the protocol prevent Bob from withholding Alice's output (guaranteed output), or at least prevent him from learning the output himself when he decides to withhold output from Alice (fairness)? The short answer is that garbled circuit protocols do not provide any such guarantees. The standard definition of malicious security in this area is "security with abort". This model allows a malicious party to learn their output first and subsequently prevent the honest party from receiving output.

The reason for this is that it is impossible to guarantee fairness in general, for 2-party secure computation. This is due to an old result of Richard Cleve (Limits on the security of coin flips when half the processors are faulty, STOC 1986). Since fairness is impossible for some 2-party functions, and garbled circuits give you secure 2PC of any function, you cannot hope for a typical garbled circuit protocol with fairness.

Output authenticity: how does the protocol prevent Bob from lying about the output to Alice, in the case that Bob doesn't withhold her output altogether? There are several approaches but one I like is to just have Bob present the output wire labels back to Alice. Wire labels have an "authenticity" property: the evaluator only learns one on each wire and cannot guess the complementary one. Hence they act as a kind of "proof" to Alice that this was indeed the correct output.

This is the main idea but there are quite a few pitfalls to avoid. It helps if all circuits in the cut-and-choose have the same output wire labels. But then if some of those circuits are opened during cut-and-choose, it breaks the "authenticity" property. So you have to arrange things in a clever order: After Bob evaluates the circuits, he commits to the output wire labels. Then the check-circuits can be opened. If they are all good, only then does Bob open the commitment to the output wire labels.

Two-output Secure Computation With Malicious Adversaries:
abhi shelat and Chih-hao Shen, Eurocrypt 2011 (uses a different technique but focuses explicitly on getting output to the sender)
Garbled Circuits Checking Garbled Circuits: More Efficient and Secure Two-Party Computation: Payman Mohassel and Ben Riva, Crypto 2013 (uses the wire-label-authenticity idea I mentioned)
Zero-Knowledge Using Garbled Circuits: Marek Jawurek and Florian Kerschbaum and Claudio Orlandi, CCS 2013 (uses the wire-label-authenticity idea as the basis of a ZK proof: possibly malicious GC evaluator has to convince the GC generator of the circuit's output)


Encrypting and Authenticating The Simplex Communication Between Embedded Devices I am planning to build temperature sensor nodes for my home heater control. Central device will control the heater using temperature data read by nodes. These nodes will send temperature data to central device over RF communication periodically. There will be no acknowledge from central device to nodes. I want to learn something about encrypted communication at the same time. I have little general knowledge and no experience about encryption.

It is common that today microcontrollers have built-in cryptographic engine supporting AES with ECB, CBC, OFB, CTR and CFB128 modes with true random number generator. (ref)

I have two goals:

Communication should be encrypted. Attacker can't read the temperature value by sniffing.
Once a node sends a encrypted message, this messages should become invalid for retransmission. For example, each message should be different even if a node transmits the same temperature value. Attacker can't act as a true sensor node by transmiting false temperature values to my heater.

My questions are: (Please consider that I have no background in cryptography.)

Encryption is not so hard. For example, I may use AES-128. But simple ECB mode doesn't satisfy my goal #2. If temperature doesn't change, AES-128 output will also be the same. AFAIU I should use encryption + authentication. I have to ensure that encrypted message is sent from a valid node not from an attacker. Is authentication term is the correct one for this case? For example, does AES-CCM overcome this problem? I read several sources about AES-CCM and other encryption + authentication methods and I couldn't correlate my problem with the authentication term used in cryptography.
Let's say that node increments a counter by one at each transmission. Plain data is now value of counter + temperature. Plain data is encrypted and sent. Counter ensures that data changes even if temperature is the same. Receiver now tracks value of the counter and ignores the message if it is not incremented by one (or within a range). It should help me to satisfy goal #2. I think this approach is similar to Keeloq algorithm. Attacker shouldn't guess the next encrypted text easily. Does it make sense?
Hardware has true random number generator. Can it be used somehow to make communication more "secure"? For example plain text =  value of counter + data + some random bits. Does random bit stuffing make any improvement?
Probably my ideas are the worst ones. What would you suggest for data validation? How can a node "sign" its data?

For my answer, I'll assume that you have symmetric keys pre-shared between your heater and your sensors. If your devices have enough computational power to support asymmetric cryptography (which will increase workload by a large factor and message length by at least 32 bytes) the answer will be different (and provide stronger guarantees).

AES-128 CCM is a good choice for your use-case because your hardware supports the required primitives, e.g. AES-CTR and AES-CBC.  Authentication in cryptography means ensuring the correct source of information. If information is tampered in transit, the tampering party is the new source. Assuming you pre-share the symmetric keys in advance, AES-CCM will ensure the data actually came from a party holding the key or otherwise return an error upon decryption.
Actually you can do better than that. AES-CCM requires a so-called (12-byte) nonce  for operation for each message. This nonce only needs to be unique to provide the full security guarantees and so you can define the nonce to be a counter whereby the nonce gets incremented by one each message. If a too-small counter (IV) arrives, you can simply reject the message. You only need to ensure that the length field for CCM is long enough to describe your message length (4 bytes would be good).
Sadly no. If you use pre-shared keys, there's no further need for randomization from the cryptographic side of things. If you'd involve asymmetric cryptography, the RNG would actually prove useful (for generating temporary keys and such).
The best solution would be for your nodes to actually digitally sign the data they send, assuming the heater has the public keys in advance, so he can validate the signatures. However, such signatures tend to be computationally expensive and so may not be an option for you.


Can we prove possession of an AES-256 key without showing it? Imagine this situation:

Alice has an AES256GCM key $K$, a plaintext $X$, and $Y$ which is the ciphertext of $X$ encrypted by $K$
Bob has $X$ and $Y$
Alice and Bob can communicate with each other
Bob wants to know whether Alice holds the key which encrypts $X$ into $Y$

In this situation, Can Alice prove that she has $K$ without showing $K$?
and if so, how to do it?

Yes she can. She would do so by relying on a boolean circuit that takes $K$ as input, uses it to encrypt the plaintext $X$, compares it to $Y$, and outputs $1$ if and only if the comparison succeeds. Given such a boolean circuit $C$ (that both parties can construct), Alice must prove that she knows an input $K$ to $C$ so that $C(K) = 1$.

The task of proving knowledge of a witness for a relation described by a boolean circuit (in zero-knowledge, hence without leaking any information about the witness) has been studied a lot in the cryptographic community. Several protocols exist for this task, Zkboo is one example. It has three moves, and is based on the MPC-in-the-head technique introduced in this seminal paper.

Other solutions (see also this paper and the related but somewhat different solution presented in this paper) achieve a comparable efficiency, and are based on garbled circuits: Alice will hand Bob a "garbling" of $C$, which takes as input an encoding of her witness $K$, and evaluates the circuit on $K$ in a hidden way, and outputs $C(K)$ (the details are quite technical, so I'll stick to this high level explanation unless you want a deeper overview of how it works).

EDIT: corrected the statement that Zkboo was based on garbled circuit, I had confused it with another paper, thanks to redplum for pointing this out.


How to Sample from Frobenius Eigenspace? So I was implementing the $2$-point method described here[1], which requires to samples two points $P_0, P_1$ in the Frobenius eigenspace initially. It uses a method called Elligator, which seems to me only samples $\mathbb F_p$ rational points.

Suppose one is given a supersingular curve $E$ defined over $\mathbb F_p$ with Elkies prime $\ell$. Since the $\ell$-torsion $E[\ell]$ is a $\mathbb F_\ell$-linear space of rank 2 and the Frobenius mapping $\pi$ is linear. Let $\lambda$ be one of the eigenvalue in $\mathbb F_\ell$. How would one sample from its corresponding eigenspace $E[\pi-\lambda]$?

For $\lambda=1$ we simply take $\mathbb F_p$-rational points, but what about cases where $\lambda \neq 1$, say $\lambda=-1$?

[1]"A Faster Constant-time Algorithm of CSIDH keeping Two Points," page 10, Algorithm 3.

The Frobenius eigenspace of $-1$ is, by definition, the kernel of the map $π+1$. Typically, this is further restricted to some torsion group $E[ℓ]$, so we are really talking about $E[ℓ] ∩ E[π+1]$, i.e., those points of $E[ℓ]$ such that $π(P)=-P$.

If the curve is expressed in Weierstrass form $y^2=f(x)$ (or Montgomery, or similar), letting $P=(x,y)$ we have $-P=(x,-y)$. Thus the Frobenius eigenspace is made by those points $(x,y)$ such that $x^p=x$ and $y^p=-y$.  A little theory shows that this is the set of rational points of the twist of $E/_p$.

So, the obvious way to sample the points is to

Choose a random $x\in _p$;
Check that $f(x)$ is not a square, i.e., that $y=\sqrt{f(x)}$ is not in $_p$, i.e., that $y^p=\sqrt{f(x)}f(x)^{(p-1)/2}=-\sqrt{f(x)}=-y$;¹
See $(x,y)$ as a point in $E/_{p^2}$, multiply by an appropriate cofactor to obtain a point in $E[ℓ]$.

¹To see why this works, note that $f(x)$ is not a square in $_p$, thus its Legendre symbol is $-1$. By the way, saying $x$ is in $_p$ and $y$ is not is equivalent to saying that $x$ is the abscissa of a rational point on the twist.

If $\#E(_p)=p+1-t$, where $t$ is the trace of $π$, then the twist has order $p+1+t$, thus the "appropriate cofactor" above is $(p+1+t)/ℓ$. Note that $E[π+1]∩E[π-1]=E[2]$ (because $1=-1\mod 2$), thus for $ℓ=2$ the two ℓ-restricted eigenspaces are indistinguishable, and you would get a random point of order $2$; however for any other prime $ℓ$ there are two distinct eigenspaces, and step 3. will stay in the twist.

Steps 1. and 2. above can be replaced by Elligator 2, which samples simultaneously in both the eigenspace of $+1$ and that of $-1$. The original Elligator 2 was explained as a map to $E[π-1]$, but the generalization to a map to $E[π-1]×E[π+1]$ is easy and has been hinted at in several papers. For an explicit description, see Section 3, and Algorithm 3 in particular, here: https://eprint.iacr.org/2019/837.

All this can be generalized to arbitrary eigenvalues $λ$, not just $±1$. The multiplicative order of $λ$ in $ℤ/ℓℤ$ determines the degree of the extension of $_p$ where the points $E[π-λ]$ are defined.


Blinding twice in RSA I understand that if you have a message $m$, you can blind it by selecting a random $r$ and then multiplying $r^e\times m \pmod{n}$ Someone else then signs it with $d$, raising to the power of $d$:  $(r^{ed}\times m^d) \bmod n = r \times m^d$.  Finally to unblind: $r^{-1}\times r \times m^d = m^d$ and $\left(m^d\right)^e = m$.  I understand that.

However, what if I wanted to blind twice?  So after the first blind:  $r_1^e\times m \pmod{n_1}$.
After the second blind:  $r_2^e \times [(r_1^e \times m) \bmod n_1] \bmod n_2$.
Then someone signs it with $d_2$:  $\big(r_2^e \times [(r_1^e \times m) \bmod n_1] \bmod n_2\big)^{d_2} = r_2 \times [(r_1^e \times m) \bmod n_1]^{d_2}$.
Then to unblind the first round:  $r_2^{-1}\times r_2 \times [(r_1^e \times m) \bmod n_1]^{d_2} = [(r_1^e \times m) \bmod n_1]^{d_2}$.
Next:  $[(r_1^e \times m) \bmod n_1]^{d_2e_2} = (r_1^e \times m) \bmod n_1$.
Finally to unblind the second round:  $[(r_1^e)^{-1} \times r_1^e \times m] \bmod n_1 = m$

Am I going wrong somewhere in my math?  Because I wrote a program to do this and the strangest thing — sometimes it gives me the original message and sometimes it does not.  However, it does work perfectly when I comment out either round 1 or round 2.  So my program doesn't work for both rounds, but works for a single round.  I know this isn't the place to ask for programming help, but I'm thinking my math is off somewhere.  Does it have to be the case:  $\gcd(r_1, n_1) = \gcd(r_1, n_2) = \gcd(r_2, n_1) = \gcd(r_2, n_2)$ that both values of $r$ cannot have a common factor with both values of $n$?  Or did I make a mistake somewhere else?

As long as you ensure that $n_1\leq n_2$ is guaranteed, the value $r^em\pmod {n_1}$ can be treated as an element in $Z_{n_2}$ and the "outer blinding" and "outer unlinding" in $Z_{n_2}$ does not change this value. Consequently, if you compute the "inner unblinding" in $Z_{n_1}$ after the "outer unblinding" your proposal works.

Remarks from the previous comments:

fgrieu – in his comment – also provided a trick for cascading signatures when working with different RSA moduli. This, however, does not apply to your setting since you are not cascading signatures (maybe you want to do that?)

Your application scenario:

As CodesinChaos noted in his comment in response to your desired application, your approach still raises some questions.

A simple eCash protocol on blind signatures does not really require you to do that. There, you can assign different values for coins by setting up different signing key pairs for the bank (one for each value) and the coin (value $m$ in your case is simply a random element). If the merchant blacklists the unblinded value and signature pairs, then you can prevent doublespending. Although you will not achieve anonymity revocation in case of this event.

It is not clear for what purpose you want to include customers identites into the coins - maybe you want to have something like anonymity revocation? (why you therefore require another modulus $n_1$ - as well as use blinding without signing this part)? I think there is still potential for discussion.


The main differences between Sketch of Proof and Full proof My question in general is:

Question 1: What are the differences between sketch of proof and full proof?

In simulation-based proof, in semi-honest model, we construct a view that is computationally indistinguishable from real view. Then we argue that the two views are computationally indistinguishable.

Question 2: Why is this approach "only sketch" of proof?

Question 3: What would the full proof be like (in reduction format)?

Edit: Why do most of papers in the well-known conferences provide only the proof sketch?

The answer to this question is not straightforward and has a lot to do with the "conference culture" of computer science. Unlike other fields, the main publication venues for CS are conferences and not journals. This isn't to say that journals don't have an important role; rather, you don't follow journals to see what research is being done - you follow conferences. (Note that also unlike other fields, conference papers ARE peer reviewed. So, some basic validation has already been done.) Journals are mainly there to validate correctness in a more rigorous way. Much has been said about the advantages and disadvantages of this culture and there are certainly both. Conference culture enables a very fast dissemination process, but it also means that people work towards deadlines and don't always have full proofs.

Ideally, one would expect researchers to have full proofs of security and then cut them down to proof sketches in the conference version. However, in many cases, this just isn't true, and this can lead to errors. Note that even when writing full proofs you can have errors, and I've had my fair share of published mistakes. However, at least I try to do my best in writing a full proof (which also makes it easier to spot the mistake if it's there). To be honest, though, I haven't written full proofs for all my papers as well, and I too am negligent in that.

Having said all of the above, some things are so obvious to the experienced researcher that writing them out in full is actually a disservice. We all know how a standard hybrid argument works, and therefore writing it out will only fill up the paper with useless details that don't help at all in understanding the result. My recommendation is to always write out the full hybrid to check that there is no subtlety. Then, if it turns out to truly be standard, writing "the full proofs follows a standard hybrid" is not only OK but also better. So, sometimes proof sketches are not laziness or lack of rigor, but a way to make a proof more readable to the experienced reader (and the inexperience would be best served by learning this in Goldreich's book anyway).

In summary, why aren't proof sketches always written?

Sometimes the full proof is just a difference of obvious details and not good to publish
More often, it's due to the conference and not journal culture. This can be due to the fact that the researchers are working to a tight deadline and never wrote a full proof [VERY BAD IN MY OPINION] or due to the fact that the conference limits the page numbers and so it can't be put in [ALSO PRETTY BAD].

The right thing to do scientifically is to have a full proof (modulo details that are not worth putting in as in the previous item) and then cut it down to a proof sketch for the conference version. In this case, a full version should always be put on your homepage or ePrint, and if it's an important result then it should be sent to a journal.

One last point, conference papers are now rarely actually printed, making the page limit quite unnecessary. Of course, it's not possible to review the entire paper in the conference refereeing procedure, but the published version can be considerably longer and numerous conferences are doing this. Still, in many cases, it's not long enough for a truly full version and this should be posted as mentioned above.


How can one protect against a Man In The Middle attack during key exchange without using certificates? Besides using a certificate to defend against a man in the middle attack

during a key exchange, what methods can be used?

Any shared secret can be used. Securely distributed passwords and symmetric keys, for example.  Alternatively, you can use asymmetric cryptography, such as public keys.

For one example, SSH has for years authenticated servers using public key cryptography and users typically using either public keys or passwords. Only recently had SSH added support for certificates.


Is there such thing as an order independent, updatable hash? I have an application where I have a set of primitive units, $P = \{p_0 ... p_n\}$ (they are byte-arrays, in my application).

I want to be able to create a hash value $H(S)$ for any subset $S \subset P$, such that:

I can update a hash without knowing what it hashes. So given $H(S)$ and $T$ (where $S, T \subset P$), there is some function $f(H(S), T) = H(S \cup T)$. Note this works without knowing the contents of S, only its hash.
The hash value is independent of the order. So $f(H(S), T) = f(H(T), S)$.

The answer largely depends on what security properties you want.

The scheme I would use here is to hash all of the individual parts, then take some Diffie-Hellman group, and then raise the generator of that group to the power of the product of the individual hashes. That is,

$ H(a_1, ..., a_n) = g^{\operatorname{SHA256}(a_1) * ... * \operatorname{SHA256}(a_n)} \bmod p $

for $ * $ being multiplication and $ g $, $ p $ being the generator and modulus of the Diffie-Hellman group. (This could also be done with an elliptic curve group to the same effect).

This provides a number of properties:

It is secure given a reasonable Diffie-Hellman group (if you're using Diffie-Hellman based on modular arithmetic, then $ g $ needs to be reasonably large, or $ g^{a} $ may not be larger than $ n $), and reasonable assumptions similar to DDH
It is communitive; that is, the hash value is independent of the order of the hash (and it can be updated after it's computed by raising the computed hash to the power of a new block)
It is reasonably fast

You may also want to consider using a block chain; it's faster, although it isn't communitive, which is one of the properties you asked for. (I also initially considered using XOR in place of exponentiation in a group, but I quickly realized that can be defeated with Gaussian Elimination. It's possible I'm missing something there, though).


RSA-based authentication and key-agreement protocol An authentication and key-agreement protocol between devices shall mutually demonstrate their identity, and establish a shared random secret $R$ suitable for securing later communications.

To that purpose, each of the many devices receive a certificate from a certification authority, binding their identity $ID_i$ (including unique serial number and operational characteristics) to their unique RSA public key $(N_i,E_i)$. The legitimate device with $ID_i$ is initially assumed to be the only thing to possess the RSA private key $(N_i,D_i)$ corresponding to its certified public key, and use it per the protocol's rules only.

An adversary's goal is to convince a legitimate device $i$ that another legitimate device $j$ with $ID_j$ was used during the protocol, when it was not; or to breach the confidentiality of $R$ that $i$ will use (with the assumption that $j$ will not breach it); or make that $R$ different from what it would be under normal execution of the protocol.

The protocol must resist disclosure of $R$ from earlier executions, and compromise of the private key of other legitimate devices. Communications are insecure, including ability for an adversary to alter, replay, or create messages (or communicate with other legitimate devices, but compromise of their private key covers that).

We can assume that in preliminary steps of the protocol, the two participating devices have exchanged their alleged identity and certificate, in clear; have verified the certificates using a conventional off-line PKI; and have unambiguously agreed upon Master/Slave roles in the protocol (statically determined from their respective $ID$; or perhaps with the device having the highest alleged $ID$ assuming Master role).

We want something simple, suitable for implementation in a Smart Card. We'd rather avoid use of a block cipher or MAC during that protocol, though we may assume a hash as used in an RSA message/signature encoding scheme.

I'm looking for literature (or an answer) discussing such protocol, hopefully something with a security argument. One theoretical difficulty is that on each side we have a single key for both mutual authentication, and confidentiality of the shared $R$.

One such protocol is specified in a European Regulation: EEC 3821/85 as modified by EC 1360/2002 and EC 432/2004, Annex 1B, Appendix 11, CSM_020, second drawing, as found page 268 of the PDF, starting with Generate Challenge. Incidentally, I'm interested in the origin of this protocol, or if it is reminiscent of something used elsewhere; and in additional security goals that it might have. To the best of my knowledge it is secure in the sense stated above, but I know of no security analysis. I tried to summarize that protocol, but the question's size doubled before I was done with notations, so I gave up for now.

Nothing in this is related to my current professional activity.

What you are looking for is authenticated key agreement with perfect forward secrecy based on certificates.

First, to address @Paulo's comment, TLS/SSL does provide this functionality with any of the Diffie-Hellman based suites. However it is more complicated than you require, as it generates several different shared secrets used for different purposes. SSH and IPSec have similar protocols.

The landmark key exchange protocol with the required properties is called the station-to-station protocol. I recommend the discussion of it (and the whole chapter for context) in the Handbook of Applied Cryptography (ch 12, pg 519).

STS does require an encryption function which you specified you wanted to avoid. A modern key exchange that does not have an encryption function is MQV and its variants. Since you also wanted a rigorous security proof, likely more has been written about MQV and its variant's security than any other protocol (although the history is somewhat sordid). The drawback for you is that it requires the public keys (in the certificates) are discrete log-based not RSA (STS can work with RSA public keys since the long-term secret is only used for signatures). It may also be patent encumbered.

To conclude, I don't have a perfect protocol that both works with RSA and avoids using encryption or MACs but looking into these two protocols should give you a head start on finding something you can work with.


Why is Tor alone not enough to guarantee anonymity for Bitcoin? Why is Tor alone not enough to guarantee anonymity for Bitcoin?

Why do we need the constructions like Zerocoin?

Bitcoin was designed to be decentralized, but was not designed to be anonymous.  How you use (earn or spend) Bitcoin cannot (in general) be made anonymous because the protocol was not designed to support that.  In fact, the design of Bitcoin,  being decentralized, requires all participants to be able to confirm all transactions.

You can use Tor to add to the level of anonymity of Bitcoin by creating a more anonymous "owner" of a Bitcoin wallet.  The transaction can still be traced back to this wallet, but it may be more difficult to tie the wallet to a specific entity.  This is hindered, however, because the wallet is only useful if it can, at some point, be converted to/from real currency--a process that is frequently traceable through traditional banking means.

Another technique to make tracking Bitcoin transactions more complicated are basically a form of digital money laundering...services that take in Bitcoin from one user and give it out to a different [set of] user(s), and visa-versa.


RC4 encryption/ decryption with hashing I am working on RC4 encryption/ decryption algorithm based on the following:

A wants to send M to B, for that A did:

H = Hash (K||M)
C = Ek (M||H)

A sent ciphertext C to B. (I have completed until this part)

Upon receiving of ciphertext B calculate:

M||H = Dk (C)

Now, how do we obtain M as I need to verify if H' = Hash (K||M) holds.

Since you already know $K$, you just need to know the length of $H$ based on the hash algorithm you are using, which should be constant, then simply split the output of $D_k$ into the 2 parts of appropriate length.

You can then perform the keyed hash on the first part and match it against the last part, which will match if the decryption was successful.

It should be noted that your method is not aligned with best practices, such as NOT hashing using key prefixing (unless you are using Keccak or other sponge based hash), and NOT hashing the plaintext, but rather the ciphertext, as attacks are possible, especially with RC4. Also it is not recommended to use the same key for both encryption and authentication as per your example.

A better option is:

$C'$ = $E_k (M)$

$C$ = $C'$ $||$ $HMAC_{k'} (C')$

Where $C$ is the final transmitted message, and the hash is checked prior to decryption of the message, and $k'$ is a separate or derived key just for authentication.


Challenging Question for the Build a Secure MAC with Special Properties We would like to ask you to give a construction for requested scheme which provides those properties or give a proof that is not achievable.

[Note that unsuccessful attempts to build such a scheme can be found on the links Is this "linear combination" of PRFs and Hashes a secure MAC? and Is this construction a secure MAC?

Definition (MAC scheme).
A message authentication code (or MAC) consists of
three probabilistic polynomial-time algorithms $\Pi =(\mathsf{Gen}, \mathsf{Mac}, \mathsf{Vrfy})$ such that:

The key-generation algorithm $\mathsf{Gen}$ takes as input the security parameter $1^n$ and outputs a key $K$.
The tag-generation algorithm $\mathsf{Mac}$ takes as input a key $K$ and a message $m =a_1||a_2$ (where $a_1, a_2 \in \{0, 1\}^{n}$, and outputs a tag $T=(t_1,t_2)$ (where $t_1,t_2 \in \mathbb{F}^*_q$). Since this algorithm may be randomized, we write this as $T \leftarrow \mathsf{Mac}_K(m)$.
The deterministic verification algorithm $\mathsf{Vrfy}$ takes as input a key $K$, a message $m$, and a tag $T$. It outputs a bit $b$, with $b = 1$ meaning valid and
$b = 0$ meaning invalid. We write this as $b := \mathsf{Vrfy}_K(m, T)$.

Expected features include:

correctness condition: it is required that for every $n$, every key $K$ output by $\mathsf{Gen}(1^n)$, and every
$m \in \{0, 1\}^{2n}$, it holds that $\mathsf{Vrfy}_K(m, \mathsf{Mac}_K(m)) = 1$.
linear combination: the construction must be provided based on a linear combination of PRFs and Hashes.
forge conditions: we redefined the condition of the attacker's success for pair $(m=a_1\mathbin\|a_2,\;T)$, so that $\mathsf{Vrfy}_K(m,T)=1$, $a_1 \neq a_2$, and also $a_1\mathbin\|a_2$ or $a_2\mathbin\|a_1$ did not asked its oracle.
validation structure: it is required that algorithm $b := \mathsf{Vrfy}_K(m, T)$ act as follows, where $f$ and $g$ are polynomial-time algorithms:
$$f(g(K,a_1),T) \stackrel{?}{=} f(g(K,a_2),T)$$
That is $\mathsf{Vrfy}$ should return $1$ iff the above expression holds and $0$ otherwise.

Here is a construction that appears to meet all your criteria:

We will assume that:

$k \ge 2^{n+1}$
$MAC'_k(a | b)$ is a standard deterministic MAC (e.g. HMAC) of the string $(a | b)$

Then,

$\mathsf{Gen}$ generates a random $MAC'$ key

$\mathsf{Mac}$ is defined as $\mathsf{MAC}_k(a_1, a_2) = (t_1, t_2)$ where $t_1 = a_1 + MAC'_k( a_1, a_2)$, $t_2 = a_2 + MAC'_k(a_1, a_2)$

Within $\mathsf{Verify}$, we have:

$g(K, a_i) = (K, a_i)$

$f((K, a_i), (t_1, t_2))$ defined as:

If $0 \le t_2 + a_i - t_1 < 2^n$ and $MAC'_k( a_i, t_2 + a_i - t_1 ) = t_1 - a_i$, then the result is $0, \mathsf{Success}$
If $0 \le t_1 + a_i - t_2 < 2^n$ and $MAC'_k( t_1 + a_i - t_2, a_i) = t_2 - a_i$, then the result is $0, \mathsf{Success}$
The result is $1, a_i$ otherwise.

Showing that most of the conditions hold is straight-forward; showing that this resists forgery is slightly involved.  To start, the MAC will declare success only if both sides have either $MAC'_k( a_i, t_2 + a_i - t_1 ) = t_1 - a_i$ or $MAC'_k( t_1 + a_i - t_2, a_i) = t_2 - a_i$ (because the MAC of the pair $(a, a)$ is forbidden.

Now, if the two sides satisfy opposite relations (say, $a_1$ satisfies the first, and $a_2$ satisfies the second, then simple algebra gives us:

$$t_1 - a_1 = t_2 - a_2 = MAC'_k( a_1, a_2 )$$

That is, to generate this forgery, the attacker must successfully predict $MAC'_k( a_1, a_2 )$.

Alternatively, if the two sides satisfy the same relation, for example, both sides satisfy the first, namely we have both:

$$MAC'_k( a_1, t_2 + a_1 - t_1 ) = t_1 - a_1$$

$$MAC'_k( a_2, t_2 + a_2 - t_1 ) = t_1 - a_2$$

This implies that the attacker has found two MAC inputs with the relation:

$MAC'_k( a + \delta, b + \delta ) = MAC'(a, b) + \delta$

This is not believed to be feasible without knowing the MAC key.


Why in RSA do we use mod n rather than mod phi(p⋅q)? When we pick $e$: $$e \in \{1,2,3,4,...,\phi(p\cdot q)-1\}$$
where $\gcd(e,\phi(p\cdot q))=1$. Similarly when computing $d$ which is the modular inverse of $e$ (the private key) we use the extended Euclidean algorithm as
$$\operatorname{EA}(e, \phi(p\cdot q))$$
so that $$e\cdot d \ \equiv \ 1\pmod{\phi(p\cdot q)}$$
So having a message $X$ why does simultaneously encrypting and decrypting message as
$$ {(X^e)}^d \equiv  X \pmod{\phi(p\cdot q)}$$
not work, as it should be equivalent to $X^{e\cdot d}$ and $e\cdot d$ are the inverse of each other in the set of  $\{1,2,3,4,...,\phi(p\cdot q)-1\}$ so they are supposed to cancel each other which is supposed to be the idea of RSA.
I know that $e\cdot d$ result in plaintext to be decrypted to 0.00 if I follow the normal encryption/decryption process (since I tried it)
Can anyone explain why it does not work as described?

There are two reasons for not using $\varphi(n)$ during encryption.
The first one is that it doesn't work - you can verify this by looking at the RSA correctness proof. It requires, that the modulus is $n$.
The second one is - if you know $\varphi(n)$ you can efficiently compute $d$ given $e$, and therefore know the private key.


RSA-OAEP versus RSA with Fujisaki-Okamoto construction I was wondering why the Fujisaki-Okamoto construction (or one of its variants) is not (at least commonly) used with RSA to achieve CCA2 security? Does anyone know of any speed comparisons between RSA w/ F-O and RSA-OAEP? Perhaps the reason is simply historical since F-O is newer.

The Fujisaki-Okamoto construction requires a non-deterministic public key encryption scheme. Textbook RSA is not randomized, but deterministic, and so it cannot be applied to it to obtain CCA-security. It can be applied to schemes like Elgamal and Paillier that take randomness to create indistinguishable encryptions of the same message.


Best way to hash two values into one? I'm trying to hash two unique strings together to create a hash. The most obvious way would be simply to concatenate the two and run a hash function on it:

hash = sha256(strA + strB)

But I was wondering if this is how most people do it, and if there is a "standard" way of doing something like this in a most secure way.

The most important thing you're missing is that you should combine the two strings with an injective function: a function such that every unique combination of inputs determines a unique output.

Your idea to just concatenate the two strings violates this condition.  One example is that "abc" + "def" is the same string as "ab" + "cdef" or "abcd" + "ef".  Whether an adversary can exploit this to their advantage depends on the application, but there's no reason to expose oneself to this risk to start with.

Some techniques for combining strings in an injective fashion:

Put an unambiguous delimiter between the strings
Prepend each string with its length

Another tip: whichever method you pick, write a function that can "split" any combined string back into its components, and a bunch of test cases to show that the property split(combine(strA, strB)) == (strA, strB) holds for all values of strA and strB.


Post-quantum asymmetric encryption algorithms One could use Falcon-512 for establishing a private and public key for an asymmetric context. Whereas in a symmetric context, we could use firesaber/saber/variants in order to obtain a shared secret that can later be used in an AES-GCM context. My question is: what encryption algorithm do we use when we want to encrypt plaintext when using a public key instead of a shared key? What post-quantum encryption algorithms (i.e., a map from plaintext to ciphertext) exist that are compatible with asymmetric schemes such as falcon? If I were to try using the public key to encrypt data, using the private key to decrypt would fail if using a symmetric encryption algorithm such as AES-GCM

The NIST post-quantum schemes mainly consist of KEMs and signature schemes due to the fact that quantum computers don't break all existing cryptography.
As per Daniel Bernstein :

...there is no justification for the leap
from “quantum computers destroy RSA and DSA and ECDSA” to “quantum
computers destroy cryptography.”

As such, there is less desire to replace AES than there is to replace RSA/DSA/ECDSA, or whatever is broken by quantum computers.
Meanwhile DJB's tone suggests he doesn't think it's a priority:

Evidently these unnamed “experts” believe—and Magiq would like you to
believe—that quantum computers will break AES, and dozens of other wellknown secret-key ciphers, and Merkle’s hash-tree signature system, and
McEliece’s hidden-Goppa-code encryption system, and Patarin’s HFEv− signature system, and NTRU, and all of the other cryptographic systems discussed in this book. Time will tell whether this belief was justified!


May it be possible that the trusted third party knows the parties' private keys in an "ideal model" of a Secure multiparty computation protocol? May it be possible that the trusted third party knows the parties' private keys in an “ideal model” of a Secure multiparty computation protocol?
I wonder if it may be possible that a trusted third party knows the private keys (e.g. the encryption's private key or the digital signature's private key) in an "ideal model" counterpart of a Secure MPC protocol.
The trusted third party may use such knowledge to simulate authenticated (and publicly verifiable) payments from one party to another, etc...

Yes.
Trusted party setup is just way to think about what the end goal of a particular MPC system is. So you may start with a party (lets call it the dealer) that sends it's private key to the trusted party, and then the trusted party uses it to commit a transaction.
Now replace the trusted party with a multi-party setup. The dealer here sends shares of its private key to each of the parties. The parties then can regenerate the private key or commit a transaction with it.


Baby step and giant step? When i see this problem,
 i think that it is similar to 'baby step, giant step' because of gauss symbol.

But in here, i don't know how to prove both (a) and (b).

What i have done is that $A= [p]$ or $A=[p]+1$. here $[p]$ is the lower integer version of gauss symbol.

Also, $$A=p^{1/2}$$ (when this is integer) or $$p^{1/2}<A<p^{1/2}+1$$ (when the square root is not an integer)

$(a)-$ Let $p$ be prime. Then $\sqrt{p}<A<\sqrt{p}+1 $, so $0<A^2-p<2\sqrt{p}+1$. This means that, prime divisor of $A^2-p$ is less than $3\sqrt{p}$.

Now try to solve $(b)$ for next $10$ points.


Problems on ANF equation? I tried to solve SBox as given in this link
I am trying to understand this paper SBox. In this on page no.4 the correct equation of given SBox is mentioned. I am not getting how to design ANF equation as given in paper.

Using the S-box package of SageMath used
S = SBox(1, 10, 4, 12, 6, 15, 3, 9, 2, 13, 11, 7, 5, 0, 8, 14);

f0 = S.component_function(1)
f1 = S.component_function(2)
f2 = S.component_function(4)
f3 = S.component_function(8)

print ( "y0 = ", f0.algebraic_normal_form())
print ( "y1 = ", f1.algebraic_normal_form())
print ( "y2 = ", f2.algebraic_normal_form())
print ( "y3 = ", f3.algebraic_normal_form())

Return a Boolean function corresponding to the component function $b\cdot S(x)$.

and the output
\begin{align}
y_0 &=  x_0 x_1 + x_0 + x_1 + x_2 + x_3 + 1\\
y_1 &=  x_0 x_1 + x_0 x_2 + x_0 + x_2 + x_3\\
y_2 &=  x_0 x_3 + x_1 x_2 x_3 + x_1 x_3 + x_1 + x_2\\
y_3 &=  x_0 x_2 x_3 + x_0 + x_1 x_3\\
\end{align}
The blow the result of the article
\begin{align}
s_0 &=  1 + a + b + ba + c + d \\
s_1 &=  a + ba + c + ca + d\\
s_2 &=  b + c + da + db + dcb\\
s_3 &=  a + bd + dca\\
\end{align}
And the result form Conchild code \begin{align}
y_0 &= 1 + x_0 + x_1 + x_0*x_1 + x_2 + x_3\\
y_1 &= x_0 + x_0*x_1 + x_2 + x_0*x_2 + x_3\\
y_2 &= x_1 + x_2 + x_0*x_3 + x_1*x_3 + x_1*x_2*x_3\\
y_3 &= x_0 + x_1*x_3 + x_0*x_2*x_3\\
\end{align}
Martin R. Albrecht provides another method with SageMath
from sage.crypto.sbox import SBox

S = SBox (1, 10, 4, 12, 6, 15, 3, 9, 2, 13, 11, 7, 5, 0, 8, 14)
P.<y0 ,y1 , y2 ,y3 ,x0 , x1 ,x2 ,x3 > = PolynomialRing ( GF (2) , order ='lex')
X = [x0 ,x1 ,x2 , x3 ]
Y = [y0 ,y1 ,y2 , y3 ]
S. polynomials (X=X , Y=Y , degree =3 , groebner = True )

The result is compatible with the article but the $y_i$'s reversed.
[y0 + x0*x1*x3 + x0*x2 + x3,
 y1 + x0*x1*x2 + x0*x2 + x0*x3 + x1 + x2,
 y2 + x0 + x1*x3 + x1 + x2*x3 + x3,
 y3 + x0 + x1 + x2*x3 + x2 + x3 + 1]


In finite field elliptical curve, is the addition of any two points on the curve guaranteed to land on the curve? I've been troubled by this, given any random number as the number of times we'll multiply a point by itself, will we always be guaranteed to land on the curve again? Is there a case where we'll have a miss?

Also, is the question to above not always true unless we are in finite fields defined by specific curves? Is this part of the reason why we need to choose specific curves?

Adding two points on a curve following the addition law will always give another point on the curve.  That's part of what it means for the curve to form a group.

The addition law is defined relative to a particular curve and a particular field.  For example, consider the field $\mathbb F_3$, i.e. the integers $\{0, 1, 2\}$ with arithmetic—addition and multiplication—performed modulo 3, and consider the curve $$E/\mathbb F_3 : x^2 + y^2 = 1 + 2 x^2 y^2.$$  The point $(1, 0)$ (i.e., $x = 1, y = 0$) is on this curve, which you can check by a simple calculation.  The point $(2, 0)$, however, is not.  (Exercise: List, for every possible $x, y \in \mathbb F_3$, whether $(x, y)$ is on the curve.  There are only nine of them!)  The addition law $$(x_0, y_0) + (x_1, y_1) = \left(\frac{x_0 y_1 + x_1 y_0}{1 + d x_0 x_1 y_0 y_1}, \frac{y_0 y_1 - x_0 x_1}{1 - d x_0 x_1 y_0 y_1}\right)$$ always gives another point on the curve.  For example, $(2, 1)$ is also on the curve, and $$(1, 0) + (2, 1) = \left(\frac{1 + 0}{1 + 0}, \frac{0 - 2}{1 - 0}\right) = \left(1, \frac{-2}{1}\right) = (1, 1),$$ which you can check by another simple calculation.

That addition law always works for the points $(x, y)$ on $E$ for $x, y \in \mathbb F_3$, but does not always work for every curve or every field.  For example, it does not work for $$E/\mathbb F_7 : x^2 + y^2 = 1 + 4 x^2 y^2$$ because $4 = 2\cdot 2$ is a quadratic residue in $\mathbb F_7$.  (Try it with $(1, 5)$ and $(4, 5)$—you'll get a denominator which is a multiple of 7, which is equivalent to zero in $\mathbb F_7$, which you can't divide by.)  Not every curve can even be written in this form, which is called Edwards form; for example, curves of prime order, such as NIST P-256, have no Edwards form.  Other forms of curves have different addition laws, which work on different subsets of points and in different cases.


Words in “index of coincidence” in relation to the Vigenère cipher I am trying to interpret the formula for index of coincidence from here…

I am not understanding $f_i$. How can I calculate $f_i$ in this context? Is this the appearance of single word like (a) in the whole sentence or what ? I am trying to solve it manually without using the mentioned website tool, but I am getting the wrong answer.

Here $f_i$ is simply the number of times the character $i$ appears in the ciphertext of length $N$ and where $Z$ is the alphabet size.

If you had ciphertext ADCXU ZMDYZ DXZUM and which was derived from English plaintext then $N=15$  and $f_A=1,f_B=0,f_C=1, f_D=3,\ldots, f_Z=2.$


Why do PKI schemes need security proofs? When it comes to designing new PKI-based key-exchange protocols, why are security proofs needed?

Without them, can we show a protocol's security? Does there exist a PKI-based key-exchange protocol that is secure without a security proof?

If you cannot provide even a basic proof of security, or a reduction of the protocol security to the underlying algorithms in use, you should assume the protocol is insecure.

Even with a security proof, a logical analysis of attacks against the protocol should be performed, as a proof may be limited to security against a limited amount of attacks, and in practice all attacks must be considered, even those that are uncommon or even impractical.


At what stage is DHE and RSA used during the SSL/TLS handshake? At what stage of the SSL/TLS handshake is the DHE and RSA used and what is the purpose of using a pre-master secret when you could just use RSA to exchange the symmetric key (i.e. AES) for further communications. I am confused how DHE, AES and RSA fuse into the SSL/TLS handshake process. Is there a handshake with purely RSA, purely DHE or both.

The SSL/TLS handshake consists of a series of messages which do keyexchange and (usually) authentication together. See rfc5246 or its predecessors or Wikipedia for details.
The handshake actually results in one "premaster secret" and one "master secret"
which is then used to derive multiple keys:
an encryption key for each direction (for an algorithm that may be AES or something else), an IV for each direction for suites that need it (which is all CBC suites in protocol versions before TLSv1.1, and some of the AEAD suites in TLSv1.2), and a HMAC key for each direction for suites that need it
(which is everything except the AEAD suites in TLSv1.2).
See How key materials are generated in SSL V3 from master secret
and What is the purpose of four different secrets shared by client and server in SSL/TLS? .

The original, and still a common, keyexchange method is RSA, sometimes emphasized as 'plain' RSA or kRSA. The server sends a certificate containing an RSA (public)key; the client validates
the cert and uses the publickey to RSA encrypt the random premaster secret.
The server proves correct decryption (and is implicitly authenticated) with the Finished message.
The server can optionally request client authentication; if so the client
sends its own cert and uses its matching privatekey to sign a partial transcript, which the server validates and verifies, but this is rarely used. Except possibly the client auth, this is 'pure' RSA.

DHE (DH in ephemeral mode) is used in conjunction with a signing certificate, which can be either RSA or DSA.
The server sends its cert which client validates, and also its DH group and ephemeral publickey signed under its cert; client generates its ephemeral key in the same group
and sends that, plus its cert and signature if client authentication is used.

There is also a method to use DH keyagreement without certificates and authentication, which is in effect ephemeral, but SSL/TLS doesn't call it that, it calls it DH-anon instead. This is usually a bad idea; many people imagine only passive eavesdroppers
and think they only need encryption, but in today's internet active attacks of many kinds are widespread and if you don't use authentication you probably aren't secure.
You could view this as 'pure' DHE even though it isn't called that.

There are elliptic-curve variants ECDHE (ephemeral, RSA or ECDSA signing} and ECDH-anon.
The handshake sequence, and security properties, are the same, only
the actual crypto computations are different. These are technically optional
but in fact nowadays widely implemented and becoming more popular to use.

And there are 'static' methods (DH and ECDH, no E or anon) which use
long-term [EC]DH keys instead of ephemeral ones. This requires certs for
the static keys (and preagreement on the group or curve) which is less
convenient, especially for classic (non-elliptic) DH, although TLSv1.3 is planned to add standardized DH groups that might change this, and these methods don't seem to be used at all on the public net.

Finally, there are some methods that don't use publickeys at all, including
Pre-Shared Key (PSK) and Secure Remote Password (SRP). These basically work only in
a private net (or virtual one) and aren't seen on the public net.

AES or other data cipher like 3DES or RC4 is not used in the handshake.
It is used for data after the handshake.

Contrary to @mirabilos for [EC]DHE methods the ephemeral key material IS
signed under the server cert and the client cert if client auth used.
Not for the -anon methods, which are designed not to authenticate.


Pairing-friendly curves in small characteristic fields There are several well-known techniques to generate pairing-friendly curves of degrees 1 to 36 on prime fields GF(p): Cocks-Pinch, MNT, Brezing-Weng, and several others.

In extension fields GF(p^n), however, one is confined to supersingular curves. In characteristic 2, embedding degrees are <= 4, and in characteristic 3 they are <= 6. In general, they are <= 2.

The question is: is there any known method to generate ordinary pairing-friendly curves over small characteristic fields, with a reasonable (say, 3-20) embedding degree?

To my knowledge the answer is no.

Informally, the only known method to construct pairing friendly curve is the CM method, which allows you to find an elliptic curve with strong constraints on its number of points if you put few constraints on the cardinal of the base field, or conversely a curve over a very constrained base field with only little constraints on its number of points.

(If you're interested in more precise statements and explicit examples, I suggest looking at Lay and Zimmer, Constructing elliptic curves with given group order over large finite fields, which despite its title covers both aspects. Article behind a pay wall unfortunately.)

This works well to find pairing-friendly curves in large characteristic because you have plenty of room to let the cardinal of the base field vary. But it doesn't work well at all over small characteristic fields, because you put both huge constraints on the cardinal of the base field (it has to be a power of the characteristic) and on the number of points on the curve (to achieve a small embedding degree).

In fact, I'd be curious to see even a single example of an ordinary curve with small embedding degree over a not too large binary field, like $\mathbb{F}_{2^{31}}$ say.

Note that this problem is entirely unrelated with the question of constructing ordinary pairing-friendly curves of higher genus over large prime fields, which Freeman's article mentioned above addresses.


MD5 update functions In the hashlib module in python is a function called m.update() where m is a hashlib.md5 object. My question, actually not specific to python, is how does this function work, such that:

m = hashlib.md5()
m.update("hello")
m.update(" world")

which is the same as if I would have done:

a.hashlib.md5()
a.update("hello world")

How does the math work to explain this?

It is an object, not a function. The difference is important: the thing you get with m = hashlib.md5() is a structure in memory that has an internal state. Each update() call updates that state (hence the name).

You can imagine the object has a kind of box. Each update() call accumulates input bytes in that box. When you want to obtain the hash value, the MD5 mathematical function is applied to the complete box contents. That way, it does not matter whether you put the bytes in the box as one or two or seventeen successive calls;  what matters is that you ultimately sent all the bytes in the box.

Technically, MD5 processes input data by blocks of 512 bits (64 bytes) and maintains a running state consisting of 128 bytes (16 bytes) along with a counter (the number of bytes that were hashed is used at the end of the function evaluation). Thus, a practical MD5 implementation will indeed contain a "box" (usually called a "buffer") that can accumulate up to 64 bytes; whenever 64 bytes have been accumulated, they are processed as per the MD5 specification, and the box is emptied. That way, the object remains small in RAM, even if you hash gigabytes of data.

Reading the specification to implement your own MD5 code is a very nice programming exercise, that is very enlightening. I recommend that you try it.


What is difference between an identification scheme and a digital signature scheme? It seems we can use every identification scheme to sign and verify a message and vice versa. I am right or not? What is difference between an identification scheme and a digital signature scheme?

Huh, I was just reading about this.
Quoting [1]:

Identification schemes: A can prove to B that he is A, but B cannot
prove to someone
Signature schemes: A can prove to B that he is A, but
B cannot prove even to himself
The distinction between identification and signature schemes is
subtle, and manifests itself mainly when the proof is interactive and
the verifier later wants to prove its existence to a judge: In
identification schemes B can create a credible transcript of an
imaginary communication by carefully choosing both the questions and
the answers in the dialog, while in signature schemes only real
communication with A could generate a credible transcript. However, in
many commercial and military applications the main problem is to
detect forgeries in real time and to deny the service, access or
response that the forger wants. In these cases the transcript and
judge are irrelevant, and the two types of schemes can be used
interchangeably.

[1]: Fiat, A., & Shamir, A. (1986, August). How to prove yourself: Practical solutions to identification and signature problems. In Conference on the Theory and Application of Cryptographic Techniques (pp. 186-194). Springer, Berlin, Heidelberg.