Are NIST's changes to Keccak/SHA-3 problematic? NIST is working on standardizing SHA-3.  They have selected Keccak as the basis for SHA-3, and they plan to make some small changes to it; the result (with NIST's changes) will be standardized as SHA-3.

A blog post from the CDT raises concerns over those changes.  Two specific concerns were mentioned:

The security level is "reduced": instead of offering 224-bit, 256-bit, 384-bit, and 512-bit versions of the hash (as found in the Keccak submission), the SHA-3 standard will only offer 128-bit and 256-bit versions.
Some of the internals of the algorithm have been tweaked by NIST.

My question: Are these criticisms of SHA-3 valid?  Are they something to worry about?

(To be clear: in the two points above, I'm just repeating what the blog post said.  I'm not trying to claim that those two criticisms are valid -- indeed, whether they are fair criticisms or not is exactly what I want to know.)

NIST gives the rationale for these changes in their presentation at CHES 2013.

I wonder if the first criticism might be a misunderstanding; is it an accurate statement of NIST's plans?  (See also Why restricting SHA3 to have only two possible capacities?.)  The second criticism might be more interesting.  Is there any technical merit to the second criticism?  Is there any reason to distrust the plans for SHA-3, or to suspect shenanigans?  Are these changes to Keccak more likely to make it more secure, or less secure?

I do worry, but not for the resistance of SHA-3; I worry for its acceptance.

Technically, what NIST wants to do is sound. They do want to somehow "break" a traditional rule, which is that a hash function with an output of n bits ought to resist collisions with strength 2n/2, and preimages (first and second) with strength 2n. Instead, NIST wants harmonized security levels at 2n/2. Indeed, 128-bit resistance to preimages are more than enough for most practical purposes. On the NIST mailing-list for the SHA-3 competition, John Daemen himself has recently (this morning) argued that the proposed modification on SHA-3 will not only retain 128-bit protection against preimages, but it will even ensure 128-bit protection against multi-target preimages, i.e. something better than what a "classic" hash function with a 128-bit output would offer.

The upside of "harmonizing" the security levels is that it is done, in the case of Keccak, by lowering the internal "capacity", and this increases performance (software performance is a sore point of Keccak in general, in that it is not really faster than SHA-2).

Acceptance, however, is something else altogether. In many cases (unfortunately, in most cases), decision to use or not use a specific algorithm in a given system will be taken by people with a, let's say, less acute grasp of cryptography than the crowd of cryptographers. Most don't imagine that there is a difference between collisions and preimages. What happens on their heads is not something like "mmh, NIST made a trade-off between academical security and performance, but a sound one, approved by other cryptographers, so that's good". Rather, it goes along the lines of "OMG they changed the algorithm now it's all backdoored !". And they finally decide to use a custom scheme, e.g. a XOR of MD4 with MurmurHash, or anything else equally dumb.

In my experience, systems which use cryptography don't get broken because of a well-informed trade-off between performance. They get broken because a good algorithm was misused, or simply not used, because someone got paranoid and/or creative, and used a custom weak scheme instead.

One of the reasons why AES was widely adopted is that Rijndael was unchanged. NIST did not change the slightest bit in the whole algorithm; they just took it as is, i.e. as it was specified by the non-American inventors and also as it was analysed by all the other non-American cryptographers during the competition.

If NIST wants the widest possible acceptance of SHA-3, then they should keep Keccak unchanged from its "third round" specification. And by "unchanged" I mean "really unchanged". This is not just about the internal "capacity", but also the padding and all the other bits.

Acceptance at all costs is not necessarily a worthy goal; maybe NIST considers that having a technically good and fast (or not too slow) algorithm is more important than catering to the crowd of ill-informed paranoid managers who make dumb technical decisions. But at least it is a question worth asking.


HKDF vs TLS PRF. Which of the one is better? Which of the one (HKDF or TLS1.1+ PRF) is more secure and why?

It is unclear if you wanted to compare TLS 1.1 PRF or TLS 1.2 PRF. Different TLS versions have different PRFs. Assuming you meant TLS 1.1 PRF although you linked TLS 1.2 RFC.

TLS 1.1 PRF

Short: HKDF is commonly a better choice than TLS 1.1 PRF, but not always.

Consider these aspects:

HKDF is a generic construct.
HKDF is extract and expand.
TLS1.1 PRF is just extract or expand.
TLS1.1 PRF is intended for TLS protocol.
HKDF can be used with hash functions chosen by the user.
TLS1.1 PRF uses MD5 and SHA-1 hashes. Thus, it does not allow using stronger hash functions.
TLS1.1 PRF uses two hash functions which causes extra complexity and complicates security analysis.
TLS1.2 defined new PRF function to use. (So for purposes of TLS, TLS1.1 PRF has gotten deprecated).

TLS1.1 PRF has been analyzed in Hash function combiners in TLS and SSL.
Based on this analysis, HKDF, when used with a strong hash function is likely stronger than TLS1.1 PRF.

TLS1.2 PRF

Comparing HKDF with TLS 1.2's PRF.

NIST SP 800-108 Recommendation for Key Derivation Functions defines various ways to construct Key Derivation Function:
- Counter Mode
- Feedback Mode
- Double-Pipeline Iteration Mode

For NIST, all these approaches are equally acceptable. The Feedback Mode matches HKDF's Expand phase. The Double-Pipeline Iteration Mode matches TLS 1.2 PRF. Thus we could assume, that TLS 1.2 PRF could be considered to be similar to HKDF's Expand phase if used with the same hash function underlying the hmac.

Purpose of HKDF's extract phase is quoted from RFC 5869:

In many applications, the input keying material is not necessarily
distributed uniformly, and the attacker may have some partial
knowledge about it (for example, a Diffie-Hellman value computed by a
key exchange protocol) or even partial control of it (as in some
entropy-gathering applications).  Thus, the goal of the "extract"
stage is to "concentrate" the possibly dispersed entropy of the input
keying material into a short, but cryptographically strong,
pseudorandom key.  In some applications, the input may already be a
good pseudorandom key; in these cases, the "extract" stage is not
necessary, and the "expand" part can be used alone.

For applications where extract phase is beneficial (distribution of input keying material is not uniform), HKDF is certainly the way to go.

For other uses, where expand phase is used alone, any one of these two (or in some cases counter mode) from NIST SP 800-108 could be used. (Note: If you use TLS 1.2 PRF outside context of TLS protocol, maybe better define the function in terms of NIST SP 800-108, instead of TLS 1.2 PRF from the RFC).

Short summary:

If you need extract use HKDF.
If you need expand only, use functions from NIST SP 800-108.
Generally you should not use TLS 1.1 PRF except for compatibility with TLS protocol.


Why is this authenticated Diffie–Hellman key exchange insecure? I was searching for the information on authenticated Diffie–Hellman key exchange and found these slides. The author says, “Remember
$$A\to B: (A, g^x, \operatorname{SIG}_a((g^x, B)))$$
$$B\to A: (B, g^y, \operatorname{SIG}_b((g^y, A)))$$
insecurity”. I fixed the mistake with $A\to B$, replaced public keys with secret ones in the signature function and added sender identifiers. I do not understand why this protocol is insecure, and I can't find anything about this protocol. I understand it as follows. Upon receiving the first message $(C, X, s)$, Bob aborts if $s$ is not a signature of $(X, B)$ by $C$, otherwise generates $y$, sends $(B, g^y, \operatorname{SIG}_b((g^y, A)))$ and associates the session key $X^y$ with $C$. Upon receiving the second  message $(C, Y, s)$, Alice aborts if $s$ is not a signature of $(Y, A)$ by $C$ or $C\neq B$, otherwise associates $Y^x$ with $C$ (Bob).
I have been unsuccessfully trying to implement the attack described in “3.1 BADH and the identity-misbinding attack: A motivating example” in “SIGMA: the ‘SIGn-and-MAc’ Approach to Authenticated Diffie-Hellman and its Use in the IKE Protocols” by Hugo Krawczyk. This and related papers are the only material on the subject I could find. Suppose that Darth posesses a secret key $d$ and the corresponding public key $D$. Since Alice initiates the session, Alice will think that she is talking to Bob anyway. If Darth replaces the first message with $(D, g^x, \operatorname{SIG}_d((g^x, B)))$, Bob will send $(B, g^y, \operatorname{SIG}_b((g^y, D)))$. I do not see how Darth can persuade Alice to start the session using $g^y$ since Darth does not have $\operatorname{SIG}_b((g^y, A))$.

My guess is that when it is written approximately

