Reductionist proofs of decisional problems to computational

Such reductions I know are

the reductions in hardcore predicates/functions from computational assumptions, say, from the OWP/OWF/RSA/DCR/CDH/DBDH assumptions,
the reductions in (provably-secure) PRGs/PRFs from computational assumptions, say, from the OWP/OWF/RSA/DCR/CDH/DBDH assumptions, and
the reductions in LPN/LWE.

Re:

  Can you be more specific? I.e: with CDH ? How CDH can be broken using a decisional problem attacker? ?  curious yesterday

Very recently, Fazio, Gennaro, Milinda Perera, and E. Skeith III (CRYPTO 2013) proved that

If the CDH problem over elliptic curves (EC) is hard, every bit of the secret DH value is unpredictable, and
If the partial CDH problem over the finite field $\mathbb{F}_{p^2}$ is hard, every bit of the secret DH value is unpredictable.

Their slides are avilable at Milinda Perera's website.

Overview.

Let $P:\mathbb{G} \to \{0,1\}$ is a predicate that is a candidate of hard core of the CDH function, $f(xg,g^a,g^b) = g^{ab}$.

We want to construct $\mathcal{I}$ that, given $g,g^a,g^b$, computes $g^{ab}$ by using a predictor $\mathcal{A}$ that predicts $P$ with non-negligible advantage.

Fazio et al. adopted a general framework proposed by Akavia, Goldwasser, and Safra (FOCS 2003), which can be considered as an extension of the proof strategy for the Goldreich-Levin general hardcore predicate.

The framework of Akavia et al. is summarized as follows:

We define a multiplication code that $\mathcal{C} = \{C_x:\mathbb{Z}_N \to \{0,1\} \mid x \in \mathbb{Z}_N\}$, where $$C_x(k) = P(k \cdot x).$$
Imagine a very long codeword of length $N$ whose $k$-th value is $P(k \cdot x)$.
(Since they will consider the Fourier transformation, $\{0,1\}$ will be replaced with $\{-1,+1\}$.)
We can treat the predictor as a received word whose values are corrupted at most half minus non-negligible portion.
The reduction algorithm now uses a list-decoding algorithm to find out candidates of $x$.
If the candidates are few, the reduction algorithm outputs one of them.
(In the CDH case, we cannot verify whether the guess is correct or not.)

Akavia et al. constructed the list-decoding algorithm for "good" multiplication codes and showed several candidates of one-way functions are "good."
Fazio et al. defined multiplication codes for EC-CDH and PartCDH and showed their "good" properties.


Differential cryptanalysis - breaking the last round of FEAL4?

No, it's not flawed.  You're just running into a fact of life; differential cryptanalysis generally doesn't just give you the entire key (or even subkey) in one shot.  It generally gives you partial information about the key, and if you want the entire key, well, you need to work at it more.

In this phase of the attack, you know that the last round subkey is one of four possibilities. Here's one obvious way to continue the attack on the next-to-last (penultimate) round subkey: you introduce the same set of differentials advanced one round (so that it has a probability 1 of surviving the first round, and fails on round 2).  In the example they gave, this would be an input differential of 0x00000000 on the left side, and 0x80000000 on the right.

Then, for the output of each differential, reverse the last round operation (using each of the 4 possible last round subkeys), and see if there is a possible next-to-last round subkey that makes that differential work, and if so, what is that next-to-last round subkey is.

If you do this is a number of differential pairs, it is quite likely that an incorrect guess to the last round subkey will not allow any next-to-last round subkey work for at least one of the differentials; that is, for one of the differential outputs you'll have in hand, there will be no value that the round 3 subkey can take on that would make that a possible output.  That means that you can eliminate the three incorrect guesses of the last subround key.  In addition, that also gives you four possible values for the round 3 subkey.

So, to recap, this next phase of the attack verified the last round subkey, and also gave us most of the next-to-last round subkey.  It should be fairly obvious how this attack continues.  Note that continuing this attack doesn't cause any exponential blow-up, as we are able to verify the remaining subround key bits left unverified by the previous attack.

Now, if there is a problem with this example of differential cryptography, it is that it is somewhat atypical of how differential cryptanalysis usually works; it's not really misleading, but it is rather simpler in this case.  There is almost never a probability 1 differential through most of the cipher.  Instead, we generally need to work with differentials with a considerably lower probability of holding, and use statistical methods to figure out when the differential holds.


This is one of the most poorly written "mainstream" crypto papers I've read. Sorry, McGrew and Viega.

Field representation and bit order

GCM works in the binary field $GF(2^{128})$. Elements of this field can be represented as polynomials with binary coefficients (i.e. 0 or 1).

Using the notation of the paper, here are some examples of field elements:

$1$ (note that this is $0\alpha^{127} + 0\alpha^{126} + \ldots + 0\alpha^1 + 1$; we simply don't writte the coefficients with 0).
$\alpha^1 + 1$
$\alpha^2 + \alpha$
$\alpha^{127} + \alpha^{64} + 1$
$\alpha^{127}$

Cool. So how do we represent this in memory, since we only have bits and bytes, and not actually polynomials? The straightforward way is to simply group the coefficients in groups of eight, inside bytes. Which raises the question: how to order the bits inside the byte? And how to order the bytes inside the 16-byte buffer (totaling 128 bits)?

One straightforward answer is to use little endian for both bits and bytes; i.e the least significant bit of the byte (i.e. what you get with x & 0x01, note that calling this "little endian" it not that usual but I need to call it something) is the least significant bit of the 8-bit group; and the least significant byte of the buffer (i.e. what you get with b[0]) is the least significant 8-bit group of the 16 groups.  So these examples would be encoded as:

$1$: 0x01 0x00 ... 0x00
$\alpha^1 + 1$: 0x03 0x00 ... 0x00
$\alpha^2 + \alpha$: 0x06 0x00 ... 0x00
$\alpha^{127} + \alpha^{64} + 1$: 0x01 0x00 ... 0x01 ... 0x00 0x80
$\alpha^{127}$: 0x00 ... 0x00 0x80

This seems natural (at least it does for me); but you could make a convicing argument for a "little-endian" bit order and big-endian byte order since it looks more like the way we write the polynomials. That's OK. Is that what GCM does? No, it isn't.

GCM uses "big-endian" for bits, and little-endian for bytes. Our examples become:

$1$: 0x80 0x00 ... 0x00
$\alpha^1 + 1$: 0xC0 0x00 ... 0x00
$\alpha^2 + \alpha$: 0x06 0x00 ... 0x00
$\alpha^{127} + \alpha^{64} + 1$: 0x80 0x00 ... 0x80 ... 0x00 0x01
$\alpha^{127}$: 0x00 ... 0x00 0x01

So there's that.

Now actually answering the question

  According to the examples on page 9 in formulas (3) (5), would they be the same, right?

Yes.

  Well already on page 11 in the example of the deconposition of X (7), xi refers to 1 byte of X, but my doubt is in P ^ 8i, in the first for 8 · i would give zero and at the end when i is 15 would be 120. That part I don't really understand.

As I described, the coefficients of the polynomials are grouped into 16 bytes with 8 bits each. Formula (7) is just the mathematical way of saying that. Note that $P = \alpha$. Why not call the same thing by two different names?

For example, take the field element $X = \alpha^{15} + 1$. This is represented by the byte buffer 0x80 0x01. So in the decomposition, we have:

$x_0$ = $1$ = 0x80
$x_1$ = $\alpha^7$ = 0x01 (we're looking at it as a 8-bit polynomial)

and then, $X = \bigoplus\limits_{i=0}^{15} x_iP^{8i} =  \bigoplus\limits_{i=0}^{15} x_i\alpha^{8i} = x_0\alpha^0 + x_1\alpha^8 + ...$ = $1\alpha^0 + (\alpha^7)\alpha^8 = 1 + \alpha^{15}$.

  Assuming that the value of i is 64, that cycle would multiply by P eight times if I am not mistaken.

Table $M$ contains $M[x] = xH$ for all 8-bit polynomials and the 128-bit polynomial $H$ (which is computed from the key).

That cycle multiplies by $P$ seven times. That loop is computing $M[128], M[64], M[32], ... M[1]$. Recall that the index is actually a polynomial, so that's the same as $M[1], M[\alpha], M[\alpha^2], ..., M[\alpha^7]$. Yes, $128 = 0x80$ (the number) is equal to $1$ (the polynomial). Welcome to GCM.

  Everything explained above is fine, it would be enough to build table M0 and R? But I don't understand the following elevation P^8(i+1) and P^128.

I think what I've explained covers the rest of your question, but I'm not sure. Feel free to ask for clarifications and I'll edit the answer.


How many characters per block in an El Gamal ECC cryptosystem?

First: use rather ECIES or some other IND-CCA2 safe variant.

If this is a theoretical question you need to know, that any plaintext (a number) must be smaller than $p$. To reach this the bitlength $log_2(m)$ must be smaller than the bitlength $log_2(p)$. Now you can only encode the data as bytes(256 values), so we are switching from base 2 to base 256 and hence $msglen=log_{256}(m)<log_{256}(p)$.

I hope that answers your question (although a bit late)


Sensible usecase for restricting special characters in passwords?

Summary of comments, not to take credit.

Answer so far is: cryptographically no. But it's practical for usability.

Restricting control characters is useful for different interfaces/input methods.
Restricting non-ASCII characters is useful for avoiding bugs with different encodings.
Restricting characters that are not on every keyboard adds to the user-friendly experience (preventing the user from locking themselves out on a different device).
Restricting characters that are in different locations on different keyboards prevents 'habit-mistakes' on different keyboards.
When a password is easier to remember it's less likely to be written down (in theory) see: XKCD #936: Short complex password, or long dictionary passphrase?


AES 128 bits with 12 bytes IV vector composed of a 4 bytes counter : safe?

As SEJPM notes in the comments, the IVs will repeat after $2^{32}$ frames.  This is bad (unless the key is changed more often than that).

In particular, if you can temporarily capture the device and make it encrypt $2^{32}$ known messages of sufficient length, you will learn the keystreams corresponding to all the $2^{32}$ possible IVs for that device.  This allows you to trivially decrypt any past or future messages sent by the device just as easily as if you had the key.

Depending on the nature of the device, convincing it to encrypt $2^{32}$ known messages may be anything from impossible to trivially easy.  Since you yourself mention that "the frame counter may overflow in the long run," it seems that it's at least within the realm of possibility.

In any case, even if this particular attack turns out to be infeasible, any situation where two different messages are encrypted in CTR mode with the same key and IV violates the basic assumptions of the security proof for CTR mode, and makes it potentially vulnerable to attacks.

To prevent such attacks, you'd need to either:

ensure that the frame counter can never overflow (under normal or abnormal operating conditions), or
ensure that the key is changed (at least) every time the frame counter overflows.

To prevent counter overflow, you can either widen the counter (e.g. adding the two unused bytes in the IV to the frame counter to make it 48 bits wide) or add an explicit overflow check (which might mean bricking your device instead of compromising security if the maximum number of message frames is exceeded, unless you have some kind of a key update mechanism in place), or, better yet, both.

Addendum: As user4982 notes above, a similar attack is also possible even without wraparound, if the frame counter can be forced (or accidentally made) to reset to zero (or to any previously used value) e.g. by cutting power to the device.

One way to defeat this attack is to store the frame counter in non-volatile (e.g. flash) memory.  Since such memory can often be slow to write to, and may not tolerate an unlimited number of write-erase cycles, one commonly used trick is to write a value that is, say, 1000 frames higher than the actual current counter value, and then wait until the actual counter catches up to the stored value before the next write.  This allows you to reduce the number of writes to non-volatile memory by a factor of 1000, at the cost of potentially skipping up to 1000 counter values every time the device is reset.

(There are other, more sophisticated methods of minimizing non-volatile memory wear as well, but they tend to depend on the specific characteristics of the non-volatile storage you're using.)

Of course, if the device already has some way of changing the encryption key, another option could be to simply change the key every time the device is reset, eliminating the need to store the counter entirely.


The answer depends on how you would layer the encryption on top of the existing protocol.

If you implemented your own Skype client, you could deal with compression issues yourself. That might allow you to use format preserving encryption, perhaps on the compressed data stream and not the audio itself.
However, you would need to be careful – speech compression is very lossy and concentrates the few bits it uses on where they are needed. You'd need to make sure patterns of speech would not be visible as higher bitrate bursts.

If you let Skype deal with compression, you likely couldn't use format preserving encryption due to compression artifacts. Instead, you'd need to use a lower bitrate encrypted channel that gets encoded as audio, probably together with some kind of error correction.
Again, you'd need a constant bitrate to hide the encrypted information fully, so some extra buffering would likely be needed to make efficient use of what's available. If the bitrate isn't enough, you might need to use a video call as the data channel for encrypted audio.

I'm unsure if the former would be an option over cellular, if the compression is done in hardware outside your control, or if the data gets recompressed en route.

As I understand the voice compression algorithms work by cutting off sounds over a certain frequency, so if the encrypted "sound" would be 100% in the "don't truncate" part of the sound spectrum the voice codec would have no way of compressing and default to send the entire thing.

That's not an accurate picture of how (modern) speech compression works. Instead, like most other lossy compression it also quantizes the information so that it is inaccurate compared to the original, but close enough for a human. Some frequencies are weighted higher and some lower, but all essentially lose information (unless the signal is very low bandwidth). Going into more detail is off topic here, but you can start from Wikipedia if you are interested.
Could you essentially invert the compression process and push the data into forms where it's retained? Maybe. That would be a very complex way to get 1. above without implementing the actual client.


HMAC remains unbroken with MD5 and SHA1 because it has a secret key that the attacker doesn't know. Therefore, the attacker cannot carry out huge computations on itself (as is required for finding collisions). [A parenthetic comment: please do not misunderstand me; MD5 is completely broken and should not be used anywhere including in HMAC.] In contrast, when you fix the HMAC key and make it public, you can once again find collisions. In fact, the specific collision-finding algorithms that we know for MD5 and SHA1 (via differentials) work for any IV. When using a key for HMAC that is known, this just gives a different IV. Thus, there is no problem whatsoever finding a collision (in practice, given known methods; not just theoretically).

The solution to SHA1 being broken is to move to SHA256 (and later to Keccak after some more validation time).


Metrics for Measuring the Distance of Two Numbers in Cryptography

Nothing is falsely indicated there!
The Hamming distance is between strings (vectors) of the same length in the space $\{0,1\}^n. $ However the integer representation of such vectors is in a different space and the distance there is different.
Besides integer distance $|x-y|$ between two integers you can have minimal cyclic distance $$\min \{|x-y|,|n-x+y|\}$$
for two elements modulo $n.$
Note Some such distances won't be a metric. The  triangle equality or symmetry may be violated.
More generally since polynomials are also widely used in Crypto, you could have metrics depending on the Hamming distance of their truth tables, or value tables if non-binary.
Or the minimal degree of two polynomials minus the number of common roots they have.
Edit: Or edit distance (levenshtein distance) which is usually defined as the minimal number of $$(insertions+ deletions+substitutions)$$ required to map a string of length $m$ to a string of length $n$ where $n=m$ is not needed. Sometimes, a weight is put on the different operations and weighted cost is minimized.


Among the reason why root public keys are often expressed as a self-signed certificate are:

It cryptographically protects against a deliberate alteration of an attribute of the public key (e.g. extension of validity period, or of what the key can be used for).
It strongly protects against accidental alteration of the public key value.
It is a reasonably effective countermeasure against some deliberate alterations of public key value or attributes, e.g. fault-injection attack.
It makes it easier to have all public keys share a single common format, complete with attributes.
Public keys are usually generated by an entity distinct from the entity or entities that will certify it, and thus if we want to leverage the above benefits must be self-signed at some point. Now if there is no authority to certify that key (as is the case for a root CA key in a system with a single and independent root CA), it will just stay that way.

However, not all implicitly trusted or root public keys exist as a self-signed certificate, much less exist only in this form. For example, the public key of the European Root Certification Authority of the Digital Tachograph system is not available as a self-signed certificate (which could be made), for good reasons:

the relevant legal text does not provide that the key could be used to certify itself:

  [CSM_007] At European level, a single European key pair (EUR.SK and EUR.PK) shall be generated. The European private key shall be used to certify the Member States public keys. Records of all certified keys shall be kept. These tasks shall be handled by a European certification authority, under the authority and responsibility of the European Commission.

there would be a chicken-and-egg problem accessing the content of an hypothetical self-signed certificate of that key, for Digital Tachograph certificates use a signature scheme with message recovery (as many Card Verificable Certificates do), and part of the public key is in the recoverable part of the signed message.


Homomorphic decryption circuit in integer-based scheme

The circuit looks like any homomorphic version of a usual circuit: you replace the inputs by the corresponding ciphertexts and the operations by the corresponding homomorphic operations.

That means that,

The decryption circuit has as input a ciphertext $c$, which is a vector of $Q$ bits, and the secret key $sk$, a vector of $P$ bits; and it performs a $\mod 2$ operation at the end.
But the homomorphic decryption circuit, let's call $HDec$, has as input a vector of $Q$ ciphertexts ($\bar{c}$) representing the encryption of each bit of $c$ and a vector of $P$ ciphertexts ($\bar{sk}$) (representing the encryption of each bit of $sk$. And $HDec$ does not perform the $\mod 2$ operation, but a homomorphic operation equivalent to the $\mod 2$. Since it is a homomorphic operation, it returns a ciphertext (so, a $Q$-bit value, as expected).

Thus, $Dec$ takes vectors $(c_1, c_1, ..., c_Q)$ and $(sk_1, sk_2, ..., sk_P)$ and returns one bit $b$, while $HDec$ takes vectors $(Enc(c_1),..., Enc(c_Q))$ and $(Enc(sk_1), ..., Enc(sk_P))$ and returns a $Q$-bit value $Enc(b)$.


Which bitwise operations are used in SHA-256?

The functions used by SHA-2, called $Ch$ and $Maj$ are defined like this in the standard:

$$Ch(x, y, z)  = (x \land y) \oplus (\lnot x \land z)$$
$$Maj(x, y, z)  = (x \land y) \oplus (x \land z) \oplus (y \land z)$$

However, an equivalent way to define them replaces the XOR with OR, as the standard (pdf) states:

  Each of the algorithms include $Ch(x, y, z)$ and $Maj(x, y, z)$ functions; the exclusive-OR operation ($\oplus$) in these functions may be replaced by a bitwise OR operation ($\lor$) and produce identical results.

Of course, any functionally complete set of operators is sufficient to implement the functions, but at least some implementations (e.g. PyPy) do elect to use OR here.


Distribution based integer factorization

The archetypal algorithms that could take advantage of $p$ being close to the square root of $N=pq$ is Fermat's factorization method; and some improvements thereof.

The basic Fermat factoring method makes about $(p+q)/2-\sqrt N$ steps. Applied to $N\approx 2^{127}$ and $p/\sqrt N\approx 0.98$ (as in the question) this is over $2^{51}$ steps. We have heuristic algorithms to factor any 128-bit RSA moduli much faster than that, and nearly as simple (e.g. Pollard's Rho), thus the method is worthless in practice even at the 128-bit level; that only gets worse when we increase the modulus to practical sizes, and compare to more powerful factorization algorithms.

There are improvements of the Fermat factoring method that still benefit from $p$ being close to the square root of $N$. They reduce the number of steps, by skipping most candidates, and performing table lookups rather than squareness tests. The gain is large, but severely bounded by available memory, and is not enough to become competitive at least for $N>2^{1023}$ and $|p-q|>2^{\lceil\log_2N\rceil/2-100}$ (the criteria in FIPS 186-4, with origin in ANSI X9.31:1988, that has plenty of headroom), which has overwhelming odds to be verified for random $p$ and $q$.


Randomness measure of a sequence over a finite set

The simplest approach is the bias away from uniformity of the sequence, $\epsilon$. $P(x_n = \text{any member of S}) = \frac{1}{|S|} \pm \epsilon$. So a regular die has 6 possible outcomes and thus a cardinality of 6.  Therefore in the case of a perfectly fair die, $P(x_n = \text{any member of S}) = \frac{1}{6} + 0.$

The USA's NIST organisation aims for $\epsilon = 2^{-64}  $ when characterising a sequence as 'fully' random. And this leads to issues of mensuration as it's very difficult to generate and managed the amount of data needed for an accurate determination with such small bias.

We therefore resort to stochastic methods within acceptable bounds of certainty, like chi-square tests.  To that end, see How many rolls do I need to determine if my dice are fair? Cryptographic tests typically use a confidence level of 0.1%.


If you look at the code in the Wikipedia we will see this part of the code;

h = (unsigned char)((signed char)r[c] >> 7);
b[c] = r[c] << 1;
[c] ^= 0x1B & h;

h stores the leftmost bit of c

c is x-or'ed with 0x1b but not with 0x11b  why?

When shifting r left by one, the MSB value is discarded. Before discarding, we hold this value with h.

If h==0 than modulus operation is not required. The 0x1B & h = 0x0 so there is no x-or with 0x1b
If h=1 than modulus operation is required. The 0x1B & h = 0x1B. The x-or with 0x1b is performed.
Note that: it is not x-or with 0x11b it is with 0x1b since we discarded the MSB 1 while shifting. Therefore, there is no need to x-or with 0x11b, x-oring with 0x1b is enough. Now, it is clear that everthing is in Bytes.

A small example;

Here [ ] represents 8-bit.

Let multiply $a = (x^7+x^6+x^3+x)$ by $\{2\}$

binary representation of  $a = [11001010]$
$h = 1 = [00000001]$
$b = a \ll 1 = 1[10010100]$ but everthing is in Bytes, therefore
$b = [10010100]$
$h \wedge 0x1b = [00000001] \wedge [00011011] = [00011011] = 0x1b$
$b \oplus 0x1b = [10010100] \oplus [00011011] = [10001111] = 0x8f$


Correctness of signle-point Oblivious PRF

My question is the following: why after the OT protocol, $q=r_0 \oplus[s\cdot F(y_R)]$?

Let's start with a case-distinction on the first bit of the OTs:

$s[0]=0$: In this case the sender gets $r_0[0]$ back. Written differently we actually get $r_0[0] \oplus 0\cdot F(y_R)[0]$ (because a XOR with a zero doesn't change anything). However we're in the case of $s[0]=0$ so we might as well write $r_0[0] \oplus s[0]\cdot F(y_R)[0]$.
$s[0]=1$: In this case the sender gets $r_0[0]\oplus F(y_R)[0]$ back. Also written differently we get $r_0\oplus 1\cdot F(y_R)[0]$. However we're in the case of $s[0]=1$ so we might as well write $r_0[0] \oplus s[0]\cdot F(y_R)[0]$.

As you can see in both cases we end up with $r_0[0] \oplus s[0]\cdot F(y_R)[0]$ on S's end. All that is left is to apply the exact same logic to the remaining bits of the OTs.


AES Cipher Block Chaining 128 bit message

However, if your message is exactly 128 bits long, do you only perform the XOR with the IV and the encryption with the key once? Or is there a way to split up a 128 bit message so that you can perform the cipher block chaining method as intended.

This is a non-starter, as there is nothing wrong with performing a single block encrypt in CBC mode. For 128 bits messages you don't need any padding method, even for CBC mode, but generally we try and apply PKCS#7 padding for compatibility reasons.

The XOR of the unpredictable IV with the plaintext is required, otherwise your cipher would not be able to handle identical messages without leaking information. If your 128 bit messages are unique by itself they you could just use a single block encrypt of the block cipher (the attacker would only know that no repetition is present in the messages).


Key exchange: I'll use ECC as an example. Alice and Bob generate ephemeral key pairs and sign their ephemeral public key with their static private key, and then send their signed ephemeral public key to each other.

Both parties receive the others signed ephemeral public key and verify it using the others static public key, stored by a CA or in a PKI. Now they combine their own ephemeral private key with the other's ephemeral public key, using EC Point Multiplication (for this example). Now they both have a shared secret, as both multiplications give the same result.

This is then run through a quick hash like SHA2/3 into the correct length for symmetric encryption. For example with AES-256, the shared secret goes through SHA(3)-256 to get a key of the correct length.

Key encapsulation: I'll use the RSA KEM for this example. Bob knows Alice's public key $(e,n)$. He creates the symmetric key $M$ from a CSPRNG , where $0<m<n$, and converts it into a symmetric key with a KDF ie symmetric key $M=KDF(m)$. The Ciphertext $$C = m^e (mod \ n)$$ This is transmitted from Bob to Alice, and she can decrypt it by computing $$P = m^d (mod \ n)$$ Alice now has $k$, and derives the symmetric key $M$ with $M = KDF(m)$

Side note: I've seen that you tagged post quantum cryptography, so you could use NTRU for KEM; ECC and RSA can be broken with a powerful enough quantum computer running Shor's algorithm. The NTRU KEM works differently to the RSA KEM however. I'm not familiar with a quantum safe version of the ECC key exchange, though I'm sure one exists.


Being new to cryptography is one thing, but you are supposed to do some research on your own before asking questions here (see How to Ask), and D.W. gave you the right directions already.

But since you wanted names and links:

The first stop should be discrete logarithm on Wikipedia, and it lists several algorithms on this topic.
As a beginner, start with Babystep-Giantstep and Pohlig-Hellman.
Your next stop should be Index Calculus.
Additionally, there are algorithms based on the NFS, e.g. described in Gordon's paper Discrete Logarithms in GF(p) Using the Number Field Sieve. Current records modulo primes employ this technique.


Dishonest verifier running a concurrent zero-knowledge protocol

The definition of soundness for an interactive (zero-knowledge) proof says that no prover can convince a verifier of a false statement (i.e., one not in the language in question), except with tiny probability. In your “Bob in the middle” scenario the statement is true—the graph is 3-colorable—so there is no violation of soundness if “Bob” proves it by relaying messages (or any other strategy).
A separate but related property is proof of knowledge, which informally says that any prover that succeeds in convincing the verifier (with large enough probability) must “know” a witness for the statement being proved—in this case, a 3-coloring for the graph in question. (This “knowing” is formalized by designing an extractor for the prover.) Importantly, in the formalization of this property, the prover can interact only with the verifier; it can’t “phone a friend” for help. So, Bob alone would not be considered a prover that on its own can convince the verifier, and therefore there is no requirement on what we can extract from Bob. By contrast, Bob together with Alice as a “joint entity” would qualify as a successful prover, but that joint entity does indeed know a witness, so there is no contradiction with the definition.
There are stronger notions of soundness and proof of knowledge that allow provers to have more powers, e.g., the ability to interact with other entities about other statements, the ability to “reset” the verifier, etc. These go by various names like concurrency, non-malleability, and resettable soundness. Your scenario is most related to non-malleability, except that Bob isn’t changing the relayed messages at all, which is something we can never prevent. Non-malleability basically says that such direct copying is the only way an adversary can succeed.


Is asynchronous perfect forward secrecy possible?

Asynchronous forward secure encryption is possible if you allow users to have synchronous clocks. It seems impossible without that or a third party, though I am aware of no formal result.

A trivial(and hence awful) solution is to generate N key pairs  and use one for each interval, discarding them as we go. A somewhat more efficient solution is to use Identity Based Encryption(IBE) to have one public key and N private keys.

The most efficient scheme I know of  is due to  Canetti, Halevi, and Katz  in this paper. It provides for constant size public keys and $O(log(N))$ private keys where N is the number of time intervals. As far as I know, no paper has improved on that bound, though several have achieved that bound with more efficient techniques.

The gist of the design is you have a tree of keys where there is one root public key and messages can be encrypted to any node in the tree with the root public key and the index identifying the node. (So far, this is just an IBE scheme). Unlike IBE, the decryption key for a given node can be computed from it's parent key.

We now map time intervals to nodes using a pre order traversal (i.e. the root is interval one, the left child interval 2, the left left grandchild of root is interval 3 ...). So once time interval 1 is up, we derive the keys for both the left and right nodes and then delete the root key. Now messages encrypted to interval one are safe, but we can still decrypt everything targeted at the remaining N-1 intervals.


Key equivalence across different elliptic curves

Yes you can. It is a proof of equality of discrete logarithms. Let's say the order of curve $g$ is $q$ and $h$ is $q'$, the tricky part is how to sample one challenge value that is uniform in both groups $Z_q$ and $Z_{q'}$. You cannot do it in either of the group because the value is not uniformly distributed in the other group. The trick is to sample the value uniformly random from $Z_{q\cdot q'}$, which would solve this problem.

The NIZK version of the proof thus requires a hash function $H:\{0,1\}^*\rightarrow Z_{q\cdot q'}$.

The prover chooses $r\in_R Z_{q\cdot q'}$, computes the following: $t=r\cdot G$, $s = r\cdot H$, $u = H(G, H, X_1, X_2, t,s)$, $v=r+x\cdot u$. The proof is $(t,s,v)$.
The verifier computes $u$ and verifies $v\cdot G=t + u\cdot X_1$ and $v\cdot H = s+ u\cdot X_2$.


Exhausting the entropy of a hash function

Entropy is not gas -- you do not "consume" it.

In the case of hashing passwords, entropy is a measure of what the password could have been. A password with "$n$ bits of entropy" is a password such that breaking it by dictionary attack (trying potential passwords until the right one is found) has average cost $2^{n-1}$.

It is useless to have a password entropy much beyond the output length of the employed hash function, because if you hash to $k$ bits, then trying random passwords will succeed with probability $2^{-k}$, hence average cost $2^{k}$. Thus, no need to go beyond $k+1$ bits or entropy for the password.

It is also useless to have a password entropy beyond the point where dictionary attacks are ludicrously expensive, regardless of the hash function output size. With today's technology, an 80-bit password entropy is already enough to defeat such endeavours. Actually, if the password hashing is done properly (with a slow password processing function, like bcrypt), then lower entropies are already fine (that's the point of slow hashing: to make low password entropy more tolerable).


How exactly to extract information base 10 from a PGP RSA key pair?

You can use the Web tool pgpdump, available at this address http://www.pgpdump.net/ or the same tool ( http://www.mew.org/~kazu/proj/pgpdump/en/)  to install on your pc.
This latter is to use if you are poking with your real secret key.

At the moment I don't remember if the tool outputs in hex or dec, but you can easily convert to your favourite Base using python or pari/gp or whatever mathematical tool you love more.


Difference b/w Hash function & Keyed Hash function? And HMAC with Matyas-Meyer-Oseas hash function

Intuitively a MAC is essentially the symmetric cryptography variant of a signature. To calculate a MAC a secret key which is shared between sender and receiver is used. This means that somebody who does not have the key cannot calculate the MAC.

A hash function on the other hand can be computed by anybody, uses no secrets and is simply used to get a shorter representation of data. For example, if somebody wants to sign an e-mail they usually hash it first and then sign the hash.

The Matyas–Meyer–Oseas construction is a way to construct a one-way compression function from a block cipher. This can then be used in the construction of a hash function, for example, using the Merkle–Damgård construction.

In particular, this means that the Matyas–Meyer–Oseas construction doesn't actually specify a complete hash function in an implementable way.


First, If the source isn’t explicitly labeled as “secure” or “crypto” in its name, you must assume it is insecure.

For example, in C#, the System.Random is insecure while System.Security.Cryptography.RandomNumberGenerator is obviously intended to be a secure RNG.

Second, you’ll need to actually do some research to ensure that it is, in fact, going to be a secure RNG in the version you are using, and in the target deployment environment. Will you have an entropy source when it is deployed?

Most languages let you access the operating system’s secure RNG in some way; these should be preferred over any user-space generators to ensure fork()-safety. User-space RNGs are also far more likely to have bugs or their state compromised by bugs in user-space applications, which history shows are innumerable.

For example, Pythons os.urandom() doesn’t mention security in its name, but it does call the operating systems secure RNG directly (/dev/urandom on Linux and CryptGenRandom on Windows). When you use the OS generator you also don’t need to evaluate the security of a particular language’s generator user-space algorithm choices or implementation quality.

The OS generator on any recent mainstream OS can be trusted, unless you’re deploying into an environment with no entropy source (such as an embedded Linux device with no user inputs and no hardware RNG).


Significance of IV in Merkle-Damgård construction

broken up into blocks before it can be (hashed)... Then a fixed IV is used...

In practice, you may not even know the entire message before beginning hashing. So this is incorrect. You divide into blocks as more of the message becomes available.

  before it can be encrypted

You are not encrypting. You are hashing.

  the blocks can be padded if necessary

Padding is always added, not only added if necessary.

  the first block of the message is run through a compression function using something like AES (possibly derived from a block cipher) with the IV

So this is sort of correct. We don't use AES, but the constructions are similar/derived from block cipher principles. The key requirement is that the compression function should be collision resistant. With a block-cipher, you typically need to be able to undo the encryption. This is not necessary for a hash function's compression function.

Specifically related to AES, another reason we don't just use AES is that is only has a 128 bit block size. This is insufficient for the types of hashes we see today, which have at least a 224 bit output (SHA-2). The internal state must be wider than 128 bits.

P.S., thanks to fgrieu for some additional points that I have added.


Question regarding reconstruction vector in LSSS

For the tl;dr see the last few paragraphs.

LSSS Background

The construction of linear secret sharing you are referring to is based on the model of computation known as Monotone Span Programs.  Other papers  go into more detail and should help with further questions.

The paper that has given rise to your question is a proposed method to construct an LSSS from a given Boolean formula (equivalently, from an access structure).  For now, we will assume their method is correct and the derivation of the LSSS matrix is as they describe:

$\begin{array}{c}
  A \\
  B \\
  C \\
  D
  \end{array}
  \begin{pmatrix}
  1 & 1 & 0 \\
  0 & -1 & 1 \\
  0 & 0 & -1 \\
  0 & -1 & 0
  \end{pmatrix}$

We will denote this matrix by $M$ and assume we are working in a field $\mathbb{F}$.  For a dealer to share a secret $s \in \mathbb{F}$ in this scheme, he does the following:

Select any vector $\mathbf{x}\in \mathbb{F}^3$ such that $\langle \mathbf{x}, (1,0,0) \rangle = s$ (i.e. the inner product with the target vector is the secret);
Compute $\mathbf{y} := M\cdot \mathbf{x}$;
Give $\mathbf{y}[i]$ (the $i^{\text{th}}$ component of $\mathbf{y}$) to the party assigned the corresponding row of the matrix $M$.  So in this case, e.g. party $C$ will receive the third component of $\mathbf{y}$.

Now assuming the construction of the LSSS matrix is correct, then any set of qualified parties should be able to combine their shares to obtain the secret.  This is because the construction of the LSSS requires that the span of all of the rows held by any set of qualified parties must contain the target vector in their linear span.

In this example, $\{A,D\}$ is supposed to be qualified, and indeed adding one times the first row to one times the fourth row, i.e. computing $1 \cdot (1, 1, 0) + 1 \cdot (0, -1, 0) = (1, 0, 0)$, gives them the target vector.

This is useful because by linearity, parties $A$ and $D$ can use their shares to compute the secret using the same linear combination: i.e. $1 \cdot \mathbf{y}[1] + 1 \cdot \mathbf{y}[4] = s$.

The required linear combination is encoded in a vector: in the running example $\{A,D\}$, the recombination vector is $\mathbf{r}=(1,0,0,1)$, since we were required to add the first row to the fourth row.

Again assuming the construction of the LSSS is correct, we will also require that unauthorised sets of parties have no information on the secret.  This is true if and only if the target vector does not lie in the linear span of the rows held by those parties.

Let us denote by $M_U$ the submatrix of $M$ where we have selected only those rows owned by some unauthorised set of parties $U$.  So we have, e.g.

$ M_{\{A,B\}} = \begin{pmatrix}
  1 & 1 & 0 \\
  0 & -1 & 1
  \end{pmatrix}
$

To see that the colluding parties $\{A,B\}$ learn no information, observe that if $(1,0,0)^\top \not \in \text{im}(M_{\{A,B\}}^\top)$ then by the fundamental theorem of linear algebra, $(1,0,0)^\top \not \in \text{ker}(M_{\{A,B\}})^\perp$ and so there must exist some vector $\mathbf{w} \in \mathbb{F}^3$ such that $M_{\{A,B\}} \cdot \mathbf{w} = 0$ and $\langle \mathbf{w} ,(1,0,0)^\top\rangle \ne 0$.  (In other words, $\mathbf{w}$ must exist because otherwise every vector in $\text{ker}(M_{\{A,B\}})$ is perpendicular to $(1,0,0)^\top$, contradicting $(1,0,0)^\top \not \in \text{im}(M_{\{A,B\}}^\top)=\text{ker}(M_{\{A,B\}})^\perp$.)

In particular, we can find any $\mathbf{v}$ such that $\langle \mathbf{v} ,(1,0,0)\rangle \ne 0$ and $M_{\{A,B\}}^\top \cdot \mathbf{v} = 0$ and then set $\mathbf{w} = \frac{\mathbf{v}}{-\|\mathbf{v}\|_2}$ so that $\langle \mathbf{w} ,(1,0,0)\rangle = -1$ and $M_{\{A,B\}} \cdot \mathbf{w} = M_{\{A,B\}} \cdot \frac{\mathbf{v}}{-\|\mathbf{v}\|_2} = \mathbf{0}$.  This is the claim you highlighted.

The fact that we have found $\mathbf{w}$ already shows that union of the  shares held by the unauthorised parties provides no information on the secret, since adding the vector $k \cdot \mathbf{w}$ to the vector $\mathbf{x}$ that was used above to generate the shares encoded in the vector $\mathbf{y}$, where $k\in \mathbb{F}$ is any field element, provides the same set of shares for the unauthorised parties in question, since
we have shares
$ M \cdot (\mathbf{x} + k\mathbf{w}) = M \cdot \mathbf{x} + M \cdot k\mathbf{w} = \mathbf{y} + k M \cdot \mathbf{w}$
corresponding to secret $\langle \mathbf{x} + k \mathbf{w} , (1,0,0) \rangle = s + k \cdot -1$
and since $M_U \mathbf{w} = \mathbf{0}$, the shares held by $U$ can equally be shares for any secret, which we obtain by changing $k$ arbitrarily.  Consequently, the shares held by these parties cannot provide them with any information about what the secret is.

Computing $\mathbf{w}$

There is at least one $\mathbf{w}$ for each unauthorised set (assuming the LSSS has been constructed correctly). Note that you only need to find one $\mathbf{w}$ for each maximally unauthorised set (since this $\mathbf{w}$ will work for any subset too).

Computing the actual $\mathbf{w}$ as descibed in your reference involves finding any vector in $(M_{\{A,B\}})^\perp$ (which is called the cokernel or left kernel of $M_{\{A,B\}}$) which is non-zero in the first component, and scaling.  In the case of $\{A,B\}$, it is easy to find a $\mathbf{w}$ with the required properties by inspection: we can see that the vector $\mathbf{w} = (-1, 1, 1)^\top$ satisfies $M_{\{A,B\}}^\top \cdot \mathbf{w} = \mathbf{0}$, and it holds that $\langle (-1,1,1),(1,0,0)\rangle = -1$, which was what we needed (after transposing).

For larger matrices in this scheme, you just need a method for computing the cokernel of a given submatrix, and from there you take any vector $\mathbf{w}$ in that space satisfying $\langle \mathbf{w},(1,0,\ldots,0)\rangle = -1$, i.e. where the first component is $-1$.


As usual, I ask a question after a couple of days of research, then immediately realise the answer: I'm doing it wrong.

My definitions included the following "suites":

SSL2_RC4_128_WITH_MD5   0x010080
SSL2_RC4_128_EXPORT40_WITH_MD5  0x020080
SSL2_RC2_CBC_128_CBC_WITH_MD5   0x030080
SSL2_RC2_CBC_128_CBC_WITH_MD5   0x040080
SSL2_IDEA_128_CBC_WITH_MD5  0x050080
SSL2_DES_64_CBC_WITH_MD5    0x060040
SSL2_DES_192_EDE3_CBC_WITH_MD5  0x0700C0
SSL2_RC4_64_WITH_MD5    0x080080
CT_SSL_CERT_TYPE    0x800001
PCT_SSL_CERT_TYPE   0x800003
PCT_SSL_HASH_TYPE   0x810001
PCT_SSL_HASH_TYPE   0x810003
PCT_SSL_EXCH_TYPE   0x820001
PCT_SSL_CIPHER_TYPE_1ST_HALF    0x830004
PCT_SSL_CIPHER_TYPE_2ND_HALF_40     0x842840
PCT_SSL_CIPHER_TYPE_2ND_HALF_128    0x848040
PCT_SSL_COMPAT  0x8F8001

TLS has a cipher suite specifier length of 16 bits. My code, when given these 24-bit identifiers, ignores the high 8 bits. This means I'm really scanning for 0x0080 a few times, 0x0040, 0x00C0, 0x0001, 0x0003, 0x0004 (*), 0x2840, 0x8040, and 0x8001.

Since 0x0004 is RSA_WITH_RC4_128_MD5, and the target server supports that suite, my code was incorrectly reporting that PCT_SSL_CIPHER_TYPE_1ST_HALF was enabled. It just happened to coincide. Other values did not align with enabled cipher suites, so that's the only one that cropped up.

I've now removed these definitions since they're erroneous for SSL/TLS.

Silly me!


Fiat-Shamir paradigm and the forking lemma

Let's recall important definitions. A proof system $(\mathsf{P}, \mathsf{V})$ for an NP language $\mathcal{L}$ is a pair of interactive Turing machines where the prover ($\mathsf{P}$) and the verifier ($\mathsf{V}$) receive a common input $\ell \in \{0,1\}^*$ and the prover receives an additional input $w \in \{0,1\}^*$ that is the witness for $\ell$, i.e., the relation $\mathcal{R}_\mathcal{L}$ defined by the NP language $\mathcal{L}$ satisfies $\mathcal{R}_\mathcal{L}(\ell,w) = 1$. The prover and verifier exchange a couple of messages and finally the verifier outputs a single bit denoted by $\mathsf{out}_\mathsf{V}(\langle\mathsf{P}(\ell,w)\leftrightarrow\mathsf{V}(\ell)\rangle)$, indicating whether the verifier accepts the proof (1) or rejects it (0). The proof system is public-coin if the verifier's messages consist of pure, unprocessed randomness. In this case the Fiat-Shamir heuristic says that no security is lost by replacing these randomly chosen messages by the hash of all messages up until that point. (And since there is a proof of this fact, albeit in the random oracle model, it is technically wrong to refer to it as a heuristic --- hence the more common phrase "Fiat-Shamir transform".)

The proof system is complete for a language $\mathcal{L} \in$ NP if honest provers are likely to succeed, i.e., $\forall \ell \in \mathcal{L} \, . \, \forall w \in \{0,1\}^* \, . \, \mathrm{Pr}[\mathcal{R}_\mathcal{L}(\ell,w) = 1 \, \Rightarrow \, \mathsf{out}_\mathsf{V}(\langle\mathsf{P}(\ell,w) \leftrightarrow \mathsf{V}(\ell)\rangle) = 1] \geq 1 - \mathsf{negl}(\lambda)$, for some function $\mathsf{negl}(\lambda)$ that is negligible in the security parameter.

The proof system is zero-knowledge if the transcript, i.e., the list of all exchanged messages which is denoted by $\langle\mathsf{P}(\ell,v) \leftrightarrow \mathsf{V}(\ell)\rangle$, is indistinguishable from the output of some simulator $\mathsf{S}$ that receives the string $\ell$ but not the witness $w$. Formally, $\forall \ell \in \mathcal{L} \, . \, \forall w \in \{0,1\}^* \, . \, \mathcal{R}_\mathcal{L}(\ell, w) = 1 \, \Rightarrow \, \langle\mathsf{P}(\ell,w) \leftrightarrow \mathsf{V}(\ell)\rangle \sim \mathsf{S}(\ell)$. Here $\sim$ denotes your favorite notion of indistinguishability of probability distributions, i.e., perfect, statistical, or computational.

With respect to soundness, it is important to draw a clear distinction between two related notions. First, the proof system has plain soundness if no (appropriately bounded) adversary $\mathsf{A}$ can make the verifier accept nonmembers of the language: $\forall n \not \in \mathcal{L} \, . \, \mathrm{Pr}[\mathsf{out}_\mathsf{V}(\langle \mathsf{A}(n) \leftrightarrow \mathsf{V}(n)\rangle) = 1] \leq \mathsf{negl}(\lambda)$. I call this notion plain soundness for the sake of exposition but the literature refers to it simply as soundness. Second, the proof system has knowledge-soundness if there is an (appropriately efficient) extractor machine $E$ that can extract and output a valid witness from any successful proof-forger $\mathsf{B}$, whether it receives the witness $w$ or not. Formally, $\forall \ell \in \mathcal{L} \, . \, \mathrm{Pr}[\mathsf{out}_\mathsf{V}(\langle\mathsf{B}(\ell) \leftrightarrow \mathsf{V}(\ell)\rangle) = 1 \, \Rightarrow \, \mathcal{R}_\mathcal{L}(\ell, \mathsf{E}^\mathsf{B}()) = 1] \geq \mathsf{noti}(\lambda)$, where $\mathsf{noti}(\lambda)$ is some noticeable function of the security parameter. Here $\mathsf{E}^\mathsf{B}$ means that the algorithm $\mathsf{E}$ has black-box access to $\mathsf{B}$, meaning that $\mathsf{E}$ is allowed to interact with $\mathsf{B}$ through messages that have the format of the proof system but $\mathsf{E}$ is not allowed to view or alter $\mathsf{B}$'s state. The literature also refers to this notion as witness-extractability and, confusingly, as soundess. Proof systems with this property are proofs of knowledge.

For many languages, knowledge-soundness is the relevant property and plain soundness is not. Consider for instance the standard Schnorr proof of knowledge of a discrete logarithm, whereby knowledge of an exponent $x \in \mathbb{Z}_{|\mathbb{G}|}$ is proven such that exponentiation-by-$x$ sends $g \in \mathbb{G}$ to $X = g^x \in \mathbb{G}$. When $g$ is a generator, as it usually is, plain soundness is trivial: since $X$ is a group element it must have a discrete logarithm with respect to $g$. However, for circuit-satisfiability type languages, plain soundness is usually more important than knowledge-soundness.

To prove plain soundness, it suffices to count the number of possible challenges from the verifier that expose a cheating prover; and the number of possible challenges that allow him to get away with the fraud. The ratio between the number of challenges that do not expose the cheating prover and the total number is known as the soundness error --- the fact that the verifier chooses his challenges at random makes this ratio equal the cheating prover's success probability and if it is negligible in the security parameter then plain soundness is satisfied. With the Fiat-Shamir transform, it suffices to argue from the difficulty of finding particular preimages to the random oracle. Formally, you can model the (classical) random oracle as a procedure that samples a random output only when it is needed and no sooner. Then the only way to find an input that leads to an answerable challenge is to test enough of them.

To prove knowledge-soundness, one must provide a description for the witness-extractor $\mathsf{E}$ and show that its success probability is noticeable if $\mathsf{B}$ has a noticeable success probability of convincing the verifier. The Forking Lemma provides such a description:

$\mathsf{E}$ plays the part of $\mathsf{V}$ honestly and runs the protocol with $\mathsf{B}$ thereby obtaining one transcript $T_1$.
$\mathsf{E}$ rewinds $\mathsf{B}$ to just after one of its messages, typically where it commits to something.
Once again, $\mathsf{E}$ plays the part of $\mathsf{V}$ honestly but with different randomness, thereby obtaining a second transcript $T_2$.

The language is structured in such a way that it is easy to extract a witness from two valid transcripts with the same commitments but different challenges. This description involves only one instance of rewinding; it may be necessary to rewind multiple times to obtain a set of transcripts satisfying very particular constraints.

Intuitively, the success probability of the extractor $\mathsf{E}$ should be somehow related to the success probability of the proof-forger $\mathsf{B}$. However, Bellare and Neven show that there is necessarily a square-root security degradation. In particular, if the extractor $\mathsf{E}$ splits into 2 branches, then $\mathrm{Pr}[\mathsf{B} \, \mathit{success}] \leq \sqrt{\mathrm{Pr}[\mathsf{E} \, \mathit{success}]}$, because the proof-forger $\mathsf{B}$ has to be successful in both branches. This means that even if the discrete logarithm problem takes $2^{128}$ units of work to compute, the proof shows only that the adversary as to perform at least $2^{64}$. In general, if the extraction requires $b$ branches, then the proof technique will induce a $b$th root degradation.

With the Fiat-Shamir transform, the random messages from the verifier are replaced with the response from the random oracle upon being queried with the list of protocol messages up until that point. This random oracle is simulated by the extractor $\mathsf{E}$, meaning that it can choose which responses the random oracle will provide. The trick is that by rewinding the proof-forger $\mathsf{B}$, the extractor $\mathsf{E}$ can reprogram different outputs for the random oracle. In particular, the extractor $\mathsf{E}$ proceeds as follows.

$\mathsf{E}$ runs $\mathsf{B}$ and provides it access with a random oracle $\mathsf{RO}$ whose responses are sampled uniformly at random when they are needed, and obviously conformant to the responses of previous queries. This provides the extractor $\mathsf{E}$ with the first transcript $T$.
$\mathsf{E}$ rewinds $\mathsf{B}$ to just after one of its messages, typically where it commits to something. Note that the list of all messages up until this point is fixed; denote this list by $L$.
$\mathsf{E}$ replays $\mathsf{B}$ again from this point but provides it with access to a random oracle $\mathsf{RO}'$ whose only difference is its response to $L$. In particular, this response has been sampled at random. This second execution of $\mathsf{B}$ provides $\mathsf{E}$ with the second transcript $T_2$.

With $T_1$ and $T_2$, the extractor $\mathsf{E}$ should be able to extract the witness. If more transcripts are needed then the extractor rewinds and replays the proof-forger as often as necessary.


How does the key size in supersingular isogeny schemes relate to their security level?

Those numbers for the key sizes come from the bit length of the prime chosen for the finite field $F_p$.  To clarify, there are no complex numbers used at all.  The elliptic curve is over a quadratic extension of $F_p$, i.e. $K = F_{p^2}$, and a root $i$ of $x^2+1$ is chosen, so that elements of $K$ can be represented as uniquely as elements of $F_p \oplus i\cdot F_p$, i.e. $a+ib$ for $a,b\in F_p$.  If $p$ is $N$ bits long, then general elements of $K$ are $2N$ bits long.  Points $(x,y)$ on the elliptic curve $E$ have $x,y \in K$, so they are then $2\cdot2N = 4N$ bits long.  The coefficients of $E$ are also elements of $K$, so they're also $2N$ bits long.

The public key consists of the two $K$ coefficients to express the elliptic curve $E_A$ (so $4N$ bits), and the two points in $E_A$, $\phi_A(P_B)$ and $\phi_A(Q_B)$, which are each $4N$ bits long.  The total length of the public key is then $12N$ bits.  However, it is possible to compress this, as you can see in Costello-Longa-Naehrig, where they get this down to $6N$ with some clever techniques. Later work improves this to about $3.5N$ while reducing the computational effort at the same time.

The relationship between key size and security level is covered in section 5.1.  So far, the best classical attack is $O(\sqrt[4]{p})$, so $N/4$ bits of classical security, and the best quantum attack is $O(\sqrt[6]{p})$, so $N/6$ bits of quantum security.  That's why the 768-bit p has 768/6 = 128 bits of quantum security.  I really recommend reading Costello-Longa-Naehrig, as some of the details are made more explicit.


This sounds like "fair exchange," the subject of many good research papers. In general you need a third party to give any security guarantees, but "optimistic fair exchange" involves the third party only when one of the parties tries to cheat (i.e., when both play honestly there is no involvement from the third party).

Incidentally, Diffie-Hellman is most certainly not fair: whoever sends first lets the other party compute the key before the original sender can.


Find Lower bound on key space with relaxed definiton of perfect secrecy

I believe that this 'relaxed' definition gives the same minimal key length as the standard perfect security definition; that is, the number of keys $|K|$ must be at least as large as the number of possible plaintexts $|P|$.  This is true for any $\epsilon < 1$.

Suppose we had a set of keys that was smaller than the number of plaintexts, or $|K| < |P|$.  In that case, we pick a possible ciphertext $c$ and see that can be decrypted to at most $|K|$ distinct plaintexts (depending on the key); hence there must be a plaintext $p_0$ that it cannot decrypt to.  Let us call plaintext $p_1$ a plaintext that it can decrypt to.

Then, consider the probability distribution:

$M = p_0$ with probability $\epsilon$

$M = p_1$ with probability $1 - \epsilon$

$M$ is any other plaintext with probability 0

If we consider the equation with $m = p_0$, we have:

$Pr[ M = m | C = c ] = 0$ (because that plaintext is impossible with that ciphertext)

$Pr[ M = m ] = \epsilon$

And hence $|Pr[M=m|C=c] - Pr[M=m]| = \epsilon \not< \epsilon$, and so we find that the required inequality does not hold.

Hence, that relation can hold in general only if $|K| \ge |P|$, which is the same bound as what perfect secrecy requires.


dealing with real numbers in Integer Vector Homomorphic Encryption lib

There are several ways...

If the message space of your scheme is $\mathbb{Z}_t$, then you can

Multiply all the plaintexts by $10^k$ before encrypting them and instead of multiply those vectors by a learning rating between $0$ and $1$, multiply them by an integer learning rate between $0$ and $10^k$.
Remove the divisions and track the changes introduced by this remotion. For instance, instead of evaluate $x = \frac{c_0 + c_1}{10}$, do $y = c_0 + c_1$ and keep in mind that $y = 10x$ so you can find the right answer after decrypting. Take a look to the section 3.2 (Division-Free Integer Algorithms for Classification) of this paper...

But if the message space of the scheme you are using is (let's say) more robust, like a polynomial ring, then you can encode double values into plaintexts, which enables you to encode the learning rate, then encrypt it and finally multiply by the vector of ciphertexts.

That answer may be helpful to you.


What's the least computationally expensive way to verify a message is from who they say they are?

The first step in verifying a signature is to hash the message, which takes a few thousand x86 instructions. Your language doesn't seem to support the logical operations that are common in modern hash functions - implementing those with arithmetic operations will cost you some overhead. So you're talking about hours before you even get to the public key portion of the signature. And you can't use a weak hash function, because your attackers aren't limited to such an under-powered platform to produce their forgeries.
I question if in-game cryptography is the best solution here. Since this is all in a managed environment, it seems like you could simply disallow spoofing of the sender property of these messages.


"official" guidelines about the minimum length of a truncated hash

minimum reasonable length for a truncated hash (specifically, a truncated SHA256 hash) to ensure preimage resistance.

To answer this one might consider the attacks.

Brute-force preimage algorithm: Currently, the collective power of the BitCoin miners reached $\approx 2^{92}$ SHA-256 double hashes per year in 06 Agust 2019. If you assume that the miners double this in every year, they need 18 years to reach $2^{128}$. Though doubling every year is highly unreasonable and we don't expect that. Here, larger than 128 will be enough.

Multi-target preimage algorithm: There is also multi-target attack by using classical computing. Using Oechslin's rainbow tables on a parallel machine:

For $\mathcal{O}(2^n/t^3)$ sequential evaluation of the hash function it will require $\mathcal{O}(2^n/t)$ time if parallelized $t^2$ ways to find a preimage for the first of $t$ targets.
This really depends on the number of the target, however, with 128-bit output, for a billion targets the cost would be below $2^{100}$ and the time would be below $2^{70}$ if you truncated to 128-bit. Adjust the numbers according to your requirements.

Generic quantum preimage algorithm If ever build a quantum algorithm for Grover's algorithm it will find a pre-image in $\mathcal{O}(2^{n/2})$-time. Therefore, if you consider this target you need to double the output size like stay with around 256.

The above cost is not included the cost of the hash implementation and set times.
The hash functions, classically, recommended by the collision resistance, which hash $\mathcal{O}(\sqrt{2^n})$ by the generic birthday attack where $n$ is the output size of the hash function in bits.
Recommending a truncation for a hash function with only pre-image resistance like 100-bit is not a good idea. Since there will be some people who will use this truncated version where collision resistance is also required. The 100-bit output will have 50-bit collision resistance with 50% probability and the 50% probability for an adversary it too high, which is not negligible in some sense. One might consider, the lower probabilities.
In short, SHA256-224  is the least recommended size if you consider all available NIST hash families after the SHA-1 which has 160-bit output. Of course, for SHA256-224, the collision attack is considered, too.


Hash algorithm for converting n-bit number into another n-bit number

What you're asking for is basically a 96-bit block cipher (pseudorandom permutation) that does not have an easily computable inverse.  On the contrary, your permutation should instead be resistant to preimage attacks.

Alas, I'm not familiar with any such cryptographic primitive, or any construction that would allow one to be constructed from standard components.  (If anybody does know such a construction, I'd be quite interested to learn about it.)

In practice, I'd recommend just using a standard hash function (like SHA-256) and truncating its output to 96 bits.  In practice, you're not likely to see any collisions before the number of hashed inputs starts to approach the "birthday bound", i.e. the square root of the number of possible outputs, in your case $\sqrt{2^{96}} = 2^{48}$.  It seems very unlikely that your game would ever end up with anywhere near that many players, considering that there are less than $2^{33}$ people living on Earth.

If you want even more certainty than that, just don't truncate the hash.


I need a 64-bit cryptographic hash for 96 bits of data

If all that's known about (G,I) is stated in the question, using a hash of the concatenation of G and I, truncated to 64 bits, is a reasonable option (and I see no better one). However the risk that there is at least one collision grows fast with the number $n$ of (G,I). On the (reasonable) assumption that this hash behaves as a random function, this probability of (at least) a collision is
$$p=1-(2^{64})!/(2^{64}-n)!/2^{64\cdot n}\approx1-e^{-n\cdot(n-1)/2^{65}}\approx n\cdot(n-1)/2^{65}$$
The approximation on the right is good when $n$ is less than about $2^{30}\approx10^9$. For $n=10^9$, we get $p\approx2.7\%$. Is that acceptable? You decide.

Late addition: an attacker able to influence (G,I) could do so in a way such as to cause collisions. Against this, instead of a hash, we could use a Message Authentication Code with a secret key; problem becomes, how can a file system hide the key from attackers and still achieve media interoperability?


RSA: What happens to restrictions of plaintext n, dependent on p and q?

RSA has quite a few aspects, which are utilized implicitly, and these questions aim at those:

Concerning your first point about what happens if $x$ is not coprime to $n$, it does not compromise the correctness of the encryption and decryption, but if you find such an $x$, you also found a nontrivial factor of $n$. However, if $p$ and $q$ are prime, the probability to find such an $x$ is negligible (in the mathematical sense).
Concerning your first question, about what happens if $p$ and $q$ are not prime, is that you effectively weaken the scheme. For every known factor $f$ of $n$ you can reduce the RSA-problem into solving it in $f$ and $n/f$ and afterwards use the chinese remainder theorem to put them back together. An other minor aspect is, that finding $e$ might be more difficult (it has to be coprime to $\phi(n)$, otherwise decryption does not work any more, because it's not a bijection).
For your second question: If $p=q$, then $\phi(n)=\phi(p^2)=p(p-1)$ is not secret any more. Everyone can just compute $d$ by solving $ed=1$ mod $\phi(n)$. Effectively there is no trapdoor left anymore, which is required for a public key scheme to work.


Are DSA and ECDSA provably secure assuming DL security?

(The (EC)DSA algorithm involves two functions: (i) the "conversion function" $f$, which for the case of DSA is a modulo $q$ operation and for ECDSA is the modulo $q$ operation applied to the $x$-coordinate of the input point; and (ii) $H$ a cryptographic hash function applied to the message.)

Brown [B] showed that the DLP implies security of ECDSA in the generic group model and under idealised modelling of the conversion function $f$. The second assumption is in  particular unrealistic as in (EC)DSA it is implemented by a simple modulo operation.

There have been some recent results by Fersch et al. [FKP1,FKP2] which have tried to relax the above assumptions. In [FKP1] it is shown that under weaker (but still quite strong) assumption on the conversion function $f$ (and under some reasonable assumption on the hash function $H$) that DLP implies the security of (EC)DSA. Perhaps the security argument with the most reasonable assumptions is given in [FKP2]. There, assuming that the hash function $H$ is modelled as a random oracle, and the signer issues at most one signature per message, then EC(DSA) is unforgeable if and only if they are key-only unforgeable (this applies also to other schemes like the Russian GOST 34.14 and the Chinese SM2). It is not known if the key-only security of (EC)DSA reduces to DLP.

So, in short, the answer would be no, not under reasonable assumptions.

(Note however, that there are close variants of the (EC)DSA, most notably the Schnorr signature and the scheme by Brickell et al [B+] which do come with security reductions in the random oracle model. Also it is baffling why (EC)DSA is still in use since the patent on Schnorr expired in 2008.)

[B] Brown. Generic Groups, Collision Resistance and ECDSA.

[B+] Brickell et al. Design validations for discrete logarithm based signature schemes. PKC'00.

[FKP1] Fersch, Kiltz and Pöttering. On the Provable Security of (EC)DSA Signatures. CCS'16.

[FKP2] Fersch, Kiltz and Pöttering. On the One-Per-Message Unforgeability of (EC)DSA and its Variants. TCC'17.


Why do algebraic proofs apply to cryptography?

Integer operations as implemented on computers are isomorphic to a theoretical definition of integers. Otherwise operations would not give the correct results.

Given the terminology in your question, I suspect that when you think of integer operations on a computer, you're thinking of operations on machine words. Cryptography uses numbers that don't fit in machine words: any cryptography code that works on integers (i.e. generally speaking asymmetric cryptography) must include a bignum library (or rely on a third-party one).

Two's complement is a way to represent negative integers. It's irrelevant to cryptography because cryptography pretty much never uses negative integers: only nonnegative integers ($\mathbb{N}$, or integers modulo $n$ which are stored using their representative in the range $[0,n-1]$.

You can find a formal proof of the equivalence between Peano arithmetic and arithmetic on binary representations in many places, for example in the BitNat module of Coq.

Implementing integer operations is a non-problem as far as getting the correct result, but it does have an impact on security. If the implementation is not careful, side channels such as timing and memory access patterns may leak confidential data that compromises the security of a protocol that would be secure if the adversary could not find out any information about the intermediate values.


Period of pseudo random sequence generated from (5, 2, 0) LFSR

I believe that you're evaluating the feedback polynomial incorrectly; both in your diagram, and in the chart you have listed, it would appear that you have a feedback polynomial similar to $x^5 + x^4 + x$ (note: there are a couple of different ways to turn a feedback polynomial into an LFSR; I'm not sure which one you're intending to use).

To fix your diagram, one way to fix it is if you place the taps at $b_3$ and $b_1$ (not $b_5$ and $b_2$)


The security is considered to be proportional to the size of the keyspace. In your proposal, the keyspace is not increased by adding encryption layers since all keys are derived from a single password.
In the proposed case Hashes are not mutually independent keys since they are derived from a single password. If they are derived from separate password then the algorithm provides three-layered security
Based on the proposal, it can be inferred that the sequence of encryption and the key derivation has to be kept secret for improving security. This is Security through obscurity and is not considered as any stronger. Wiki
If the algorithm is not hidden then cascading encryption with keys derived from the same source is not adding any layers (additional time penalty to brute-force keys at each stage) therefore no better than one layer of encryption, that is the outermost layer.
It provides one layer of encryption with a strength depending on password complexity.


Public Key Encryption scheme with small messages among many parties

No, if you publish an N bit message it can hold at most N bits of information.

An N-bit accumulator value doesn't magically hold more than N bits of information in the same way a hash value does not hold the string it is calculated from. Verifying accumulator membership of a given element X requires storing a witness value for that X (essentially CurrentValue - X). Membership is tested by checking if witness + X = CurrentValue. Accumulators work only because computing a witness value for an arbitrary X is a hard problem, though such a value is guaranteed to exist.


Is it the idea to limit the result to a group?

Yes. The advantage to doing so is that we have multiplicative inverses (well, for anything relatively prime to $n$) and can therefore decrypt. It also keeps ciphertexts relatively small.

Why is there no uncertainty about the result?

There would be, except we require require plaintexts to be smaller than the modulous (i.e., part of the group). In your example, we wouldn't allow 10 to be a plaintext, because 10 is greater than 7, the modulous.

So how do you encrypt long messages? Normally, the only thing you encrypt using RSA is a symmetric key, and then encrypt your actual message using the symmetric key. Since symmetric keys are significantly shorter than RSA moduli, this isn't an issue.

We would also like to sign long messages with RSA. Therefore we typically hash the message to a digest that's shorter than the modulous, and then sign the digest. This also improves performance and stops attackers from exploiting the fact that RSA encryption is a homomorphism to forge signatures.


X9.62 Multiplying an elliptic curve point by a number

Well, you understand that Elliptic Curves define an operation on points we denote as +; that is, if $A$ and $B$ are two (not necessarily distinct) points, then $A+B$ is a third point (which will be distinct unless either $A$ or $B$ are the 'point-at-infinity'). If $A$ and $B$ are the same, the operation is usually called doubling instead of addition.

Now, by "multiplying an elliptic curve point by a number" (or point multiplication), what we mean is adding the point to itself the specified number of times.  That is:

$\displaylines{kG =}{\underbrace{G + G + G + ... + G}}$

where exactly k $G$'s are added together.

Now, the naive implementation is just to perform $k-1$ point additions; however, because the integers we're multiplying by are huge, this is not practical.

However, point addition is associative (that is, $(A+B)+C = A+(B+C)$, that means that we can use less than $k-1$ additions; for example, to compute $8G$, we can note that:

$2G = G + G$

$4G = G + G + G + G = (G + G) + (G + G) = 2G + 2G$

$8G = 4G + 4G$

and hence we've computed $8G$ using only three additions.

One straight-forward (decent, but nonoptimal) method to do this (assuming, of course, that you have already implemented the Elliptic Curve addition function) is to use the binary addition method; just note that the Wiki article talks about 'multiplication', while you're doing addition; that is merely a difference in syntax.


What is the point of using a cryptographic sequence number if you're not using it as a nonce?

After reading the draft, I think that the purpose of using a sequence number in place of a nonce is because handling nonce in practical situations is very difficult. We need to keep a directory of the used nonces and then do a search through them. You can maintain a heap for the already seen nonces, but the problem is of storing them.

In the draft it says - "The value used in the sequence number is arbitrary, but two suggestions are the time of the message's creation or a simple message counter". This gives a very clear idea that the way they want sequence numbers to be used in practice is to use them in a strictly increasing fashion so that there is no need to store all the seen values and just the latest one can be stored.
I also think that using increasing sequence numbers which wrap (start to repeat) around after a decent amount of time would also work because by the time the sequence numbers repeat, the validity of the message will long be expired.


You are right, when you're working on a finite field, you should get integer results. So let's look at why you aren't.

The problem lies in how you handle the fractions inside the equation, e.g.
$s=\frac{y_q-y_p}{x_q-x_p}$. Elliptic curve operations make use of finite field arithmetic. Maybe it'd be easier for you to grasp if you imagined the equation to look like $s=(y_q-y_p)(x_q-x_p)^{-1}\mod p$. This means that you have to calculate the modular inverse of the denominator of your fracture and then multiply this with the nominator.

$R$ is indeed part of the curve. Recalculate it using the "technique" described above.
It's not right to see it as length. As you're reducing the result modulo a prime ($\mod p$) the information which you call "length" is lost.
Take two points that are part of an elliptic curve, e.g. $P$ and $Q$. Commutative means that $P + Q$ gives the same result as $Q + P$. However it does not mean that you can just switch the $x$- and $y$-coordinates


How to find the interpolation polynomial of the DES S-boxes


Safe encryption of large files with RSA is possible. One can split the file into suitably small blocks, and encipher these individually with a safe RSA-based encryption scheme. The receiver deciphers the ciphertext blocks, and concatenates the deciphered plaintext blocks. This demonstrably is safe (in the sense that it protects the confidentiality of the large file), if the RSA-based encryption scheme is (this requires random padding, and excludes textbook RSA encryption, which allows to verify a plaintext guess).

This is however rarely done in practice because:

RSA is slow/compute intensive compared to symmetric encryption, especially for decryption; and that slowness applies to the decryption of each of the many blocks, and becomes a computational bootleneck. We are talking like 4 decimal orders of magnitude or more compared to symmetric encryption. Making the modulus larger reduces the number of blocks but worsens the problem, because RSA's execution time grows much faster than linearly with the modulus size (even much faster than quadratically, for decryption).
Safe RSA-based encryption schemes expand the size of the ciphertext. For example RSA-OAEP with SHA-256, when using 2048-bit RSA, uses 2048-bit ciphertext blocks (256 bytes) which convey at most $2048-2\cdot256-16=1520$ bits (190 bytes), loosing over 25% of the bandwidth. This can only be improved to some degree (for $n$-bit security, there must be at least $n$ bits lost per block).
RSA with long-term keys does not offer forward secrecy.

Hybrid encryption solves 1 and 2. Negotiating a session key with an appropriate protocol can solve 3.


Modes of operation that allow padding oracle attacks

In the padding oracle attack you have an oracle that only tells you whether a particular chosen ciphertext decrypts to a correctly padded plaintext. That oracle is used to build a last word oracle, which used iteratively can reveal a whole message.

The reason it works in CBC mode is that we can make predictable, arbitrary changes to the plaintext of the last block by modifying the ciphertext (of the second to last block, or the IV):

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

For another mode to be vulnerable, the same kind of control would be needed.

  It would be a surprise to me if ECB would allow padding oracle attacks that give more information than the length of the plaintext, but I'd rather be sure.

In ECB, the ciphertext only passes through the decryption function, so any change to it makes an unpredictable change to the only block of plaintext it affects.

Except, there is one predictable change we can make: we can substitute any other ciphertext block of a valid message for the last. If it passes the padding oracle, we know it ends with one of 1, 2|2, ... 16|...|16 (assuming that's the padding mode used), but we can make no other checks.

This is unlikely to help because a textual (ASCII or UTF-8) message will never include most of those – 9|...|9 (tabs) and 10|...|10 (newlines) being the only ones I could imagine seeing. In a "random" binary plaintext, it would be likely you'd see some 1s at least, but that would probably not be helpful.

Still, I guess this leaks information, so it should count as an attack.

  Question: are any other modes of operation vulnerable to padding oracle attacks?

As above, ECB is only partially vulnerable, but how about other modes?

CFB, OFB and CTR all allow predictable changes to the last plaintext block. However, they are essentially stream ciphers that don't require padding. If an implementation does use padding, it could be vulnerable. GCM is authenticated, so it doesn't leave room for the attack, and anyway also doesn't require padding.

For example, here's a padding oracle attack on $b$-byte blocksize CTR padded with $p = 1$ to $b$ bytes each equal to $p$, up to a multiple of the blocksize:

The ciphertext is simply the xor of a message and an IV-derived keystream: $C = M \oplus K$. You know the final 1-$b$ bytes of $M$ will be padding, so you can flip a single bit in the last byte, test it; the second last, test; etc. as long as the oracle returns 0. You will find the padding length, and thus know the last $p$ bytes of both $M$ ($M_i=p$) and $K$ ($K_i=C_i \oplus p$).
Set the last $p$ bytes so that they are correct for a $p+1$ byte padding (or if $p = b$, remove the last block of ciphertext). Now you can try every possible ciphertext byte in the next position ($p+1$ counting from the right). One of them will pass the oracle, returning 1. Now you know the last $p+1$ bytes of both $M$ and $K$.
You can repeat step 2. any number of times, to find the whole keystream and message.


The question performs arithmetic in ${\mathbb Z_{p-1}}^*$, the integers reduced modulo $p-1$ that are coprime with this modulus. There are $\varphi(p-1)$ of these, where $\varphi$ is the Euler totient function. It is irrelevant that $p$ is prime, and the question has little to do with integer factorization.

For any $a\in{\mathbb Z_{p-1}}^*$, the application $\scr F_a:{\mathbb Z_{p-1}}^*\to{\mathbb Z_{p-1}}^*$, $b\to x=a\cdot b\bmod(p-1)$ is a permutation of ${\mathbb Z_{p-1}}^*$ (since $a$ has a multiplicative inverse). If follows that if $b$ is uniformly random on the set ${\mathbb Z_{p-1}}^*$, then $x$ is.

Therefore, no information is learned about $\scr F_a$, thus about $a$, from any number of $x_j$ disclosed without the corresponding $b_j$ (assumed independent and uniformly random on ${\mathbb Z_{p-1}}^*$), regardless of the size of parameters or computing power of adversary.


Is there any reason not to use EdDSA with Weierstrass curves?

Strictly speaking EdDSA, as defined in "EdDSA for more curves" by Bernstein, Lange et al., can only work for (twisted) Edwards Curves.

Thus, IMHO, the correct answer your question is no.

In the paper, they define the curve parameters as being the parameters of a (twisted) Edwards curve, the addition law as the addition law on twisted Edwards curves, etc.

Note that even the base point $B$ is defined as lying on the (twisted) Edwards curve. This means that even if you have a curve birationally equivalent to a (twisted) Edwards you can't compute on the original curve, because the $R$ parameter of the signature will be a point lying on the equivalent (twisted) Edwards. (Well, of course you can convert input points on your curve and convert back the output to the twisted Edwards but this, in general, will have performance penalties)

If you, instead, allow a more elastic definition of EdDSA, then yes, the scheme is generic for any group, as Schnorr's signature scheme is (from which EdDSA is derived). The only reasons to stick to (twisted) Edwards are those related the the definition of "safe" curves used in safecurves' website, which, by the way, don't limit to the applicability of EdDSA, and are probably the reasons why the EdDSA authors restricted EdDSA to (twisted) Edwards.

I also believe EdDSA is commonly associated with Ed448 and Ed25519 because it's a new algorithm and it just has been applied to new curves.

But you can apply the same modification to Schnorr's signature scheme as done by EdDSA (e.g. use ECC, signature is $(\underline{R},\underline{S})$, use point encoding/compression, include encoded public key $\underline{A}$ in hash, have a deterministic generation of $r$, use key derivation from "secret key", etc.) without constraining to (twisted) Edwards.

Security proofs rely on the discrete log being hard. Since every curve defined over prime fields can be written in short Weierstrass form, the discrete log  can't be easier for one family of curves, so you can't loose security just by using a non twisted Edwards curve.

Note: above I used "family" to mean the curve's shape. Of course discrete log is easier, in general, for e.g. supersingular of curves (where embedding degree is $\leq 6$ allowing efficient MOV attack), but that's independent of their shape. For example: $y^2 = x^3 + x$ over $\mathbb{F}_{19}$ is supersingular and has a point $(18,6)$ of order $4$, which makes the curve birationally equivalent to an Edwards curve by Theorem 3.3 of the Twisted Edwards Curve paper


Prove that textbook RSA is susceptible to a chosen ciphertext attack

You can choose a random number r, and let $\hat{y}=y\cdot r^e \mod n$. Then, invoke the decryption query on the ciphertext $\hat{y}$ and suppose that the answer is $x'$. Then, you can extract $x=x/r\mod n$.


Is the following symmetric design secure?

Given:

The attacker can call PRP() and the inverse function prp() on any message of his choosing.
PRP is a pseudorandom permutation indistinguishable to the attacker from a random permutation.
Assuming R and K are "sufficiently large", perfectly random, and never leaked to the attacker -- in particular, during a chosen-ciphertext attack, the decryptor only gives the message M to the attacker, never leaking the value of R.

passive attacks

It appears at first glance that this construction is secure against a polynomial-time Eve, a passive eavesdropper, even under both a chosen-plaintext attack and chosen-ciphertext attack,
in the sense that the attacker can't decode any other encrypted messages
(other than the ones you allow him to decode during the chosen-ciphertext attack).

                    K
                    |
M||R----->[PRP]--->(+)---->C

active attacks

Because there is no message authentication code, an active attacker can conduct a replay attack.

If the "message" part is allowed to be short -- for example, 2 bytes long,
an attacker who can trick the system into encoding all possible 2 byte messages,
or decoding a few hundred thousand random values,
can make a collection of ciphertexts that he knows corresponds to each possible 2 byte message.
Because there is no message authentication code,
an active attacker can inject any such such message of his choosing -- "Ya", "No", "Hm", etc.

attacks on weakened variants

Alas, weakening any of the assumptions makes this almost trivial to break.

leaked R:

If R is ever leaked to a single known plaintext/ciphertext pair,
then the key can be recovered from that single message pair, allowing the attacker to decode all other messages encrypted with that key.

Key = PRP( R || plaintext ) xor ciphertext.

weak random-number generator

If the random number generator is "weak" for a single known plaintext/ciphertext message,
so it is known that the random number R for that message is one of N possibilities
(for example, if all but b bits of the number R are known,
so it is known that the random number for that message is one of 2^b = N possibilities),
and N is small enough for the attacker to try out all N possibilities,
then the attacker can narrow the key down to one of N possible keys.
With a single other known plaintext/ciphertext message, or a few more known ciphertext messages that decode to something that the attacker can recognize as plain text --
even if those other ciphertexts was built using a strongly-random number --
the attacker can narrow the possibilities down even further,
probably recovering the key.

weak PRP

If the function O() is statistically flawed,
the attacker may be able to recover the key.

For example, if the function O( R || M ) is truly awful and always returns ( R || Y),
where Y = R xor M,
then with enough ciphertext messages that were encrypted with some fixed key,
ciphertext-only techniques can be used to recover the re-used key
(see
How does one attack a two-time pad (i.e. one time pad with key reuse)?
).

other ideas

This construction reminds me of one round of a
Feistel cipher.
Perhaps a few more rounds would make it less fragile to weaknesses in the PRP and the random-number generator?

                K
                |
M||R---[PRP]---(+)--->[PRP]---->C

the Even-Mansour scheme:

        K              K
        |              |
M||R---(+)-->[PRP]--->(+)---->C

EDIT:

Rough draft of a proof

Let us imagine that Olivia implements the
random oracle
by sitting in a big isolated room with lots of filing cabinets.
Every time a piece of paper with a new red number comes in the red slot,
Olivia flips some coins to come up with a new black number.
(If that black number is the same as a black number already in her archives,
Olivia forgets that number and starts over, flipping all the coins again --
this is necessary to make this a random permutation,
rather than a random function.
).
Olivia writes down the results of the coin-flips in black ink twice --
once on a blank piece of paper that she shoves out the black slot,
and again on the incoming piece of paper next to the incoming red number,
which she then files.

When a piece of paper comes in with a previously-seen red number,
Olivia looks up that number in her files,
copies the corresponding black number to a blank piece of paper that she shoves out the black slot.

When a black number comes in the red slot, Olivia handles it similarly, writing with red ink and shoving a corresponding red number out the red slot.

Every time the the attacker feeds a red number directly to Olivia and gets the corresponding black number, if R is large and random enough, he's almost certainly getting the values of freshly-flipped coins -- practically the definition of useless information.

Every time the attacker feeds a black number directly to Olivia and gets the corresponding red number, if R is large enough, he's almost certainly getting the values of freshly-rolled dice -- practically the definition of useless information.

Every time the attacker tricks the system into encrypting some chosen-plaintext,
the system generates a fresh new random number R, Olivia flips her coins,
and the output ciphertext is the key encrypted by Olivia's new one-time coin-flips.
(Assuming R is large enough that Olivia actually does flip her coins again,
rather than re-use some previous number, the one-time-pad security proof
indicates that the attacker won't learn anything about the system key from that ciphertext).

Every time the attacker tricks the system into decrypting some chosen-ciphertext
that is different from any ciphertext generated in normal operation,
the "ciphertext" is run through the key,
again Olivia flips her coins,
and assuming the system throws away the many bits of "R" and only gives the decoded plaintext to the attacker,
the attacker only receives the values of freshly-flipped coins -- practically the definition of useless information.

user8911 pointed out a presentation about Even-Mansour:

Orr Dunkelman, Nathan Keller, and Adi Shamir.
"Minimalism in Cryptography: The Even-Mansour Scheme Revisited".
2012.

which is apparently a summary of thier paper,

Orr Dunkelman, Nathan Keller, and Adi Shamir.
"Minimalism in Cryptography: The Even-Mansour Scheme Revisited".

They prove that certain attacks require a certain number of operations.
It appears that all their proofs and attacks can be adapted to the randomized cipher machine proposed by udfrg2.
So any desired security level can be attained by fixing the message width |M| and the random width |R| wide enough.

As you may have already guessed, all these attacks rely on some kind of birthday attack --
after enough data runs through the system,
eventually the attacker gets lucky and Olivia re-uses some number rather than generating fresh coinflips.


Which cipher is used in the new 5G network?

Ericson's white paper lists them as

  The strong and well-proven security algorithms from the 4G system are reused. These are encryption algorithms based on SNOW 3G, AES-CTR, and ZUC; and integrity algorithms based on SNOW 3G, AES-CMAC, and ZUC. The main key derivation function is based on the secure HMAC-SHA-256.

Notably, all of them are stream ciphers as CTR mode converts any block cipher into a stream cipher.

SNOW 3G is a word-based synchronous stream cipher developed by Thomas Johansson and Patrik Ekdahl at Lund University.
ZUC uses a 16-stage LFSRs with each stage in $GF(2^{31}-1)$ and produces a 32-bit word on each tick.


CD

CD is collectively referring to the C and D Registers.  Their use and operation while simultaneous is independent.  C and D are concatenated together to specify PC2.

Permuted Choice 2

PC2 is a selection permutation.  You might notice that the first 24 bits of the selected Key are from the C Register (CD(1 to 28)) and the second 24 bits are from the D register (CD(29 to 56)).  The order of the selected Key bits in each have is non-linear.

The left portion of the table is recognizable as PC2 from the Digital Encryption Standard.

Permuted Choice 1

To demonstrate the how C and D Registers are concatenated we look to PC1.

The above table shows how PC1 maps a 64 bit input to the two 28 bit C and D registers from an 8 bit interface where the LSB of each input byte is a parity bit and the upper 7 bits are used as key bits loaded into the C and D Registers.  Once the C and D Registers are loaded they are independently shifted (recirculated) by either 1 position or 2 positions to distinguish each round key from it's neighbors.  Shift direction is in the opposite direction for encryption and decryption, reversing the key schedule order.

C and D operated simultaneously

The following table plotting selected Key bits versus round keys for encryption is taken from the Carl Meyers and Stephen Metyas book Cryptography, A New Dimension in Computer Security, subtitled 'A Guide for the Design and Implementation of Secure Systems', Wiley Interscience, 1982, ISBN-0-471- 04892-5.

It's generated by this answer's author from a program keytab (keytab.c, executed as keytab -s).  It demonstrates that the C and D blocks are independent that the first 24 bits of selected key are from the C Register and the last 24 bits of selected key are from the D Register.

The KS column and Bit rows demonstrate the round index and selected key bits of CD respectively.  The table is formatted to a) show that C and D recirculate independently and b) to fit in an 80 column display.

  Bit  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
KS
   1  15 18 12 25  2  6  4  1 16  7 22 11 24 20 13  5 27  9 17  8 28 21 14  3
   2  16 19 13 26  3  7  5  2 17  8 23 12 25 21 14  6 28 10 18  9  1 22 15  4
   3  18 21 15 28  5  9  7  4 19 10 25 14 27 23 16  8  2 12 20 11  3 24 17  6
   4  20 23 17  2  7 11  9  6 21 12 27 16  1 25 18 10  4 14 22 13  5 26 19  8
   5  22 25 19  4  9 13 11  8 23 14  1 18  3 27 20 12  6 16 24 15  7 28 21 10
   6  24 27 21  6 11 15 13 10 25 16  3 20  5  1 22 14  8 18 26 17  9  2 23 12
   7  26  1 23  8 13 17 15 12 27 18  5 22  7  3 24 16 10 20 28 19 11  4 25 14
   8  28  3 25 10 15 19 17 14  1 20  7 24  9  5 26 18 12 22  2 21 13  6 27 16
   9   1  4 26 11 16 20 18 15  2 21  8 25 10  6 27 19 13 23  3 22 14  7 28 17
  10   3  6 28 13 18 22 20 17  4 23 10 27 12  8  1 21 15 25  5 24 16  9  2 19
  11   5  8  2 15 20 24 22 19  6 25 12  1 14 10  3 23 17 27  7 26 18 11  4 21
  12   7 10  4 17 22 26 24 21  8 27 14  3 16 12  5 25 19  1  9 28 20 13  6 23
  13   9 12  6 19 24 28 26 23 10  1 16  5 18 14  7 27 21  3 11  2 22 15  8 25
  14  11 14  8 21 26  2 28 25 12  3 18  7 20 16  9  1 23  5 13  4 24 17 10 27
  15  13 16 10 23 28  4  2 27 14  5 20  9 22 18 11  3 25  7 15  6 26 19 12  1
  16  14 17 11 24  1  5  3 28 15  6 21 10 23 19 12  4 26  8 16  7 27 20 13  2

  Bit 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
KS
   1  42 53 32 38 48 56 31 41 52 46 34 49 45 50 40 29 35 54 47 43 51 37 30 33
   2  43 54 33 39 49 29 32 42 53 47 35 50 46 51 41 30 36 55 48 44 52 38 31 34
   3  45 56 35 41 51 31 34 44 55 49 37 52 48 53 43 32 38 29 50 46 54 40 33 36
   4  47 30 37 43 53 33 36 46 29 51 39 54 50 55 45 34 40 31 52 48 56 42 35 38
   5  49 32 39 45 55 35 38 48 31 53 41 56 52 29 47 36 42 33 54 50 30 44 37 40
   6  51 34 41 47 29 37 40 50 33 55 43 30 54 31 49 38 44 35 56 52 32 46 39 42
   7  53 36 43 49 31 39 42 52 35 29 45 32 56 33 51 40 46 37 30 54 34 48 41 44
   8  55 38 45 51 33 41 44 54 37 31 47 34 30 35 53 42 48 39 32 56 36 50 43 46
   9  56 39 46 52 34 42 45 55 38 32 48 35 31 36 54 43 49 40 33 29 37 51 44 47
  10  30 41 48 54 36 44 47 29 40 34 50 37 33 38 56 45 51 42 35 31 39 53 46 49
  11  32 43 50 56 38 46 49 31 42 36 52 39 35 40 30 47 53 44 37 33 41 55 48 51
  12  34 45 52 30 40 48 51 33 44 38 54 41 37 42 32 49 55 46 39 35 43 29 50 53
  13  36 47 54 32 42 50 53 35 46 40 56 43 39 44 34 51 29 48 41 37 45 31 52 55
  14  38 49 56 34 44 52 55 37 48 42 30 45 41 46 36 53 31 50 43 39 47 33 54 29
  15  40 51 30 36 46 54 29 39 50 44 32 47 43 48 38 55 33 52 45 41 49 35 56 31
  16  41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32

You might note that KS16 shows the values for Permuted Choice 2 from the Digital Encryption Standard. It says that decryption can occur without being preceded by a shift operation should you actually use recirculating shift registers to hold C and D registers.  The above table demonstrates simultaneous operation.

C and D used independently

The following is a description of the inputs to each S Box in the round function f(R,K), expressed in E(R) and Ks bits.

Each six bits of KS are applied to each of eight S Boxes after XOR with the matching E(R) permutation bits.  The header row shows the Column Address bits (CA) and Row Address bits (RA) applied to each S Box.

f(R,K) can actually be devolved into operations associated with a nybble register of R, borrowing Row Address R bits from adjacent nybbles via the E permutation.  C Register selected key outputs are applied to S Boxes 1 - 4, while D Register selected key outputs are applied to S Boxes 5 - 8.

DES is hardware

You shouldn't be surprised we can't describe DES without resorting to hardware terms.  There's a paper by Miles E. Smid and Dennis K. Branstad of the National Institute of Standards and Technology (NIST) entitled The Data Encryption Standard Past and Future, first appearing in Proceedings of the IEEE, vol. 76, no. 5, pp. 550-559, May 1988 (and not copyright eligible as a a U.S. government work), which makes the distinction between Basic standards, Interoperability standards, Interface standards and Implementation standards and points out that the DES is an interoperability standard.  It describes how to interconnect an 8 bit interface to the Initial Permutation, Inverse Initial Permutation and Permuted Choice 1 as well describing which bits are association in time ordered hardware operations.

The Digital Encryption Algorithm described in FIPS Pub 46 (-1, -2 and -3)
describes the hardware implementing IBM's block cipher commonly known as DES and found in U.S. patents 3,958,081 and 3,962,539. The original implementations where bounded by chip count using MSI (Medium Scale Integeration) devices.  It's easily possible today to implement shift registers with a shift of distance of one or two, or use a schedule key register file as a look up, or some other 'faster' scheme.


Is it possible to perform a length-extension attack if only the last bit of the new message changes?

No, the length extension property does not allow to compute  $H(\text{secret_key}\mathbin\|\text{timestamp}+1)$ from $H(\text{secret_key}\mathbin\|\text{timestamp})$ and $\text{timestamp}$.

Two caveats:

That's for reasonable encoding of integers to bitstring for the $\text{timestamp}$ field, including anything fixed-size, ASN.1, Integer-to-Octet-String Conversion, and any conceivable variation. Argument: the length extension property computes the hash of a message larger than the original by the padding size (at least 65-bit for SHA-256), and further that much of the extension is heavily constrained.
What's considered is not an intended use of $H$, and we have no convincing argument of security from other attacks. The academically sound thing is to use a MAC, for example HMAC with $\text{secret_key}$ as the key and $\text{timestamp}$ as the message.


Is there any way to solve for pair(x,y)?

If you're looking for an arbitrary pair, it's easy (assuming $a \ne 0$).

Pick an arbitrary $y$

Solve for $f(x) = y^3$; that'd be $x = a^{-1}(y^3 - b) \pmod{n}$

You're done.