Can we really have a non-replayable 2-msg protocol?
□ Remember (the question's protocol) insecurity

the author is thinking about an attacker capturing the first message of the exchange $(A, g^x, \operatorname{SIG}_a((g^x, B)))$ and using a replay of that to impersonate Alice.
There are two variants:

Declaring victory just because Bob thinks (and the logs of its machine show) that Alice connected again, when she did not.
Further, if Alice leaked the $x$ she used in the past, that allows the attacker to get the new shared secret by doing just as Alice normally does, and fully impersonate Alice.


RSA Encryption that only my family could decrypt I was doing some thinking about what would happen to my computer and passwords if I fell off the earth tomorrow. I wanted to have a message that only they would have the ability to decrypt and I wanted it to be very strong.
Lets say they are the only ones who know our first dog's name, Scout.
How could the decrypt a say RSA-encrypted message using this information? I was thinking they could add it to the end of the private key and but I don't think that is how RSA works. How would you approach this task?

I was thinking they could add it to the end of the private key and but I don't think that is how RSA works.

Indeed it is not.

How could the decrypt a say RSA-encrypted message using this information?

One solution is to encrypt a private key with the password and encrypt the message under that private key. This also allows you to add new messages / remove old ones w/o having to recover the private key first. Of course if you'd always do that anyways, you could also just forgoe the asymmetric encryption and just use plain password-based encryption.
The cleaner solution would of course be to encrypt the message under everyone's public key, but given that it sounds like the family is not so much up to tech, a simpler solution like the above one will probably be better.
Of course note that the security of passwords like a dog name is very questionable and for a proper security level one would probably have to combine a dozen or so such information pieces (assuming that every question has ~2000 equiprobable answers).

[What] [...] would be the easiest [way] for someone with limited computer knowledge to decrypt a RSA encrypted message?

Using a standard tool and writing a detailed guide (ideally with pictures) on how to use it. A GUI is probably preferred as quite a few people are scared of command lines.


Supersingular isogeny Diffie–Hellman key exchange (SIDH) Library Support AES-256? In the version 3.0 of the SIDH library, it implements SIDH/SIKEp503 (AES-128) and SIDH/SIKEp751 (AES-192) only.

Are there plans to incorporate AES-256?

Nathan Aw

Neither implementation actually incorporates or uses AES of any keysize, rather the primes used provide a security about 1/6 of their bit size, resulting in a security level of 83 bits for SIDH/SIKEp503 and 125 bits for SIDH/SIKEp751 against quantum attacks, and 126 bits and 188 bits against classical attacks, respectively.

Because of this, you are not limited to the recommended cipher bit size, or even to AES. You can use any secure block cipher with an appropriate security level and mode.

Since AES provides a post-quantum security of half its key size, AES-256 is actually better matched to SIDH/SIKEp751. Against classical attacks, this results in 188 bits of security, and against quantum attacks, 125 bits.


Encrypting small values with RSA private key I'm looking for best practices when it comes to encrypting small (< 128 bytes) amounts of data with the RSA private key. Signing it would make the resulting payload too large.

In any public key system, you don't encrypt with private key. You encrypt with public key, or sign with private key.

If your goal is signing (resp. encrypting) one small value with the RSA private (resp. public) key, keeping the signature small: forget about it, that's not directly possible. Under RSA, a cryptogram is always of size at least comparable to the key. You need another public key scheme. Edit: standard RSA signatures schemes have signatures about as wide as the public modulus; a state of the art RSA variant can about half that.

If you want to encrypt several small values with RSA, do that with a random secret key drawn for that purpose, and a symmetric cipher; and send the secret key, RSA-encrypted with the public key, using a proper padding scheme like OAEP.

If you want to sign several small values with RSA, concatenate them (each with length indication unless the lengths are agreed in advance), then sign the aggregate using a proper RSA signature scheme like PKCS#1 PSS. If you want to send the small values along and care about the total size, use a signature scheme with message recovery, such as ISO/IEC 9796-2 (but beware that the first of the three schemes in this standard, still the most used, has some flaws if the opponent can obtain the signature of enough chosen messages).


PPT eavesdroper able to output $m_{0}$ and $m_{1}$ of different lengths I've read the following two questions and their answers:

Messages of different lengths and one-time computationally-secret
Why is a non fixed-length encryption scheme worse than a fixed-length one?

I am still not convinced of what is the actual strategy of the adversary $A$. I understand that in case that the encryption scheme cipher depends on the length of the message to encrypt then $A$ could output $m_{0}$, $m_{1}$ of different lengths and would be able to tell which one was encrypted by the length of $Enc(m_{b})$ (where $b\gets\{0,1\}$).

Now, who promises that $|Enc(m)|$ depends on $|m|$?
Isn't it possible that $|Enc(m_{0})|=|Enc(m_{1})|$?

Actually, every encryption algorithm has an associated message space which defines the maximum message size which can be encrypted and the ciphertext is always of size of the associated ciphertext space. If the message at hand is larger than the message space of the encryption algorithm, you have to encrypt the message "block by block" (where a block can also be a bit. For block ciphers there are various ways to realise this, e.g., CBC (see here), for stream ciphers viewing the message space as being a bit it should be obvious how the ciphertext size depends on the message size and for asymmetric schemes in practice this is typically not required since you use hybrid encryption and thus always only encrypt a single "block".

Now for achieving the weakest reasonable security, i.e., indistinguishability under chosen plaintext attacks (IND-CPA) where i'm talking about public key encryption schemes here (actually the argument is the same for one-time computationally-secret as in your referenced question), an adversary providing two challenge messages $m_0$ and $m_1$ and given back the ciphertext $c_b$ has to figure out which one has been encrypted (i.e., determine whether $b=0$ or $b=1$) (here it does not really matter that the adversary can then afterwards ask an encryption oracle for encryptions of messages different from the challenge messages). Clearly, if one of the challenge messages is out of the message space and the other is larger, i.e., requires $>1$ blocks, then it is trivial to distinguish the two ciphertexts.

Consequently, in the attack game one requires that if one message is larger, the second is padded to have the same length as the first to rule out this trivial attack. Then, if both messages are of the same length (and padded) both ciphertexts will be of the same length and then the adversary has to apply a non-trivial strategy to figure out which message has been encrypted as a challenge.

Edit: PrivK Game:

Ok, the PrivK game is defined as follows (I took the definition from this question):

An (efficient secret-key) encryption scheme $(Gen,Enc,Dec)$ is one-time computationally-secret if for any PPT adversary $\cal A$ it holds that $Pr[PrivK_{\cal A}^{eav}(n)=1]−1/2$ is negligible function, where $PrivK_{\cal A}^{eav}(n)$ denotes the output of the following experiment:

(a) The adversary $\cal A$ on input $1^n$ outputs a pair of messages $m_0,m_1$.

(b) Let $k\leftarrow Gen(1^n)$ and let $b\in \{0,1\}$ be chosen uniformly at random. Then a ciphertext $c\leftarrow Enc_k(m_b)$ is computed and given to $\cal A$.

(c) $\cal A$ on input $c$ outputs a bit $b'$.

(d) The output of the experiment is $1$ if $b'=b$ and $0$ otherwise.

Let us assume that we have a block cipher with block size $k$ bits and let the adversary now choose a message $m_0\in \{0,1\}^k$ and $m_1 \in \{0,1\}^{2k}$, i.e., message $m_0$ has one block and message $m_1$ has two blocks. Consequently, $c_0=Enc_k(m_0)$ will be of size $k$ bits and $c_1=Enc_k(m_1)$ will be of size $2k$ bits. Hence, the adversary will always output $1$ and thus $Pr[PrivK_{\cal A}^{eav}(n)=1]=1$ and $Pr[PrivK_{\cal A}^{eav}(n)=1]-1/2$ is $1/2$, which is non negligible. Consequently, we need to require that $|m_0|=|m_1|$ to rule out this strategy for $\cal A$.


Is it guaranteed that all possible random numbers can be produced? As far as I know PRGs get an input (seed) and generate a larger output value than the input. Therefore is it possible that some outputs will never be generated? based on the fact that input is smaller than the output.

PRGs get an input (seed) and generates a larger output value than the input.

Indeed. The standard definition of a PRG makes it a deterministic polynomial-time algorithm with input a seed in $\{0,1\}^n$ and output in $\{0,1\}^{\ell(n)}$ with $\forall n, \ell(n)>n$; and an other characteristic (pseudorandomness).

is it possible that some outputs will never be generated?

It's not only possible, it's certain, for all $n$. To prove this, we only need to count the possible inputs: there are $2^n$; and the number of outputs: there are $2^{\ell(n)}$. The condition $\ell(n)>n\ge 0$ implies $2^{\ell(n)}>2^n$. And since the algorithm is deterministic, there can't be more possible outputs than possible inputs.

Is it guaranteed that all possible random numbers can be produced?

Also yes, but in another sense.
If we truncate the output into $\lfloor\ell(n)/k\rfloor$ bitstring of $k$ bits, then it becomes possible that each one of the $2^k$ potential output bitstrings of $k$ bits is reached for some input when $n$ grows high enough. In fact, pseudorandomness implies that holds¹. Every possible output of any fixed size $k$ bit is reached¹ for large‑enough $n$ and when we consider all the $2^n$ possible inputs.
Now we only need to choose $k$ such that all the random numbers thought are in $[0,2^k)$, and then all possible random numbers thought are¹ produced.

¹ except perhaps for vanishingly few $n$


How to prove that someone encrypted a specific (large) chunk of data Alice encrypts her data with HER secret key. Then she sends the encrypted data to Bob who should encrypt it with HIS secret key.

Caroline should then eventually get this double encrypted data.
Caroline only wants to receive pseudo-random (looking) data which would only be decryptable for her if Alice and Bob BOTH tell her their secret key. She wants to be able to use this fact in court in case she and [Alice XOR Bob] get accused of deliberately saving and/or distributing intellectual property illegally.
Caroline therefore wants to be sure that Bob really takes the encrypted data of Alice, encrypts it with HIS secret key and then sends it to her.
How can that be achieved?
Alice and Bob are allowed to use different encryption algorithms.

I suppose AES is not suitable for this task.
I hope I was somehow able to express what I want in a comprehensible way.
I know, my English is bad.

I may be interpreting your question incorrectly, but it sounds to me like you are asking if Caroline can prove (in court or whatever) that she can only gain access to some secret $S$ if both Alice and Bob collaborate in revealing it to her.  Unfortunately as you have currently set up the question, I don't think that is possible, because your question establishes that Alice knows the secret $S$ before any encryption is applied (it's "her data", as you put it).  Hence, it is always possible for Alice to simply tell Caroline $S$, regardless of whether Bob collaborates.

But, if we modify the set-up a bit, it is possible to prove what you want.  We need to assume that neither Alice nor Bob knows $S$, and in addition we need a trusted third party and a secret sharing scheme.  Only the trusted third party, Tim, starts off knowing $S$, and he can be trusted to a) not leak any information about $S$ to anyone at any point, and b) to reliably carry out the following three steps:

Tim generates a pad $P$ - a random string of bits equal to the length of $S$.
Tim establishes a secure channel with Alice (using e.g. secure public key exchange and PKI methods to prevent Man In the Middle attacks), and sends her the string $P \oplus S$.
Tim similarly establishes a different secure channel with Bob, and securely sends him $P$.

At this point, Tim has split the secret into two 'shares', and Alice and Bob only know what their own share looks like (i.e. random nonsense).

Alice and Bob then each encrypt their own share using authenticated encryption (e.g. AES-GCM) and their own secret keys.
Alice and Bob now send Caroline the encrypted shares.

This way, no one (aside from Tim) can know what $S$ is unless both Alice and Bob  reveal their shares (e.g. by sharing their keys with Caroline).  Knowing only one share gives you zero information about $S$ (besides the length), and as such if either Bob or Alice don't reveal their share then $S$ is safe.

As to any concerns about ensuring that Alice and Bob do their part (i.e. properly encrypt their shares) and don't simply forward their shares unencrypted to Caroline, I would note that simply forwarding the unencrypted shares to Caroline is equivalent to encrypting the shares but then revealing the keys to her -- so long as either Alice or Bob does their part properly Caroline cannot know $S$. It takes collaborative effort / incompetence by both Alice and Bob for $S$ to be revealed. If we cannot trust that at least one of the two will keep their key secret and properly run their part of the protocol then no scheme will succeed (so my scheme is not unique in that respect). But given my described scheme, one person doing their part properly is sufficient to keep Caroline provably in the dark.


Sending the nonce in ChachaPoly1305 with the ciphertext I am trying to implement a ChachaPoly1305 encryption with authentication scheme over a network. I am using a counter to derive the nonce as suggested by the rfc.

Is it secure to send the nonce over the network along with the ciphertext? If not then why?

Yes, it is acceptable to send the nonce over the network when using ChaChaPoly1305.  The nonce needs to be unique for every message encrypted with the same key, but the nonce does not need to be secret.

However, the RFC referenced in the question take a different approach.  It does not suggest using a counter.  That RFC uses information from the protocol that is available to both parties to construct the nonce.  This allows a unique nonce to be constructed without additional protocol overhead and without requiring the sender to keep track of the counter separately.  It does not harm the security of ChaChaPoly1305 if the protocol fields used to construct the nonce are sent in the clear.


How is EdDSA different from ECDSA with a custom curve? I just found this draft/informal IETF specification: Alternative Elliptic Curve Representation:

This document specifies how to represent Montgomery curves and (twisted) Edwards curves as curves in short-Weierstrass form and illustrates how this can be used to implement elliptic curve computations using existing implementations that already implement, e.g., ECDSA and ECDH using NIST prime curves.

This triggered my curiosity as I thought that ECDSA and EdDSA had many more differences than just different curves.
From what I understand, Edwards curves can be expressed in the Weierstrass form.
How is EdDSA different from using ECDSA with an Edwards curve (e.g., Curve25519) converted to a Weierstrass curve? I am mostly interested in functional aspects rather than possible optimization(s) due to curve parameters.
Related questions: #1, #2

EdDSA is not ECDSA over a different curve. Rather, it is a type of Schnorr signature. Indeed the name is very confusing, and I'm pretty sure that it was chosen in order to give this impression, since Schnorr is less well known.
Schnorr is essentially a zero-knowledge proof of knowledge of the discrete log of the public key, obtained via the Fiat-Shamir paradigm applied to the classic Schnorr Sigma protocol.
ECDSA is a completely different signature scheme, which was designed specifically to bypass Schnorr's patent (at least, this is the understanding in the field).


Pollard’s Rho Method I can't get my head around  Pollard’s Rho Method for solving discrate log problem

I have read in a book:

  The basic idea is to pseudorandomly generate group elements of the
  form α^i · β^j

So,what are i and j

  We continue until we obtain a collision of two elements, i.e., until
  we have
  α^i1 · β^j1 = α^i2 · β^j2

Why does finding a collision mean that we have solved the problem??

I understand Pollard’s Rho Method for factorization ,but I can't see how it's similar to Pollard’s Rho Method for solving discrate log

Why does finding a collision mean that we have solved the problem?

If we find a collision:

$\alpha^{i1} \cdot \beta^{j1} = \alpha^{i2} \cdot \beta^{j2}$

then we know that:

$\alpha^{i1-i2} = \beta^{j2-j1}$

And so, if we know the order of the group (which we generally do), then we can compute $({i1-i2})^{-1}$, and so, we have:

$\alpha = \beta^{(j2-j1) \cdot ({i1-i2})^{-1}}$

Tada, we're done.

  I understand Pollard’s Rho Method for factorization ,but I can't see how it's similar to Pollard’s Rho Method for solving discrate log

Actually, the similarity isn't in what you do when you find a collision, it's a clever way of searching for collisions without using a huge amount of memory.

Here's that idea behind the Rho method: if we designate $F^n(x)$ as the function $F$ iterated $n$ times, for example, $F^4(x) = F(F(F(F(x))))$, and $F$ as a finite range of size $\lambda$, then $F^n(x) = F^{2n}(x)$ for some $n$.  In addition, if $F$ is a random function, then $n$ will (with good probability) be $O(\sqrt{\lambda})$.  This allows us to search for a collision with a small amount of memory (and at a constant cost factor over more obvious techniques that do use a table for $F$ values).


Is ElGamal encryption still secure if the randomness is known to be even? In ElGamal encryption $(g^r, g^mg^{kr})$, if the randomness $r$ is always chosen from even numbers, and the attacker knows about this, is it still provable secure?

Suppose that computations are done in $\mathbb{F}_p^*$ for some prime $p$.  Let $c = g^m g^{kr} \bmod p$.  If $r$ is even then $g^{kr}$ is a square modulo $p$.  As a consequence, assuming that $g$ is a non-square modulo $p$, the Legendre symbol of $c$ modulo $p$ will leak the least significant bit of $m$: if $c^{(p-1)/2} \equiv 1 \bmod p$ then $m \bmod 2 = 0$; otherwise $m \bmod 2 = 1$.

Remark  If $g$ is a generator of large prime order $q$ (as should be the case for a proper implementation of ElGamal-like encryption), choosing even values for random $r$ should not help an adversary.  To see it, observe that (1) $g$ and $h := g^2 \bmod p$ generate the same group of order $q$, and (2) letting $M = g^m$ the corresponding ciphertext $(g^r, M \cdot g^{kr})$ can be rewritten as $(h^{r'}, M \cdot h^{kr'})$ where $r' = r/2 \pmod q$.

However, if $r$ is chosen at random as an even integer in $[0, q)$ then one bit of randomness is lost.


How do you find a cheater in Shamir Secret Sharing? If there are 4 people involved, and every two of them should be able to know the secret (the polynomial is just a line) and you are given $f(x)$ and $x$ for each of those people, and you know one of them is a cheater, how do you find the cheater?

Shamir's secret-sharing scheme has $n$ shares of a secret.  The shares are of the form $(x_0,f(x_0)), (x_1,f(x_1)), \ldots , (x_{n-1},f(x_{n-1}))$ where the $x_i$ are $n$
distinct nonzero elements of a finite field $\mathbb F$, and $f(x)$ is a polynomial of
degree $k-1$ with coefficients in $\mathbb F$. One coefficient, say $f_0$, of
$f(x)$ is the secret being shared and the remaining $k-1$ coefficients are chosen at random.  Note that the while the $i$-th share is constructed as $(x_i,f(x_i))$,
what the owner of the $i$-th share  sees is just a pair $(x_i,y_i)$ of
elements of $\mathbb F$, that is, while the owner knows that $y_i = f(x_i)$,
the owner has no other knowledge about $f$.

Given any set of $k$ shares $\{(x_{i_j},y_{i_j}) \colon 1 \leq j \leq k\}$,
there is a unique polynomial $g(x)$ of at most degree $k-1$ that interpolates through these $k$ points, that is, enjoys the property $g(x_{i_j}) = y_{i_j}$
for $1 \leq j \leq k$, and
this polynomial can be found, for example, through Lagrange interpolation.
Since $f(x)$ is of degree $k-1$ (or less if the random choice of $f_{k-1}$
resulted in $f_{k-1}=0$) and also has the property that $f(x_{i_j}) = y_{i_j}$
for $1 \leq j \leq k$, it follows that the $g(x)$ that has been interpolated
is the same as $f(x)$, and thus $g_0$ is the secret.  If fewer than $k$ shares
are available, the $g(x)$ that is recovered is not the same as $f(x)$.

If $m > k$ shares are available, we can interpolate through any $k$
of them and recover the secret.  For the application on hand, if it
is known that there is one (or at most one) cheater, and the
cheater's share  may have the wrong value for $x_i$ or $y_i$
or both, proceed as follows.

If two shares are identical, one of the two shares belongs
to the cheater but it is not possible to
determine who is the cheater. Fortunately, the secret is
recoverable if at least $k+1$ shares are available (that is,
$k$ distinct correct shares are available).  Of course, in
a different scenario, the reconstructor may know the identity
of each share owner, and so know that the $j$-th owner should
not be "turning in" a share in which the first symbol is $x_i$,
and thereby identify the cheater right away.
If there are two shares $(x_i,y_i)$ and $(x_i,y_j)$, then
one of them belongs to the cheater.  If $m \geq k+2$, interpolate
through a set of $k$ shares excluding these two to recover $f(x)$.
Calculate $f(x_i)$ and check which of the two possible cheater
shares matches $(x_i,f(x_i))$: the other belongs to the cheater.
Again, in the different scenario,  $(x_i,y_j)$ could be identified
right away as the cheater's share since the $j$-th owner should not
be turning in a share with $x_i$.
If all $m \geq k+2$ shares have different (and correct)
$x_i$ values, interpolate
through the $\binom{m}{k}$ different subsets of $k$ shares.
$\binom{m-1}{k}$ of these subsets will not contain the cheater's
share and all these interpolations will recover the same $g(x) = f(x)$.
The other interpolations will be through the cheater's share and
will give different interpolating polynomials.  It can be shown
that fewer than $\binom{m-1}{k}$ of these interpolations can
result in the same (but incorrect) $\hat{g}(x)$, that is,
in the $\binom{m}{k}$ interpolating polynomials resulting from
the $\binom{m}{k}$ different subsets, the correct polynomial
$f(x)$ will occur most often (win by a plurality but not
necessarily a majority).  Having found $f(x)$, simply reconstruct
the $m$ shares $(x_i,f(x_i))$ and compare to the ones "turned in"
to identify the cheater.  Alternatively, the union of the
$\binom{m-1}{k}$ subsets of shares that gave $g(x) = f(x)$
is the set of $m-1$ correct shares, and the complement is the
unique cheater's share.

More generally, if there can be as many as $t$ cheaters
it can be shown that the secret can be recovered and
the cheaters identified if $k+2t$ shares are available for
reconstruction.  Note that as many as $t$ of these $k+2t$
shares might be cheaters' shares.  Put another way, if
there can be as many as $t$ cheaters, we need at least
$k+t$ honest shares available (in addition to the $t$
possible cheaters) to be able to recover the secret and
identify the cheaters.

The proofs of assertions about plurality can be found
in the paper I.S. Reed and G. Solomon, "Polynomial
codes over certain finite fields,"  SIAM J. Appl. Math.,
v. 8, pp.300-304, 1960.  The original application of
Reed-Solomon codes to secret sharing (and suggestions
for more efficient recovery than multiple Lagrange interpolations)
can be found in R.J. McEliece and D.V. Sarwate, On sharing
secrets and Reed-Solomon codes, Communications of the ACM,
v. 24, Issue 9, Sep 1981.


Are commutative digital signature possible? Say we have a message $m$. Signer $S^1$ will sign this message using his digital signature to produce:

$$\operatorname{Sign}_{S^1}(m)$$

Now, say another signer $S^2$ wants to sign the output of the previous stage to generate:

$$\operatorname{Sign}_{S^2}(\operatorname{Sign}_{S^1}(m))$$

Is there a way to verify that $m$ has been signed by either signer without having to remove the signature of signer $S^2$?

Also, can I verify that $m$ was signed by signer $S^1$, even if I am not interested in verifying that it was signed by signer $S^2$?

Let a signed message consist of a bit string $m$ and a set of signatures $\Sigma$.  A ‘signed message’ of a bit string $m$ with no signatures is $(m, \{\})$.  When the $i^{\mathit{th}}$ user signs $(m, \Sigma)$, they return $(m, \Sigma \cup \{\sigma\})$ where $\sigma = \operatorname{Sign}_{S^i}(m)$.  The verifier confirms that there are signatures by all the signers they care about on the message.

This works with any base signature scheme, like Ed25519.  If a signature appendix in the base signature scheme adds $s$ bytes, and there are $n$ signatures, a signature appendix in this composite signature scheme adds $s\cdot n$ bytes, and the cost of verification is at most $s$ times the cost of verification of the base signature scheme.

If this doesn't satisfy your goals, you'll need to be more specific about what they are!


period of the lfsr sequence after some manipulations Here is the question I am dealing with. I have some sort of a solution but I need more specific results. If someone can help I'd appreciate:
Given 3  maximum length (max period) LFSR's of lengths L1,L2,L3 which are clocked simultaneously and L1,L2,L3 are  pairwise relatively prime. The output sequence is the output of the 1st or 3rd one depending on the output of the second one being 0 or 1, respectively.
1) If we pick only every fourth bit of the output sequence how does linear complexity(LC) and period change? What would they be in terms of the previous LC and Period?
2) What is the weightt of the sequence in one period?
Now here is my solution in short: First of all this is Geffe Generator and combining function is  f(x1,x2,x3)=x2.x1+x2.x3 +x3$.
-Linear Complexity= LC= f(L1,L2,L3)=L2.L1+L2.L3 +L3. (since lengths are all relatively prime)
- Period = P = (2^L1 -1).(2^L2 -1).(2^L3 -1) (since they are of max period   and relatively prime lengths i.e. Li's)
Now let's say the output sequence of the system is {a_n} = {a0,a1,a2,a3,...}
1)  Picking up every fourth bit of the output sequence is the 4-decimation of the sequence starting from a3. Therefore 3 terms need to truncated before the decimation is taken into account. Decimation does not increase the LC but truncation makes LC at most  LC+3. I solved this by considering the denominator of the generating function which is the connection polynomial whose degree gives the LC after all simplifications are done.
i.e. if new LC is L then:
L <= LC+3
But I don't know how to find the period in terms of the period of the unmodified  system P. I could only say that, if the new period is T, then:
T<= (2^{L+3}-1)
Can anyone give a more specific bound for the new period which is in terms of the unmodified period P of the system?
2) for the weight of the function in a period :  I checked the Truth Table of the function f. And it is balanced, thus weight must be:  (2^{3-1})= 4.  But how can I find the weight of the sequence in a period?
My idea is: in one period function takes all possible input values (x1,x2,x3) that is possible. ( as many as integer multiples of lengths.) Thus it must be the weight of the function multiplied by some integer?  I am not sure of that one?  Does anyone have an idea?

If you pick every 4th term in the sequence, since the original period $P$ is
$$
(2^{L_1}-1)(2^{L_2}-1)(2^{L_3}-1)=2^{L_1+L_2+L_3}-2^{L_1+L_2}-2^{L_1+L_3}-2^{L_2+L_3}+
\sum_{i=1}^3 2^{L_i}-1,$$
and relatively prime to 4, except for trivially small choices for the $L_i,$ you get a proper decimation and a reordering of the sequence. There is no truncation.

Thus $LC_{new} \leq LC_{old}.$ But note that each of the component maximal length sequences can be written as $\mathrm{tr}(c_i \alpha_i^t),$ where $\alpha_i$ is a primitive element in $GF(2^{L_i})$ and the constant $c_i$ from the same field is used to adjust the phase.

However, the trace map is linear under repeated squaring $$\mathrm{tr}(x)=\mathrm{tr}(x^2)=\mathrm{tr}(x^4),$$ (constant on cyclotomic cosets) and decimation by 4 is equivalent to taking the fourth power, so I contend that the linear complexity also stays the same.

In addition, the weight of the decimated sequence obviously doesn't change.

The weight of the original sequence will simply be $(P+1)/2,$ since the function is balanced and the all zero point $f(0,0,0)=0$ is missing from the truth table.


Is the padding wrong on the "Length Extension Attack" Wikipedia page example? In the Length extension attack of Wikipedia
The following information summarizes the relevant information provided on the page at the time of posting this question.
The provided parameters are

secret length: 14
message: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo
the original signature is 6d5f807e23db210bc254a28be2d6759a0f5f5d99
the page does not explicitly state it, but we can infer that the hash algorithm used in the example is SHA-1 (using SHA-1 yields the new signature provided in the example, 0e41270260895979317fff3898ab85668953aaa2)

The extended message (referred to on the page as "New data", reformatted here to remove the line breaks and spaces) is listed as:
count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x02\x28&waffle=liege
The padding should yield a message length in bits (excluding the extension) that is a multiple of 512.
Counting the bits in "New data" (excluding the extension):

message length in bits = 55 * 8 = 440
secret length in bits = 14 * 8 = 112
padding in bits: 58 * 8 = 464
total length in bits (excluding the extension) = 1016

Based on the above calculation, there are 8 bits missing, so "New data" should include another \x00.
Is my calculation/reasoning/understanding wrong?

50- byte padding staring with 1 and rest is zero ( each \ is a byte)
\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
\x00\x00

8-byte size part of padding where the size is encoded ( SHA-1 has 64-bit length encoding in the padding that makes 8-byte)
\x00\x00\x00\x00\x00\x00\x02\x28

0x228 = 552 and we have 69 bytes of message size.
That is correct. 55-byte message and 14-byte secret make a 69-byte message.
The message in bits makes 552 bits that are over one block of SHA-1 that has a 512-bit block size. So in total, we need 1024 bits for hashing, two blocks. 64 bits reserved for the message size. This left 960 bits. Now subtract the 552-bit message size and we have 408 bits. So we need 51 bytes of padding starting with 0x80 but we have 50, i.e. $\color{red}{\text{1-byte is missing. Your calculations are correct}}$.

We should have;
$$\underbrace{secret}_{14-byte}\mathbin\|\underbrace{message}_{55-byte}\mathbin\|\underbrace{100\ldots00}_{51-byte \text{ padding 10 part}}\mathbin\|\underbrace{000\ldots 0228}_{8-byte \text{ length part}}$$

SHA-1 padding rule

append the bit $\texttt{1}$ to the message e.g. by adding byte $\texttt{0x80}$ if message length is a multiple of 8 bits i.e. byte-oriented.

append $0 \leq k < 512$ bits of zeroes, such that the resulting message length in bits is congruent to $$−64 \equiv 448 \pmod{512}$$

append the original message length, as a 64-bit big-endian integer.
Thus, the total length is a multiple of 512 bits.

The real extension;
Wikipedia doesn't show the required padding after &waffle=liege is appended. This is 13 bytes text and the size of the message will be $1024+13*8= 1128$. Therefore we will need 3 blocks for the extension that makes total of 1536 bits. 64 bits of this will be the new size encoding and this will need 344 bits of $1000.000$
$$\underbrace{secret}_{14-byte}\mathbin\|\underbrace{message}_{55-byte}\mathbin\|\underbrace{100\ldots00}_{51-byte \text{ padding 10 part}}\mathbin\|\underbrace{000\ldots 0228}_{8-byte \text{ length part}} \mathbin\|\underbrace{\text{&waffle=liege}}_{13-byte \text{ extended message}} \mathbin\|\underbrace{100\ldots00}_{43-byte \text{ padding 10 part}} \mathbin\|\underbrace{000\ldots 0468}_{8-byte \text{ extended length part}} $$
In other view;
$$\text{SHA-1}(\text{secret_key}\mathbin\|\text{message}\mathbin\| \text{pad1}\mathbin\|
 \text{appended_data} \mathbin\| \text{pad2})$$


Is a new block cipher harder to design than a new hash? I realise that   cipher and  hash primitives are somewhat different.  But they share common requirements like attack resistance amongst others. And I realise that attacks /vulnerabilities are different for each.   However in addition to resisting attacks, a cipher has to be reversible given the correct key. And it has to be very not reversible given a slightly incorrect key.  A hash does not,    simply needing something like what the RadioGatún team called a secure mangling function.

Does this mean that a new secure block cipher is more difficult to develop than a new secure hash? Or are they just     too applely and orangey for objective comparision?

PS. I'm aware of Feistel networks and  stream ciphers. I'm referring to the       block primitives themselves like DES  & AES v. SHAx   & Whirlpool and whatever else is in the pipeline.

There are standard constructions for block ciphers and hashes that can be instantiated with a given "mangling function", where the "mangling function" is a fixed permutation such as keccak-f, or for another example Rijndael without the addRoundKey layer.

There are really two different things you might design: A new construction that uses a permutation, or a new permutation for instantiating a given construction*.

Instantiating a known construction with a new permutation

If you want to develop a new permutation and instantiate a key-alternating block cipher or sponge construction for hashing, then they are more or less challenges of equivalent difficulty. There are some differences.

One of those differences has to do with how you calculate how many rounds the resultant design will require to be secure. A hash function does not use a secret key, and so an adversary has an easier time crafting inputs that will target the weak points of the design. So an unkeyed hash function will tend to require more rounds than a block cipher to achieve the target security goal.

A permutation designed for a hash function may also be larger than one designed for a block cipher. This may seem like a trivial detail, but with vectorized designs MOV instructions into vector registers are expensive, and there usually are no vector rotate instructions. Using SIMD (single-instruction-multiple-data) efficiently is more challenging than not using it at all, but you can't make a big permutation that is fast without it.

A block cipher tends to incorporate a key schedule of some kind, which is a requirement that will not necessarily be present when designing a hash function. If you are using a block cipher in a Merkle–Damgård construction then the key schedule will be relevant to the security - this is where the related-key attack model is relevant.

It may be slightly easier to design a permutation for a block cipher than a hash function if you can get away with a 128-bit block size, due to not having to muck about with SIMD.

Designing new constructions

The other game to play is: Suppose you are given a permutation such as keccak-f. How can you create a block cipher with it? How can you create a hash function with it?

This game is arguably more open-ended and challenging than the previous one. If you want to find a construction that is not simply a variation on a pre-existing construction, you may have a lot of thinking to do.

In this case you can't really answer whether coming up with a new block cipher or hash construction would be more challenging than the other - how can you rate the difficulty of coming up with novel ideas that you don't know of yet? Who's to say whether Merkle–Damgård style hash functions were harder to come up with than Feistel networks, especially when you assume that you don't yet know of the existence of either type of construction?

* It doesn't have to be a permutation (which is invertible), but it helps to keep the answer simple and on-point to only consider permutations.


What is universal composability guaranteeing, specifically? Where does it apply, and where does it not? I don't have a proper computer science education, so bear with my misunderstandings.
UC is supposed to "guarantee strong security properties". From what I stand, if you have some secure protocol, such as a strong block cipher mode of operation, you can't distinguish it from another protocol that looks pretty much the same. But how?
Let's say I use regular AES-GCM as part of a protocol, and I also use a protocol that just uses a variant of AES-GCM with the same key size, but with a single round instead of 10+? Or maybe a really weak block cipher, tailor-built to be broken?
Scenario
Say that Alice and Bob have established communications on unsecured channels X and Y. They use protocols named PX and PY. Eve can listen in on both of these channels. A channel is made of two parts: A tape controlled by Alice, and a tape controlled by Bob, but are open to be written to by any machine. Since there are two channels, there are 4 tapes involved.
PX is nearly identical to PY, except that they use different block ciphers. Technically, however, we can say that they are different protocols. Eve cannot distinguish between one protocol and another because everything is encrypted in transit, and Eve only started eavesdropping after Alice and Bob have exchanged Diffie-Hellman parameters and created a session key (no MITM attack happened, since parameters are signed and certified by some TTP).
Universal Composability states (correct me if I'm wrong) that if Alice and Bob and Eve are Turing machines with Eve is able to intercept new symbols written to Alice or Bob's tapes (but not "effectively" write to them*, since doing so requires existential forgery to be possible), and Eve cannot distinguish whether symbols made on either channel is defined by the rules for PX or PY, and one of PX and PY are provably secure, then both PX and PY are secure.
Question
However, PY utilizes a very weak block cipher, despite traffic from the two being indistinguishable**. Eve can brute force the key for decrypting PY symbols with ease. By attempting brute force attacks on both channels, one of them succeeds in polynomial time. Does this not violate UC?
*"Effectively" means that, while Eve can write a bunch of symbols on Bob's tape and pretend to be Alice, Bob can easily distinguish the fake symbols from those that are from Alice.
**Is it even possible for something to be breakable yet indistinguishable? I made a leap in logic here that is probably incorrect.

The different guarantees of security
In security proofs, you have several guarantees that you can obtain on the security of a protocol. The most famous are maybe the following:

game-based security
sequential composable security
general composable security (sequential + parallel composition)

Game-based security
The weaker guarantee that you can obtain is the game-based guarantee. Here, you specify a game, usually between a challenger and an adversary, and the goal of the adversary is to win the game. If no polynomially bounded adversary can win this game, you will say that the protocol is secure. The first problem of this model is that you can only specify a specific property that you want your protocol to respect, but it's very hard to think about all the possible properties that you would like your protocol to respect.
For example, let's imagine that you want to transmit a message between Alice and Bob, and make sure that Bob does not learn the message that Alice sent to Bob. Then, you could imagine the following game:

The challenger (playing the role of Alice), picks a random message $m$ uniformly at random over all the messages of length $n$ ($n$ being the "security parameter"). It encrypts the message and sends this cipher text $c$ to the adversary.
The adversary (playing the role of a malicious Eve), receives the cipher text $c$ and outputs a message $\tilde{m}$ to the challenger.
The challenger says that the adversary wins if $m = \tilde{m}$

We can then say that an encryption scheme is secure if no adversary can win this game with non negligible probability over $n$, i.e. if there exists a negligible function $f$ such that for all adversary:
$$\Pr[ m = \tilde{m} ] \leq f(n)$$
For simplicity, we will write that as:
$$\Pr[ m = \tilde{m} ] \leq negl(n)$$
This game seems pretty natural, however it is very imperfect. Indeed, it denotes the fact that no adversary can completely learn $m$ given $c$ when $m$ is sampled uniformly at random over all the messages of length $n$. But it may be completely possible for an adversary to learn lots of information about $m$! For example, it could be possible for him to learn the first $n/2$ bits of a message: just consider the stupid encryption algorithm that do not touch the first $n/2$ bits of a message, and perfectly encrypt with a one time pad the last $n/2$ bits. This encryption scheme is secure according to the above game, but nobody would claim that this scheme is completely secure since it reveals half of the message!
There is also another issue: in this specific game, the adversary has no way to choose the distribution used to sample $m$. For example, if you know that the messages exchanged are always YES or NO, and that the scheme is slightly buggy and maps all YES messages to the $0\dots 0$ string (while all other messages are perfectly encrypted), then this encryption scheme is nearly perfectly secure... but completely useless in practice. Due to that property, it means that you usually don't have any guarantee on the security of the protocol when it is composed into larger protocols, since the input usually come from other protocols that could be controlled by an adversary.
Then people tried to come-up with games that provides more guarantees (see CPA, CCA, CCA2 securities)... And this is just for encryption. Then for all others primitive (signature, delegated computation, authentication...) you need to redefine all the games that you want to have, and make sure that you didn't forget any property that may be crucial for the security of the protocol. The way I imagine games is a bit like some "lines" that you can draw to delimit the security of the protocol: it's nice to get a rough picture of the security of the game, but it's hard to be sure that you did not forgot any property to really cut down all possible attacks.

So to sum-up this section:
Advantages of game-based security:

proof are simple to do in this model of security

Drawbacks of game-based security:

it is harder to see quickly what guarantees we have on a protocol: games can be quite specific and tied to a specific form of attack
we usually don't have guarantees when the protocol is composed into other protocols

Sequential and parallel composability
Then, to avoid these issues, people started to define "simulation based" models of security, that could guarantee that the protocol can be securely used when it is composed into other protocols, or used at the same time as other protocols. Usually, you can compose protocol either:

one after the other: it's called "sequential composition"
at the same time: it's called "parallel composition"

Some models of security (like the standalone model) provides guarantees when the protocol are composed one after the other (i.e. under sequential composition) while other models of security target security under both sequential and parallel composition (i.e. "general composability"). It is the case of the Universal Composability (UC) model, but also of the Constructive Cryptography (CC) model (a.k.a. Abstract Cryptography model)).
All these models are quite similar in the spirit, and are "simulation based" (you will understand later why). I'll mostly focus on UC and CC here, but the standalone model is quite similar as well. Note that I don't want to enter into the details of how UC is defined in term of Turing Machine, channels... because I don't think it really adds anything important, and I think it is mostly confusing implementation details. Therefore both UC and CC models are very similar at that level of abstraction (for me CC is a kind of generalization of UC in which the computation model is not explicitly specified and can be instantiated in different manners, for example with Turing machines, but also with quantum machines...). So here, we will just assume that there are some parties and some oracles, and that if required they can communicate between each others.
So first, I like to see them as a "special case" of game-based models, except that we force the games to have a very specific shape that allows us to have stronger guarantees on the security, due to the addition of a simulator. So the two entities that we had before are still there:

the adversary that we defined in the game based-security section is now called "environment" (in UC) or "distinguisher" (in CC). The UC model also describe something that they call adversaries, but in practice it's possible to get rid of them by replacing them with so called "dummy adversaries", that simply forwards everything to the environment.
the challenger will be described later, and basically everything else will be part of the challenger

On top of that, the "games" will be described in a very special way. We will indeed introduce the Ideal Functionality (called "resource" in CC) that is supposed to be a perfect, ideal, version of our protocol, i.e. trivially/information theoretically secure version (NB: as pointed in the comments, the Ideal Functionality is more precisely our "definition" of security, i.e. we want to prove that our protocol is at least as secure as our Ideal Functionality, in the sense that if you can learn some information during the real protocol, you can learn equality interesting information in the ideal protocol. However, most of the time we are interested by Ideal Functionalities whose properties (i.e. which information is learnable or not from an attacker) are trivial to check, that's why I do this shortcut and say that the Ideal Functionality is "information theoretically secure". I elaborate more on that in the remark at the end of this post). Then we will say that a protocol is secure with respect to that Ideal Functionality if there exists a simulator that "disguise" the ideal functionality so that it becomes indistinguishable from the real protocol. That way, any attack that can be done in the real protocol (also called "real world") could also be done in the ideal protocol (also called "ideal world")... which is impossible because it's information theoretically secure!
Now, we have all the ingredients to define our "challenger": the challenger will toss a coin, and with probability $1/2$ it will let the adversary (i.e. the environment/distinguisher) interact with the real world, and with probability $1/2$ it will interact with the ideal world (composed of the ideal functionality + simulator). At the end, the adversary (i.e. the environment/distinguisher) needs to say to the challenger if it is interacting with the real world or the ideal world. The protocol is then said secure if no computationnally bounded adversary as a significant advantage in winning this game, i.e. if the probability of winning the game is $\leq 1/2 + negl(n)$.
For example, if you want to talk about a perfectly secure channel (that cannot be modified, by an eave dropper, and that leaks only the size of the message), you could define an ideal functionality as follow:

Where the left "interface" of the ideal functionality belongs to Alice, the right interface to Bob, and the bottom interface to a potentially malicious Eve. As you can see, it is very clear from the picture that no Eve can learn anything else but the size of the message $m$ given only access to the bottom interface.
Now, we want to say that our protocol is at least as secure (modulo the fact that we consider computational security) as this Ideal Ressource. So first, let's define our protocol. Here, for simplicity, we will assume that we already have an authenticated channel, i.e. that we have a protocol realizing the following ideal functionality:

and that on top of that, we also suppose that we have a protocol to distribute a secret key:

Then, the idea is just to encrypt the input $m$ (for example using the One Time Pad algorithm, or if you prefer you can try to see if it works with the AES-GCM algorithm) using the key $k$, and put the cipher in the authenticated channel. Bob will then be able to decrypt it:

Now, to prove the security, we need to find a simulator that disguises the ideal functionality into this protocol (for simplicity, here we consider Alice and Bob are honest, but in UC you need to prove that far all possible subsets of possible corrupted users, and you can define a different ideal functionality depending on who is corrupted/malicious). If we assume that $E_k(m)$ has the same length as $m$ and looks like a uniform random string (which is the case of the one time pad encryption), then the simulator is trivial: it just generates a random string of size $|m|$.

It is then easy to show for the one time pad that no environment/distinguisher can make the distinction between to two last pictures (i.e. between the real world and the ideal world), because for any $r$ we can find $k$ such that $r = m \oplus k$, and all these keys are equiprobable. If you consider AES or other encryption schemes, then you need to prove that if the environment/distinguisher can make the distinction between the two world, then you can use the distinguisher to break a hardness assumption.
Now, you may wonder why is it a strong security guarantee. The first thing you can see is that if you have an attack against the real world (say, you can extract $m$ having access to $E_k(m)$ on Eve interface), then you could do exactly the same on the ideal world: so you could extract $m$ having access to a random string completely unrelated with $m$. Or if you consider the block "environment/distinguisher + simulator", you managed to extract $m$ having only access to the size of $m$... Impossible no? ;-) So it means that there exists no attack that is possible in the real world but impossible in the ideal world, i.e. the the real world is at least as secure as the ideal world. We can therefore continue our picture like that:

Then, you see that the composability comes "for free". Indeed, if you can attack the protocol by running another protocol in parallel or sequentially, then you could integrate that protocol into your environment/distinguisher and use it to attack the first protocol directly.
And to answer the OP's question
After all that, I still didn't have answer directly your question. So first your question does not completely makes sense since you usually compare an ideal functionality with a real world protocol, while in your question you compare two real world protocols. But then, indeed, if Eve (or rather the environment/distinguisher) can break your weak encryption scheme (we can continue our above example), then it will be easy for it to recover $m$ given $E(m)$ in the real world, and check if indeed it corresponds to the $m$ given as input to Alice. Now, in the ideal world, if it inverts the message $r$, it will find a message $m'$, but it is very unlikely that this $m'$ will match the $m$ that he gave to Alice. So the environment/distinguisher can easily make the distinction between the ideal and the real world: it tries to invert the message he saw on the channel, and check if it matches the $m$ given to Alice. If it does not, it means that it is talking with the ideal world! So it is not possible to prove the UC security of an encryption scheme that is weak ;-) (so that answers your last questions: Does this not violate UC?: yes, it does violate UC. Is it even possible for something to be breakable yet indistinguishable: no)
So usually, UC proofs are considered much stronger than usual game-based proof. However, they are much more difficult to prove, and there exist quite a lot of impossibility results.
Also, a last comment: you say something like "take a weak AES with only a few rounds", and indeed since it's not secure, it cannot be UC. But then you may wonder "what happens if we add one round? And two rounds? And 10 rounds? When is it starting to be back to UC?". So usually people consider asymptotic security, i.e. they take a security parameter $n$ (it could be linked with the number of rounds of AES, the size of the key...), and see what happens when $n$ goes to infinity. Then, they say that the protocol is secure if the distinguishing probability is smaller than $1/2+f(n)$, for some functions $f$ that is negligible, i.e. converges to 0 faster than any polynomial. So it does not make sense to say that AES is UC secure if we fix the size of the key and the number of runs, since in constant time you can break it (maybe it's a huge constant, but still independant of $n$). But you could talk about the AC security of AES, where the number of runs is $n$ and the size of the key is $n$. The reason why we like asymptotic security is also because in that regime, if a task A is easy to do, and if a task B is also easy, then you can also easily do both tasks A and B, and even repeat them a polynomial number of times. While if you are not in the asymptotic regime, then you don't have this nice stability property: if task A can be done in less than 100 years on one computer (a life time), and if task B can be done in less than 100 years on one computer, then A and B may not be done together in less than 100 years on one computer.
I hope this will help you to grasp what is behind UC/AC!
A remark on computationally secure Ideal Functionalities (spoiler: not really better than game-based security)
Again, as pointed out in comments, our Ideal Functionality is more precisely our definition of security (i.e. the protocol is at least as secure as the Ideal Functionality). So in practice, one could prove that a protocol realizes a completely broken Ideal Functionality (so just saying "the protocol is UC secure" is not enough to claim the security of the protocol, one also must check that the Ideal Functionality is indeed meaningful), or we could choose to define our Ideal Functionality to "look secure", i.e. be only computationally secure (for example, one could imagine that the Ideal Functionality leaks some encryption). However, my claim is that this kind of computationally secure Ideal Functionality is not very helpful:

First, it is quite hard to quantify the security of a computationally secure Ideal Functionality. If we consider for instance an Ideal Functionality that leaks the encryption of a message, then the first question will be "what can I learn from this ciphertext". And then, you would need to argue why this leakage is fine, so you will need to define some games that are hard to win... There is therefore no clear benefit of using simulable security over game based security in that context, since instead of defining games to quantify the security of your protocol, you will need to define games to quantify the security of the Ideal Functionality (i.e. the problem is just shifted from protocol to Ideal Functionality). Note that if the Ideal Functionality is information theoretically secure, the security is trivial to obtain and games are not even really required since most of the time it is obvious to see what is possible or not.
It is very easy to define computationally secure Ideal Functionalities that are very specific to one given protocol (one trivial way to do that is simply to take the Ideal Functionality that corresponds to the protocol itself). But then, if your Ideal Functionality is too specific (for instance because it hardcodes a given encryption function inside...), the benefit of using composable security framework is mitigated: when you use your protocol as a sub-protocols in bigger protocols, since existing literature is unlikely to have considered your very specific functionality, you will need to do a whole security analysis from scratch for any such big protocol. Which is basically what you would have do in game based security.
I'm also not aware of a single paper that defines such computationally secure Ideal Functionality. Of course, I do not know all papers, but still, I guess it shows that people do not really consider them.
Finally, I think that an important interest of simulation-based security is to abstract the protocol as much as possible and improve its modularity: this is very elegant, and having computationally secure Ideal Functionalities goes against that abstraction.

The only advantage I can see to consider computationally secure Ideal Functionality is to provide a simpler overview ofthe requirements of a protocol, but I'm not even really convinced.
For all that reasons, I don't think that having computationally secure Ideal Functionalities is really better than having game-based security.
Note that there also exist cases in which is is impossible to have information theoretically secure Ideal Functionalities, but where it is possible to have computationally secure Ideal Functionalities and game based security. See for example this paper (disclaimer, this last paper is a paper of mine (and is quantum), See section 3.4 for the computationally secure, unsatisfactory, Ideal Functionality and for a short similar discussion). You should be able to derive similar results for most impossibility results, including the impossibility of UC-secure commitment protocols, I just don't think they even bother to define a computational version of the Ideal Functionality (which could be, for example, an exact copy/paste of any commitment protocol).


Why would an Initialization Vector be supplied externally? My software uses a 3rd party encryption appliance. One of the capabilities they allow is for the client software to supply an IV while doing CBC encryption.

Why would they not generate a random number on their own to use as an IV?

What is the advantage of letting the client specify an IV?  I can only think of disadvantages, such as people supplying an insufficiently random number over a public network.

It offers more flexibility in using that API. Having a separate IV parameter enables bigger plaintexts than would not be possible in a single invocation, because of for example memory restrictions.

I assume CBC is used. You generate the IV and invoke the encryption on the first part of the big plaintext with the generated IV. For every other part of the plaintext, you take the last block of the previous ciphertext and use it as an IV to get the ciphertext of the current plaintext part. You then concatenate every ciphertext part to get a ciphertext which is the same as you would have got in a single invocation on the complete plaintext.


Finding the prime factors of $n'$ given the previous $n$ and its prime factors $p$ and $q$ Say I have a very large number $n$ = $pq$ where $p$ and $q$ are prime.

A new number $n'$ is generated by increasing these prime factors. How can I find this new number's prime factors?

On one hand, what's asked in the question's title is finding the factorization of $n'$ given the factorization of "the previous" $n$ as $n=p\,q$. As far as we know, that can't be done for $n'$ of cryptographic interest, for a definition of "previous" implying a small increase in value.
That's part of surrogate factoring, which is to factorization what perpetual motion is to movement.

On a second hand, what's asked in the question is different: finding the factorization of $n'$ given that it is of the form $p'\,q'$ with $p'$ (resp. $q'$) a prime "generated by increasing" some known $p$ (resp. $q$). That makes the task easy, for a definition of "increasing" implying a small increase in value. All there is to do is explores the integers $p'$ above $p$ sequentially, and try if they divide $n'$, until hitting the factorization; it is not even necessary to check that $p'$ is prime.

On a third hand, a comment tells that "$n$ grows by a digit each round", which implies that at least one of $p$ or $q$ has changed a lot in value. If only one has changed a lot, we can try the above method on both $p$ and $q$. If both have changed, and we have no clue about how, then the factorization of $n$ is useless to find that of $n'$, and we are back to the problem of factorization of $n'$ without clue, which can be handled up to 800 bits (240 decimal digits) give or take 50%, depending on resources.


Is it safe to re-use the same p and q to generate a new pair of keys in RSA if the old private key was compromised? Say I selected two large primes p and q for RSA and computed my public key (e, n=pq) and my private key (d).

Now, I was careless and compromised my private key (d). p and q were not leaked. Taking into account that (e, n) were already public knowledge, would it be safe to generate a new key pair with the same p and q or are they somehow compromised by the leaking of the private key?

If it would not be safe, how could someone compute p and q from my public-private key pair?

No, it is not safe.

There are several methods to compute $p$ and $q$ from $n$, $e$ and $d$. See appendix C of this document.


Is there an algorithm to derive a 1-of-N shared secret from a set of N private keys? This is different from Shamir's Secret Sharing in that we are starting with the keys and deriving a shared secret, rather than the other way around.

Let me be more precise:

We are given keys $k_1, \ldots, k_N$. We wish to derive a shared secret $S$ and a public datum $D$ such that:

$S$ is the same size as the $k_i$ (i.e. it is an element of the same key space).
$D$ is as small as possible -- hopefully no bigger than $S$ (but I'll take what I can get).
$D$ together with any one $k_i$ is sufficient to recover $S$, but insufficient to recover any of the $k_j$ (for $i \ne j$).
$D$ alone is insufficient to recover $S$. (This is to preclude trivial solutions like making $S$ constant.)

Can anyone suggest an algorithm, or convince me that this is impossible?

If no one solves this I may accept a partial solution that satisfies a subset of the above criteria.

I'll start this thread off with a not-very-satisfying solution. If we let $D$ be as long as all the $k_i$ put together (i.e. $|D|=N |k_1|$), then we can solve this using Shamir's Secret Sharing (SSS).

First, choose any $S$ we want. (As you can see, this problem is now under-constrained.)

Use $1$-of-$N$ SSS to derive keys $r_1,\ldots,r_N$, any one of which is sufficient to recover $S$.

Then define $$d_i := r_i - k_i$$ (that is, the difference between the $i$-th SSS key and our $i$-th input key).

Finally, let $$D := d_1 \| \cdots \| d_N$$

Now we can use any single $k_i$, together with $D$, to recover one of the $1$-of-$N$ SSS keys, which gets us $S$.

So I've established an upper bound on the length of $D$. Can anyone do better?


Adaptive Hash Functions: How to tell how many iterations were used? If an adaptive hash function like bcrypt or PBKDF2 is used in hashing passwords, the number of iterations used in the hashing process can be configured.

For a penetration tester or a malicious hacker, what are the ways to determine how many iterations were used in hashing passwords, assuming that they do not have access to source codes, only a database dump of the password hashes.

The plain hash itself does not give any indication of the number of iterations. But with practical schemes, such as most crypt based ones, the number of iterations is stored alongside hash and salt in the database.

Keeping the number of iterations secret doesn't gain you much security in practice. Figuring out the number of iterations isn't that hard in practice. Choose a few users who probably have weak passwords, and compare after each iteration. Or if you can register your own accounts, you can simply attack that single user whose password you know.

If you want to improve security in a scenario where the attacker obtains only the database, but not the source-code/config file, there are much better techniques than a secret number of iteration. For example you could concatenate the salt with a secret key, or encrypt the hash. That way an attacker has no chance of attacking the hashes without gaining access to the place where you store the key.


Why can't garbled circuits be reused? There are a bunch of papers do research on resizable garbled circuits. But I wonder why garbled circuits cannot be reused?

For example, the constructor constructs a garbled circuit of "AND" like this:

$E_{K_{u}^0}(E_{K_{v}^0}(K_{w}^0))$,
$E_{K_{u}^0}(E_{K_{v}^1}(K_{w}^0))$,
$E_{K_{u}^1}(E_{K_{v}^0}(K_{w}^0))$,
$E_{K_{u}^1}(E_{K_{v}^1}(K_{w}^1))$

Then he sends this garbled circuit and $K_{v}^0$, $K_{v}^1$ to the evaluator.

Every time, he wants to evaluate the garbled circuit with an input $b\in\{0,1\}$, he just sends $K_{u}^b$ to the evaluator.

Other than letting the evaluator know that he may have the same input in different evaluations, I cannot think of other revealed information.

One of the security guarantees of garbled circuits is that the evaluator doesn't learn anything about the circuit beyond the output on the given input.  Executing more than one input string will break this property.  For instance, if you allow him to evaluate two inputs, $0^n$ and $1^n$, then he can "mix and match" bits on each gate to determine what kind of gate it is.  An AND gate will have three outputs which are the same, but an XOR will only have two, etc.  Additionally, by doing this mix and match, he will be able to calculate the output value of the circuit on new inputs which you have not directly given to him.  Combining these two advantages, it is also very likely that the will be able to recreate some or all of the bits of the input by tracing the circuit, since he learns the final output in plaintext.


Alternative to NSA encryption algorithm I am looking for a strong alternative to elliptic curve cryptography. It should be something that could face quantum computing attacks, but nothing created by the NSA.

I heard about isogeny key exchange, i.e. supersingular isogeny, is it really secure? Otherwise, what would be an alternative that fulfills the above?

In addition, what would be a post-quantum algorithm for file encryption? Perhaps snow 3g?

Supersingular isogenies are a rather recent attempt at post quantum security. You will have a hard time finding an efficient and secure implementation, and even if you write one yourself, the algorithms have not yet seen that much cryptanalysis. (Although that's a subjective judgement call.)

If post quantum security wasn't a concern, you could choose from any number of non-NSA elliptic curves. However, quantum computers, if practical, can break elliptic curves (using Shor's algorithm).

NTRU is, like the other answer notes, a more practical and established alternative for post quantum cryptography. It still isn't necessarily as efficient or well studied as elliptic curves, though. As a practical matter the main implementation is under GPLv2.

For key exchange there is also the "new hope" lattice algorithm which is being field-tested by Google as a possible successor of ECC in TLS. (Personally I find this to be one of the likelier algorithms to see use, but I would not use it – alone – for anything important yet.)

For file encryption, or anything that works with a secret key, you can use existing symmetric algorithms. You may want to choose a key size of at least 256-bits, though, to account for the quantum Grover's attack. SNOW 3G in particular isn't post quantum secure for that reason – it has a 128-bit key. Other standardized general purpose ciphers like AES-256 or something on the eSTREAM portfolio (Salsa20 at least has a 256-bit key) would work fine.


RSA2048 smallest possible modulus what is the smallest possible modulus for RSA2048? I generate a random data with I want to encrypt by a textbook RSA2048 and I'm not sure where the first 1-bit should be.

According to OpenSSL source code and used padding function, the first byte seems to be 0, 2 follows and than there could be anything. Seems I need first 14bits to be 0 to ensure my plaintext fits the RSA modulus.

The modulus defines the key length for RSA. So a 2048 bit key has a 1 at the leftmost bit. Otherwise there could be almost any number of zero's following it, each zero becoming less likely, as the modulus value depends on two large random primes - usually in the order of half the bit size of the modulus. So if you want to take a minimum modulus $N$ into account, you can have any 2047 bit message for plaintext RSA - as long as the most significant bit of the most significant byte is zero (commonly RSA uses big endian calculations, so that would be the highest order bit of the leftmost byte).

But please note that plaintext RSA is insecure; the security of the scheme would depend on the content of the message. If it by chance is a fully OAEP padded message then it is certainly secure if verified correctly, but I'm not sure you would implement a secure scheme by chance. Actually, I would consider it highly unlikely that a scheme would survive even the simplest of plaintext oracle attacks.


What is the lowest level of mathematics required in order to understand how encryption algorithms work? What mathematical fields of knowledge would be required in order to get a good understanding of encryption algorithms?

Is it basic algebra, or is there a "higher education" mathematical field dedicated to encryption? I know there is the cryptography field, but what is the subset of knowledge required for cryptographers?

Most encryption is based heavily on number theory, most of it being abstract algebra.  Calculus and trigonometry isn't heavily used.  Additionally, other subjects should be understood well; specifically probability (including basic combinatorics), information theory, and asymptotic analysis of algorithms.  There's also more math that's worth knowing to be a good programmer which is key if you really want to be an expert.  The number theory is more important with understanding asymmetric encryption, but does come up in symmetric encryption as well (e.g., in AES how to derive the S-box and MixColumns relates to understanding Galois fields).

First, you need to learn some notation.  Things like logical operators, most importantly for cryptography XOR (sometimes denoted as circle plus: ⊕), where 0 XOR 1 = 1 XOR 0 = 1, and 0 XOR 0 = 1 XOR 1 = 0.  It also helps to be able to understand the notation and language of abstract mathematics and set theory; e.g., {0,1}128 means the set of all strings that are made up of 128 binary digits (each digit is a 0 or 1).  Similarly, F: {0,1}64 → {0,1}128 means F is a function that maps a 64 bit input into an output that is 128-bit string.  You'll have to learn the difference between a function, bijection, permutation, etc, but again this is mostly just terminology of relatively simple concepts.

One of the most important topics is modular arithmetic.  E.g., 1 ≡ 64 (mod 21) where (mod N) means you only care about the remainder when dividing by N (since 64/21 = 3 with remainder 1; the modulo is 1).  One important notation to learn (that's a potential source of confusion) is that the (mod N) applies to both sides of the equation; so you could equivalently say 8^2 ≡ 1 (mod 21).  Many programming languages (e.g., C, Java, python, javascript) use % to do modulo division -- e.g., 64 % 21 gives 1.  The cool thing about modular arithmetic is that you can just do normal arithmetic (addition and multiplication) and reduce at the end (or at any step in the middle) as modular arithmetic forms a finite field; e.g., 8 ≡ 29 ≡ 50 (mod 21) so since 8*8 ≡ 64 ≡ 1 (mod 21) we also know that 29*8 = 232 ≡ 29*50 = 1450 ≡ 1 (mod 21).  With modular arithmetic there's no difference both 8, 29, 50 represent the exact same number.

You'll need to understand things like Fermat's little theorem, Euler's theorem (based on totient), Euclid's algorithm for greatest common denominators (specifically Euclid's extended algorithm to generate multiplicative inverses), Carmichael numbers, Fermat primality test, Miller-Rabin primality test, modular exponentiation, and discrete logarithms.

If you want to go further you may want to learn about things like finite fields (specifically Galois fields), polynomial rings, elliptic curves, etc.  This isn't meant to limit things; e.g., cryptography (and attacks on cryptography) aren't necessarily limited to these types of math.  E.g., NUTRUEncrypt is based on lattices/shortest vector problem, and the McEliece Cryptosystem is based on Goppa codes, but again you still need to learn the math above to be able to understand this math.

And then you have the basic math background to learn about cryptography, which isn't just the math but also involves using the math in secure ways.  (For example, textbook RSA c = m^e mod p q is insecure for a variety of reasons - you should use a secure randomized padding scheme to your message and likely combine with symmetric encryption for long messages).

Free Electronic References

The Handbook of Applied Cryptography - Chapter 2 has a decent introduction to these concepts for the advanced learner -- it introduces concepts very quickly and compactly, and is probably better as a reference or second/third attempt at the material.
Chapter 1 of Algorithms by DPV (specifically sections 1.2 to 1.4) give a gentler introduction to the math behind RSA.  (2015 Update: This pre-print of the book appears to be have taken off the one of the authors' academic website.  The good textbook is available for purchase on amazon.  I believe you can still find the book for free via google search for "Dasgupta  Papadimitriou Vazirani algorithms pdf", though I am not directly linking as I am not sure it is being shared by a copyright holder with authority to legally share the book.)
Shoup - A Computational Introduction to Number Theory and Algebra - From the preface "Number theory and algebra play an increasingly significant role in computing and communications, as evidenced by the striking applications of these subjects to such ﬁelds as cryptography and coding theory. My goal in writing this book was to provide an introduction to number theory and algebra, with an emphasis on algorithms and applications, that would be accessible to a broad audience."  Very detailed and fairly accessible.
Stick-figure introduction to AES at various levels of complexity with the last level showing where the number theory goes in.
The Udacity Applied Crypto course.  More of an introduction to the cryptography than the math behind it, but introduces the math when necessary.
Dan Boneh's Coursera cryptography course.  Solid introduction to cryptography, again introducing the math when necessary.


Is there a general way to crack this graph cipher? Every coded message has a numerical key, it can be a number any digits long. Each decoded letter of the message is placed on separate points of a 10 by 10 coordinate graph. Each letter is represented by a 6 digit number. The first two digits show which letter of the alphabet the letter is. A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 10 20 30 40 50 60 70 80 90 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 The third and fourth digits represent the Y axis point. The fifth and sixth digits represent the X axis point.

To encrypt a letter, one takes the representing numbers and multiplies the 6 digit number by the key. If the key was 605, and one wants to place the letter 'H' on point Y: 5 X: 3, the equation is 805,030 * 605. This equals 487043150.

To decrypt the letter H, one divides 487043150 by 605. This would equal 805,030. Then the solver fills in the blanks. 80 shows that the letter is H. 50 shows that the letter goes on Y point 5. 30 shows that the letter goes on X point 3. The solver would then decode letters systematically until they spell out words on the graph.

As stated by @tylo, this cipher can be cracked by simply finding the greatest common divisor for your numbers.

Continuing from your example: if i am encrypting the message HELLO using the key 605, while following along the graph (or what is essentially a matrix) with the intention to spell out my message, i only actually need the calculations for the first two letters to find the key:

H: 805030 * 605 = 487043150
E: 505040 * 605 = 305549200

Taking these numbers one can trivially find gcd(487043150, 305549200)—gcd being the greatest common divisor—e.g. by using a tool like WolframAlpha, which finds the gcd to be 6050 (6050 rather than 605 due to both of the numbers multiplied with the key ending in a zero, thus for this purpose having an unnecessary extra power of magnitude. Removing these zeros would give 605 directly).


Why is the subhash key (H) of AES-GCM defined as such? From what I've read in section 5.3 of NIST 800-38D it states:

  The hash subkey, denoted H, is generated by applying the block cipher
  to the “zero” block.

In serious crypto J.P Aumasson describes the implementation of it as H = AES(K,0) for a single block of zeros, hence no block chaining mode, hence no IV as I understand it. Therefore the mapping between H and K should be universally constant.

The book notes:

  In GCM, GHASH doesn't use K directly in order to ensure that if GHASH's key is compromised, the master key K remains secret. Given K, you can get H by computing AES(K,0), but you can't recover K from that value since K acts as AES's key.

If the mapping is universally constant wouldn't it be the case that this could be pre-computed and available somewhere? (I wanted to say rainbow table here, but that probably doesn't quite apply based on what I read in this response)

So is the strength just that storing this permutation space for later indexing is thought to be too large? Or is there more to it that what I laid out?

In GCM, GHASH doesn't use K directly in order to ensure that if GHASH's key is compromised, the master key K remains secret.

Actually, there's not why GCM was designed the way it was (it may be an effect, but not the reason).  Instead, the reasons were:

To allow provable security (based on the assumption that the block cipher was a secure keyed random permutation).  If we used $k$ as both the block cipher key, and used as an input to compute the tag, we need to make additional assumptions on the block cipher.
Because of the size mismatch; $h$ is 128 bits, $k$ is (at least, for AES) is either 128, 192 or 256 bits.  Yes, one could select an arbitrary section of $k$ as your $h$, however, that seems a bit, well, arbitrary...

In any case, to answer the question you did ask:

  If the mapping is universally constant wouldn't it be the case that this could be pre-computed and available somewhere?

Not really, the effort of pre-computing such a table would be at least $O(2^{128})$ operations; we believe that is infeasible for anyone, even as a one-time effort.  And, generating a rainbow table doesn't decrease this effort any; it just makes the generated table smaller...


Is this the right way to implement one time pad? I would like to know if this the right way to use the one time pad based on this table

Now, my idea is to use the same Ascii #2 to again if the message is longer, I know this is bad practice, what I found this is the only solution if the key is short.
Also, I read that better if I XOR the (#1 + #2), but I see it is useless, do you have a better way to enhance it?

No, this is not a proper way to perform the One Time Pad, even with just 5 letters (assuming the pad and message are bound to be letters that is in range [65..90]).

Problem is, when we see that the first encrypted character is 139, and since we know that the pad is in range [65..90], we know that the first plaintext character is in range [65..74], not in range [75..90]. That's a huge information leak. When the ciphertext character is 130 (resp. 180), we exactly know the plaintext letter: it is 65/A (resp. 90/Z).

The solution to this problem is to compute ciphertext as $c=((p+m)\bmod 26)+65$, and decipher as $m=((c-p)\bmod 26)+65$ (implementable as (c-p+26)%26 + 65 in C). As a bonus, the ciphertext consists of letters.

  My idea is to use the same Ascii #2 to again if the message is longer

That's a tried, tested, and bad idea. This is no longer a One Time Pad and it is no longer unconditionally secure. See for example How to attack the Two Time Pad?.


How would I convert an arithmetic circuit into a system of bilinear equations? Given an arithmetic circuit, are there any examples of turning it into a system of bilinear equations, with the end goal of turning it into a matrix?

I don't know if this is exactly what you mean, but you can always consider each one of the wire values in the circuit as variables, and then create an equation per gate which represents the relation that the corresponding wires must have.

For example, if the wires labeled as variables $x$ and $y$ are the inputs of a multiplication gate, whose output is $z$, then you would obtain the equation $x\cdot y - z = 0$. Similarly for addition gates. Overall, you would get a system of $N$ (non-homogeneous) quadratic equations in $n$ variables, where $N$ is the numbers of gates and $n$ is the number of wires.


M-Sequence Properties in LFSR I test this law with a 7-bits primitive polynomial LFSR. and the run property could be found according to output. Is there any theoretical to prove m-sequence property, I could just find some conclusion on some literature.

General property for a primitive LFSR:

Each nonzero bitstring of length $k$ where $k\leq m,$ occurs $2^{m-k+1}$ times while the all zero bitstring occurs $2^{m-k+1}-1$ times, in a single period of the LFSR. The run of $k$ 1’s is just one of those nonzero bitstrings.

For $k>m,$ some patterns never occur. The ones that do occur are exactly those patterns that satisfy parity checks which correspond to polynomial multiples of the generating polynomial.

Example: For the generating polynomial $x^4+x+1,$ the generating parity check is
$$s_{t-4}\oplus s_{t-1}\oplus s_t=0.$$ Since
$$(x+1)(x^4+x+1)=x^5+x^4+x^2+1,$$
the only $5-$tuples that occur at the output of this generator are those satisfying
$$
s_{t-5}\oplus s_{t-4} \oplus s_{t-2}\oplus s_t=0.$$


Can we do Multi-Prime Diffie-Hellman? What is the correct way, if any, to do Multi-Prime DH?
From security point of view, is there any benefit to do it?
Multi-Prime is not about multi participants.
Multi prime is when we use two or more prime numbers and multiply them to get the modulus part in DH.
It is faster to find four 4096 bit safe primes and multiply them than to find single 16384 bit safe prime.
The question is if a multi-prime will yield valid and secure key exchange procedure.
And if so, what will be the procedure to get good g and p.

By Multi-Prime DH, I assume you mean something analogous to Multi-Prime RSA.
In Multi-Prime RSA, we pick a modulus with three (or more) prime factors; because the holder of the private key knows the factorization, he can compute (using the CRT optimization) using smaller prime modulii (and smaller exponents), yielding a moderate speed-up.
Given that is what Multi-Prime RSA, what would Multi-Prime DH be?  I assume that it is one where we pick a modulus with two (or more) prime factors.  If we know the prime factors, then we can use the CRT optimization (similar to how it works in RSA) to get a two time speed up in the DH operations (assuming two prime factors).
So, if that's the benefit, what's the downside?  Will if the attacker learns the factorization, he can use it to attack each prime factor of the modulus individually; this would yield a significant improvement in this expected effort.
So, what do we conclude?  Well, this would be a moderate optimization (factor of 2) for one side (we can't assume both sides know the factorization), at the risk that the adversary learns it (in which case it drastically reduces the security level).
Hence, I cannot recommend it.

Update: on reconsideration, I do see one scenario where it might make some sense; if you are generating ephemeral Diffie Hellman groups (which is quite unusual, however I have run into knowledgable people who have advocated for it); in that case, searching for (say) two 2048 bit primes is much simpler than searching for a single 4096 bit primes.  In addition, in that case, we wouldn't have to worry about whether $p-1$ has small factors (because the corresponding value for $\phi(n)$, which the adversary wouldn't know).  The security of the system would rely on the difficulty of factoring $n$ (as that factorization process would dominate the time taken by the discrete log problem modulo the smaller primes).  Hence, in this corner case, it would make some sense.


Can all asymmetric key pairs be reversed? After reading about public/private key cryptography, there are still a few points I don't really understand.

Based on the way (I understand) challenges work, the public key is used to encrypt a sequence which the private key can be used to decrypt:

When a key pair is freshly generated, does it matter which key that is chosen as the private key since the opposite key can be used for encryption?
Does this apply to all known and/or hypothetic asymmetric encryption algorithms?

This depends on the public-key system (algorithm).

For RSA, technically the private and public key (i.e. the exponents, the keys share the same modulus) are symmetric, you can swap them, and it still works.

But you usually don't want to do this: The public exponent is usually a small number (like $3$ or $2^{16} + 1$) in order to speed up encryption/signature verification, and can thus be easily guessed. You don't want this property for a private key.

Also, in practice the private key is often not just the exponent $d$ and modulus $n$, but also the factors of the modulus (i.e. $p$ and $q$), in order to speed up decryption or signature. That kind of key certainly doesn't work as a public key.

For other public-key systems (like ElGamal/DSA, Diffie-Hellman, or EC), the relation between public and private key is not symmetric at all. In the examples mentioned you have a private key $x$ and a public key $y = g^x$ (with some kind of exponentiation operation which is difficult to reverse).

In these cases, you certainly can't swap out public and private key.