Can an attacker predict value of $d$ if attacker already used $n$ for encryption?

Technically you're right, if you get the two prime-factors of n (p and q), then you can calculate everything else pretty easily.

But that's the problem! There is no known way to calculate p and q efficiently, but it is also unproven, if there really isn't a suitable algorithm and RSA is purposefully implemented in that way.

This is actually one of the big unsolved questions in mathematics.

See:

https://en.wikipedia.org/wiki/P_versus_NP_problem
https://en.wikipedia.org/wiki/Integer_factorization

Also your idea with storing a database of possible n's is infeasible, because this database would be unimaginably huge. You would have to store all possible calculations which would easily be greater than the number of atoms in the universe by far.


Maybe I misunderstood but it seems like you suggest hiding the encryption algorithm instead of your secret key, basically. Firstly, it is useless in any scenario that you want to send data to someone else to decrypt. If you aim to encrypt values so that only you will be able to decrypt them, think about which one is easier, hiding an algorithm from someone else or just a key?


Will rehashing an SHA256 hash continually, eventually produce every possible value?

Is it possible that hashing "foobar" recursively an infinite amount of times will eventually yield any arbitrary hash value?

I very much doubt it. A simple demonstration of this logic can be done through the birthday paradox. Suppose we log each successive recursive SHA-256 on "foobar" in a table. We can ask ourselves what the probability is that our next recursion will collide with any item already in the table?

Assuming SHA-256 behaves as a random function the probability will exceed 50% just after we've tried approximately $2^{128}$ recursions. However, since we know that SHA-256 is not actually a random function, as soon as a collision is found it will then fall in to a cycle. Thus, approximately 0% of the total hash value space will be covered.

The string "Foobar" would need to be a special case where each hash value is visited exactly once. I believe this property is called being a "generator" but I'm happy to be corrected on that point.

  Although my question is about SHA256, I'd be equally curious of other hash algorithms as well

I'd expect that this analysis would apply to any secure cryptographic hash.


The goal is to generate string password of length characters among alphabet, with uniform distribution (assuming alphabet does not contain duplicate characters), while minimizing consumption of octets drawn from a source assumed uniformly random (hereafter just octets).

A bug in the original code suppressed the first character of alphabet on the left of the generated password, creating a bias for any remaining left character.

The current code seems correct: it generates a uniform arbitrarily large integer that can be thought as index of the generated password in a lexicography sorted vector of all possible passwords, then deduce the password by expressing that integer in a base corresponding to alphabet. This is conceptually clean, but:

Contrary to the objective, it frequently over-consumes octets. The underlying cause is that Go's implementation of rand.Int(rand.Reader, max) (by crypto/rand#Int or math/big/nat#random, I can't tell) repeatedly generates a uniformly random integer less than max rounded up to the next power of two, until that integer is less than max. For a password of 2 characters among 17, 2 octets are consumed at each iteration; the average is over 3.5 octets per password; 16 octets or more are consumed over once in 336, with no upper limit.
Average execution time is quadratic with the length of the password, rather than linear for simpler algorithms. That's because cost of modular division grows linearly with the length of the number divided.
While the language Go comes with an arbitrary precision integer library, not all languages do; and languages that do (like Java) sometime are used in an environment where that library is unavailable (e.g. most Java Cards).

Unless the length of alphabet is a power of two, whatever method introducing no bias can consume unbounded octets. Proof:

Assume a method always consume at most B octets and has no bias.
There's also no bias for a method always consuming exactly B octets, obtained by throwing away octets in the end as necessary.
That method has 2B possible inputs and length(alphabet)length possible outputs. It has no bias, hence the later must divide the former.
Hence length(alphabet) must be a power of two.

It is hard to tell if the use of big makes it more or less difficult to exhibit a timing dependency or other side-channel leaking some info about the generated password.

I can't tell what RNG is actually used, much less if it is cryptographically sound and properly seeded.

A fixed-precision algorithm

Note: this is work in progress, missing an implementation (more readable to the OP), and optimizations to reduce octet consumption when len(alphabet) is large.

Here is pseudocode for a method without arbitrary precision arithmetic. It is simple, fast, yields no bias, and is competitive with the question's method on consumption of random bytes when len(alphabet)<80 (in particular, on likelihood of large over-consumption for some parameters). All variables are non-negative integers less than 256*len(alphabet) and conveniently fit integer variables.

Set $n\gets 256$
[ $n$ is the number of possible input symbols (here, bytes) ]
Set $k\gets$ len(alphabet)
[ $k$ is the number of possible output symbols]
Set $r\gets0$
Set $s\gets1$
[ $s$ is the number of possible values for randomness buffer $r$ ]
Set the password to empty
For each character to be generated
[ $r$ is uniformly random with $0\le r<s<n$ ]

While $r\ge\lfloor s/k\rfloor\cdot k$

set $r\gets r-\lfloor s/k\rfloor\cdot k$
set $s\gets s-\lfloor s/k\rfloor\cdot k$
[ $r$ is uniformly random with $0\le r<s<k$ ]
Get one new uniformly random symbol $x$
[ $x$ is uniformly random with $0\le x<n$ ]
Set $r\gets r\cdot n+x$
Set $s←s\cdot n$
[ $r$ is uniformly random with $0\le r<s<k\cdot n$ ]

Let $y\gets r\bmod k$.
[ $y$ is uniformly random with $0\le y<k$ ]
Let $r\gets \lfloor r/k\rfloor$
Let $s\gets \lfloor s/k\rfloor$
[ $r$ is uniformly random with $0\le r<s<n$ ]
Append to the password the character at index $y$ in alphabet

Proof of correctness follows from the comments and arithmetic facts. More there, including why this is economical on randomness consumed (no claim of optimality). Despite the simplicity, I fail to find a reference in the literature.

Notation: to the Go programmer, $\lfloor r/k\rfloor$ is r/k and $r\bmod k$ is r%k.

Extension: One can modify $n$ at the second bullet of step 1 (e.g. to adapt to input symbols variably chosen by dice or coin throw). One can can modify $k$ after step 4 (e.g. to generate passwords always starting with a letter then also allowing digits), but that also requires re-initializing $r$ and $s$ (which looses some randomness), or careful adjustment of these variables.

Caution: I often get my answers correct only after many revisions, and we are only at the second version of the pseudocode itself.


The "Square Root" Solution of Oblivious RAM Simulation

Presumably, the shelter could store a bunch of pairs $(a,v)$ where $v$ is the contents of the virtual word at address $a$.  Then, to scan through the shelter to see whether it has the value of the virtual word at address $i$, you'd just check whether the shelter contains any pair $(a,v)$ where $a=i$.

I don't know whether this is actually what Goldreich and Ostrovsky do, but it seems like one natural candidate scheme that could be used.


How can we reason about the cryptographic capabilities of code-breaking agencies like the NSA or GCHQ?

Applied Cryptography is book which is becoming, say, not-so-recent. NSA has quite a lot of budget, but not an infinite amount, and there are other organization, in particular big private corporation, which also have impressive means. Google or Apple, for instance, are companies with R&D activity in the area of cryptography, and who are able to potentially throw a billion dollars at a given problem (and they could probably do so with more administrative ease and flexibility than a federal agency).

Also, there has been quite some change in the area of public research on cryptography. In the early 1980s, there was a couple of conferences dedicated to cryptography; in 2011, there are more than one hundred ! The field has simply expanded, inflated, so much that no single organization, even the NSA or Microsoft or Apple, can claim employing a non-negligible proportion of the available brain resources. It is a recent change: from my own personal experience, inflation really began in earnest around 1995.

That's one thing that can be said about NSA abilities. They do not tell who they employ and what they work on; but we can estimate the probabilities of NSA having discovered advanced cryptanalytic techniques which have evaded the grasp of public academics. As Leibniz put it, discoveries are a product of ideas which are "floating around", and who will actually make the discovery is a random choice. In other words, if NSA employs 1% of the top cryptographers, then they will get 1% of the advances. Even if there is such as a thing as scientific capital (scientists work much more efficiently when they are in labs with many other scientists and a strong local tradition of working on the same subjects), it is still quite improbable that NSA is far ahead of everybody else.

Another point is about incentives. NSA is a budget sink-hole, but it has goals: namely, to protect the USA against their enemies (the rest of the World). When the NSA says that an algorithm is good (say, the AES), other US organization (both public and private) begin to use it. It is sure that NSA would like to be able to break encryption systems which are in widespread use; but, and (in my view) this is for them a much more important goal for NSA, they want the encryption that US organizations use to be unbreakable by their enemies. As such, it would make sense for NSA to promote an algorithm that they can break only if they have good reason to believe that only them can break it. NSA, like all secret services, knows what secret is: they keep their secrets, but they also assume that they do not know all about the secrets of their competitors. Correspondingly, there again, I find it implausible that NSA would know how to break AES, since they keep on brandishing it as "the solution" and there is not the slightest hint of a plan to define another symmetric encryption standard, if only as a backup.

So this is how I reason about the unknown capacities of secretive organization: I look at their resources, and I match their observable actions against their goals. Which leads to the following conclusion: if NSA can break AES, then either they have access to some non-Earth-based technology and science (a popular theme in movies, e.g. Men In Black), or they are not really trying to protect the organizations they are supposed to protect. Or both.

On the purely scientific plane, we have no proof that symmetric primitives really exist (in particular hash functions; but we do not know either if it is possible, in a Turing-said-it way, to have a symmetric cipher with an in-memory representation shorter than $\log n!$ bits: the amount of bits needed to represent a randomly selected permutation over $n$ bits). Right now we have candidates: defined block ciphers which we do not know how to break. And not block ciphers which we know cannot be broken. Therefore, there are no real "lower bounds" which would work against unknown cryptanalytic advances.


How to correctly use RSA for digital signature with hashing?

You're missing two things:

First off, we don't try to retrieve the message from the hash; as you correctly point out, that's impossible.  Instead, what we do is (using your notation):

Accept $[m,s]$
Take public key $[e,n]$
Retrieve the hashed message: $m'_{hashed} = P_a(s) = s^e \bmod(n)$
Generate the hash of the message being verified $m_{hashed} = Hash(m)$
Check authenticity of signature and message immutability by comparing $m_{hashed}$ and $m'_{hashed}$

If we assume that the hash function is collision resistant, that is, it is infeasible to find two distinct messages $M_a, M_b$ with $Hash(M_a) = Hash(M_b)$, then if $m_{hashed} = m'_{hashed}$, then either we've demonstrated a hash collision (which we assume is difficult), or $m = m'$.

The other thing you are missing is padding.  We (should) never take output of a hash function, interpret it as an integer, and hand it off to the RSA function; if we do that, then an attacker could potentially take advantage of the homomorphic property of RSA, namely, $a^e \bmod n \times b^e \bmod n \equiv (ab)^e \bmod n$, look through a pile of signatures for hashes that happen to have common factors, and cobble together a signature to a new message (whose hash is made up of those common factors).  Instead, we always apply a padding function to the hash output to turn it into a large (nearly as large as $n$) integer, and then apply the RSA function to that.

There are a number of padding methods known that are believed to be secure, including PSS and RSASSA-PKCS1-v1_5; the reference I gave you short get you started.


Why EMI/EMC testing is necessary of Cryptographic Equipment?

It’s my understanding that the information gained from a side channel attack would typically be isolated to the particular cryptographic algorithm’s structure, and physical hardware implementation. Provided the context of the article completing EMI/EMC testing would generally be a requirement of governing bodies like the Federal Communication Commission, which have jurisdiction even if the hardware is not running cryptographic systems.

So in the interest of security and responsibility it would be necessary to complete this testing to ensure that the particular cryptographic software/hardware is resistant to side channel attacks, while simultaneously maintaining compliance with regard to preventing the emission/receiving of harmful EM interference. Personally completing side channel testing adds nothing to security except to gain insight on the capabilities of a potential attacker on a particular system, because even if the system being tested is resistant to side channel attacks the tester will gain zero insight into undocumented modes of operation.


Getting the encryption method and key from the encrypted data and the raw data

There is no general method for that. Cryptography is about making it impossible in practice.

In the particular examples, it looks like "encrypted data" is encoded in Base64, as 22 characters, representing 128 arbitrary bits. From that it can't be deduced much about the scheme used.


Can a digital watermark be still extracted from the reprinted digital watermarked image?

Yes it can. But it's very difficult to resist the printing process.

You can find useful information here:
http://jultika.oulu.fi/files/isbn9789526200583.pdf


ElGamal signature - show that $(\gamma, \delta)$ signs $m$

A valid ElGamal signature satisfies, in the notation from the book you posted:

$$\beta^\gamma \gamma^\delta = \alpha^m \bmod p$$

That's just the definition of an ElGamal signature. The snippet you posted is not an example, but precisely the proof that $(\gamma, \delta)$ is a valid signature of $m = i \delta \bmod (p-1)$. On page 68 of the book, it says

  ($\gamma, \delta$) este o semnatura valida pentru x. Intr-adevar, se verifica...

(In English: "$(\gamma,\delta)$ is a valid signature for $x$. Indeed, one verifies...")

So let's step through the proof. Everything is $\bmod p$:

$$\beta^\gamma \gamma^\delta = \beta^{\alpha^i \beta^j } (\alpha^i \beta^j)^{-\alpha^i \beta^j j^{-1} }$$

(Substitution of values)

$$... = \beta^{\alpha^i \beta^j } \alpha^{-i j^{-1} \alpha^i \beta^j  } \beta^{-\alpha^i \beta^j}$$

(Just distribute the exponent across $\alpha^i$ and $\beta^j$. In the $\beta$ exponent, you get a $j j^{-1} = 1$)

$$...=  \alpha^{-i j^{-1} \alpha^i \beta^j  }$$

(The $\beta$ terms cancel out)

$$...=  \alpha^{-\gamma i j^{-1}  }$$

(definition of $\gamma$)

$$...= \alpha^m$$

(definition of $m$)

Here, $i$ and $j$ are such that $0 \leq i,j \leq p-2$. The proof you are showing is that this scheme is existentially forgeable (see page 381, Theorem 16). This is a two-parameter forgery (the $(i,j)$).


AES-128: can any two keys generate the same ciphertext from the same plaintext?

So we already know that AES-128 has, in one context, the weird property that a series of values it generates is indistinguishable from a random series of 128-bit values, with the sole exception of "but you never get a duplicate until you've hit everything". I'm wondering if it might have that property in a different direction also.

Highly unlikely.  The weird property you point out was actually a design goal of AES (actually, of any block cipher), and is fairly easily seen if you open up the hood of AES and look inside - it's the concatenation of a number of fairly trivial permutations, and concatenating permutations together always gives you a permutation.

In contrast, it was never a design goal that two different 128 bit AES keys never map the same plaintext block to the same ciphertext block; as you point out:

  But with an actual series of 128-bit random values, you'd virtually certainly get at least one duplicate by the time you did all the inputs

So, unless AES-128 has some special properties that no one (even the designers) expect, there is almost certainly two keys that map one particular plaintext block to the same ciphertext block.


The question describes a stream cipher with key $S$, using $C_S(R)$ to transmit a random session key $R$, and a keystream (or pad) generated from $R$ using a CSPRNG to encipher the message.

This is not an OTP; and contrary to an OTP, it is not secure against a computationally unbounded adversary, who hypothetically, knowing a plaintext/ciphertext pair significantly more than 128 bits, could find by enumeration the (much probably unique) $S$ that could have generated that pair, breaking the system entirely.

Another error is made in computing the risk of reusing a keystream (or pad). It raises with the number of messages. Odds of reusing the same $R$ on or before $n$ messages are
$$1-\prod_{j=0}^{n-1}\Big(1-{j\over2^{128}}\Big)$$
which for small $n$ is about $n(n-1)2^{-129}$; it that happens, the keystreams are the same, and that's detectable by the identical header, and exploitable for cryptanalysis assuming a known plaintext, or plaintext with enough redundancy.

Even for two messages, odd of key reuse are $2^{-128}$ (not $2^{-256}$), and become near $2^{-41}$ for $n=2^{44}$. Which is still perfectly fine in practice.


Why does a hacker need to crack the key to an encrypted file, instead of just brute forcing the password?

There's a few reasons.

First, most encryption doesn't rely on a password. It relies on 128-bit or 256-bit keys (for symmetric encryption at least), which are mathematically and physically outside the realm of what we consider ever possible to brute force.

Second, in systems that do derive a key from a potentially-weak password, you're right in that the password can be brute forced. However, this is why cryptographers have designed password-based key derivation functions (such as PBKDF2, scrypt, and Argon2). These impose a large computational cost upon each attempt at deriving the encryption key from the password. While it might take 500ms of computation (on a particular CPU) and 50MB of memory for a legitimate user to verify their password, this is an acceptable cost if they're only having to attempt authentication once or twice. On the other hand, this is a significant burden on someone who wants to brute force all possible combinations.


How robust is RSA-FDH against distribution bias?

Fix a number of bits $t$, e.g. $t = 2048$; consider RSA-FDH with $t$-bit modulus $n$, so that $2^{t - 1} < n < t$.  Fix a hash $H\colon \{0,1\}^* \to \{0,1\}^{t - 1}$.  Can we use $H$ for RSA-FDH, even though the literature on RSA-FDH typically posits a hash $G_n\colon \{0,1\}^* \to \mathbb Z/n\mathbb Z$?

It is not hard to define a hash $G_n\colon \{0,1\}^* \to \mathbb Z/n\mathbb Z$ with near uniform distribution using a double-length hash $H_0\colon \{0,1\}^* \to \{0,1\}^{2t}$ by $G_n(x) = H_0(x) \bmod n$; the modulo bias at this scale is negligible, just like in EdDSA's use of SHA-512 to select $k$ from $\ell \approx 2^{252}$ possibilities.

If our signature scheme were randomized, we could do rejection sampling, as phayes suggests in another answer, and attain an exactly uniform distribution—indeed, if we wanted anonymous signatures so that signatures under two keys are indistinguishable without the keys, we would have to do rejection sampling, though on the signature rather than the hash, to thwart anglophone statisticians from counting German tanks.  But this question is about the deterministic RSA-FDH.

As far as I can tell, this specific question—where $H$ covers only about half of $\mathbb Z/n\mathbb Z$—has not been addressed in the literature.  But very similar questions have been:

Tight security can be proven for deterministic Rabin–Williams signatures using $H$[1].  Although there are barriers to applying the same proof to RSA, it seems unlikely that the space covered by $H$ is one of them: they rather have to do with differences between squaring and (e.g.) cubing.  (Questions like this are part of why [1] used a single $H$ with $t$-bit codomain instead of a key-dependent $G_n$.)
Tight security can be proven for PSS signatures using a randomized hash whose most significant bit is always zero[2].  Here the randomized hash is $$P_r(m) = 0 \mathbin\| w \mathbin\| (r \oplus H_2(w)) \mathbin\| H_3(w),$$ where $w = H_1(r \mathbin\| m)$, and $H_1$, $H_2$, and $H_3$ have the right widths to make it all work out.  The proof given by Bellare and Rogaway requires $|r| \geq 128$ to provide meaningful security.
Tight security can be proven for a randomized version of FDH[3] where the randomization is appended to, rather than embedded in, the signature, like in phayes' system: a signature $(r, s)$ on $m$ under $n$ satisfies $$s^e \equiv G_n(r \mathbin\| m) \pmod n.$$  Bizarrely, this tight security works even if $|r| = 1$, even though it can be proved that deterministic RSA-FDH cannot admit such tight security[4], although that proof works only for large exponents which leaves open the possibility of tight security for $e = 3$[5] (paywall-free).  This state of affairs raises all sorts of questions about the significance of these reductions[6].

The Bellare–Rogaway 1996 proof[2] that a $q$-query forger for a trapdoor permutation signature scheme $f(s) = G_n(m)$ can be converted into an algorithm for inverting $f$ on a point $y$ works by running the forger with a derived random oracle $G'_n$ that returns $y$ on a randomly chosen one of the $q$ queries, and otherwise defers to $G_n$.  If the forger succeeds in finding a forgery $(m, s)$, there's about a $1/q$ chance that it found the preimage $s$ for our chosen point $y$ rather than for the $q - 1$ options we sent to $G_n$, and thus that $s = f^{-1}(y)$ is the desired preimage.

If we replace the equation by $f(s) = H(m)$, the reduction simply doesn't work to compute $f^{-1}(y)$ for $y \geq 2^{t - 1}$, which happens with probability less than 1/2 if $y$ is uniformly distributed in $\mathbb Z/n\mathbb Z$, so the same inversion algorithm has about a $1/(2q)$ chance of success instead.  Formally this would suggest you need to add another bit to the modulus to attain the same security—but in practical terms that bit is likely inconsequential (some practical key generation algorithms vary with a slop of a bit anyway[7]), and it remains unclear what the significance of the tightness gap is at all here when adding a single bit of randomization enables proving a theorem that eliminates the gap.

In brief, it is hard to imagine that using a hash covering only up to $t - 1$ bits, where $2^{t - 1} < n < 2^t$, could meaningfully hurt the security of RSA-FDH.  Certainly there are no known attacks like there are against biases is per-message secrets in Schnorr- and DSA-type signatures.


Breaking effort on both Weak and Strong collision resistance hash values

Basically strong collision resistance means you can't find any pair $(x,x')$ for which $h(x)=h(x')$ holds.

Weak collision resistance means that you can't find any $x'$ for all given $x$ such that $h(x)=h(x')$ holds.

To break strong collision resistance an obvious strategy is to just list a large chunk of hashes and see for any matches among them.

For weak collision resistance the obvious strategy is to take your $x$ and iterate through other potential candidates until you hit a new $x'$ which is a collision.

Obviously the former approach will lead to results before the latter.

Another illustration (which is less definition or attack-centric) is the classic one of birthdays.

Weak collision resistance essentially corresponds to finding somebody who has the exact same birthday as you have. For this you probably need to find around 200 people before chances are that you'll get a match.

Strong collision resistance on the other hand means that you meet people until any of two of them have a matching birthday. You expect this to happen with $>50\%$ probability after around 23 people.


Does the Blowfish cipher work with OFB mode?

Blowfish inputs two blocks of the same length and outputs two blocks of the same length.

That is where you are running into an issue. Blowfish inputs a single 64-bit block and outputs a single 64-bit block, just like the picture shows. All the standard 64-bit compatible block cipher modes are compatible with Blowfish.


Building a combined encryption scheme from two encryption schemes that's secure if at least on of them is secure

You can generate a random string $s_1$ as long as the plaintext. Then XOR this value with the plaintext generating $s_2$. Now encrypt both parts using $\mathrm{Enc}_1$ and $\mathrm{Enc}_2$. You need to decrypt both to XOR the two parts together again. This is similar to secret sharing where you need two parts of a key to decrypt.

If $\mathrm{Gen}_1$ and $\mathrm{Gen}_2$ are two random generators then you may want to XOR those together as well when generating $s_1$. I presume however that they are used to generate the secret keys.


Can (EC)DH keys be used as the signed content in X.509 certificates?

Yes, but it isn't that common and you may therefore have trouble finding implementations of it. Dave already pointed out in the other answer that you may need to use the OpenSSL API (which is a lower level crypto-API, not just SSL/TLS) rather than using the command line.

Please look at the following in the X509 RFC 5280:

  4.1.2.7.  Subject Public Key Info

  This field is used to carry the public key and identify the algorithm
     with which the key is used (e.g., RSA, DSA, or Diffie-Hellman) (emphasis mine).

When used with TLS:

With a static DH key you would be using ephemeral-static Diffie-Hellman. That means that such a key is normally only used to authenticate the key agreement protocol. That also means that this protocol won't be providing forward secrecy.


Is a simple stream cipher "partially homomorphic" if no integrity check is applied?

To answer your question: no this is not homomorphic encryption because one of the plaintexts is used unencrypted. There may be times when it is a useful property, but the only uses I know of it are to demonstrate the malleability of xor ciphers.

To be a homomorphic encryption function, it should be possible to calculate the encryption of some function of the plaintexts from their respective ciphertexts without using the key. That is, given $c_1=e_k(m_1)$, $c_2=e_k(m_2)$ one should be able to calculate $c_3=e_k(f(m_1,m_2))$ by evaluating some $g(c_1,c_2)$.

More generally, a homomorphism is a mathematical function that preserves some operation. For example, if an encryption scheme $e$ would be xor-homomorphic if
$$
  e(m_1)\oplus e(m_2) = e(m_1\oplus m_2)
$$

More complex schemes might commute with other operations. For example the Pallier scheme uses the fact that
$$
   a^x \cdot a^y = a^{x+y}
$$

To construct a scheme that uses multiplication of ciphertexts to calculate the sum of plaintexts.


How can I use asymmetric encryption, such as RSA, to encrypt an arbitrary length of plaintext?

The solution to this problem is to use hybrid encryption. Namely, this involves using RSA to asymmetrically encrypt a symmetric key.

Randomly generate a symmetric encryption (say AES) key and encrypt the plaintext message with it. Then, encrypt the symmetric key with RSA. Transmit both the symmetrically encrypted text as well as the asymmetrically encrypted symmetric key.

The receiver can then decrypt the RSA block, which will yield the symmetric key, allowing the symmetrically encrypted text to be decrypted.

This can be shown more formally as the following. Let $M$ be the plaintext, $K_{AES}$ be the randomly chosen AES key, and $K_{Pu}$ be the receiver's public RSA key you already have.

$$ C_1 = E_{AES}(M, K_{AES}) $$
  $$ C_2 = E_{RSA}(K_{AES}, K_{Pu}) $$

Then, send both $C_1$ and $C_2$.

Let $K_{Pr}$ be the receiver's private RSA key. The receiver can then recover $M$ as

$$ K_{AES} = D_{RSA}(C_2, K_{Pr}) $$
  $$ M = D_{AES}(C_1, K_{AES}) $$

(To allow streaming decryption or large messages, you would usually send $C_2$ first and then (the much larger) $C_1$.)


Sometimes, to make it easier to understand, the advantage is multiplied by a factor of 2: $Adv = 2|\Pr[b' = b] - 1/2|$.

Note that when the adversary has no advantage in breaking the protocol, the only thing s/he can do is guessing $b'$ at random.  In this case, $\Pr[b' = b] = 1/2$ and thus $Adv = 0$.

When the adversary always correctly finds the value of $b'$, we have $\Pr[b'=b] = 1$ and thus $Adv = 1$.

Similarly, when the adversary always incorrectly guesses the value of $b'$, we have $\Pr[b'=b] = 0$ and thus $Adv = 1$.  Note that such an adversary is as powerful that an adversary who always guesses the correct the value.  It suffices to flip the result to get the same answer.

To sum up, the advantage is a value between 0 and 1 (or 0 and 1/2 with your definition).  The higher the value is, the more powerful the adversary is.

In practice, typically, a cryptographic construction is said IND-CPA secure if $Adv < 2^{-128}$.


Definition of randomly generate in the parallelepiped

As @LeoDucas already commented, the answer is contained in Appendix E (page 22) of the same paper:


Why not to use curve over field of $p^m$ with $p > 2$ for ECDSA?

Form a mathematical point of view, one can define ECDSA over arbitrary finite fields.

Form a security point of view, the most important thing is the size of the group order.

Arithmetic is easy in the case
 $GF(p)$.

Arithmetic gets more involved for $GF(p^m), m>1$, because you have to perform polynomial divisions.

Arithmetic in $GF(2^m)$ is easy again, because the polynomial division in $GF(2^m)$ can be done by simple feedback shift registers. This makes it especially well suited for implementation in hardware.


How does Schnorr signature actually work?

Signatures do not keep the message secret.

Verification in Schnorr is by recovering $r=g^s*y^c \textrm{ mod } p$ and then checking that $c$ depends on $r$ in the right way; i.e., $c=H(r||M)$.

Efficiently generating an $s$, $c$ pair requires knowing the private key, so that raising to $s$ can cancel the $g^x$.


You don't use a pre-generated list of primes. That would make it easy to crack as you note. The algorithm you want to use would be something like this (see note 4.51 in HAC, see also an answer on crypto.SE):

Generate a random $512$ bit odd number, say $p$
Test to see if $p$ is prime; if it is, return $p$; this is expected to occur after testing about $Log(p)/2 \sim 177$ candidates
Otherwise set $p = p+2$, goto 2

There are other methods to generate primes (e.g., do step 1, if step 2 fails goto step 1). The method I outlined is what OpenSSL uses though.

For an official, public standard on RSA key generation, see FIPS 186-4, section 5.1 and Appendix B.3.1.


What is the difference between CPA and IND-CPA?

IND-CPA is equivalent to semantic security under CPA.


Understanding WannaCrypt's hybrid encryption scheme

The server will never release Spriv, it protects all ransomed clients.
Assuming the server wants to allow a given client to decrypt it's file the server will use Spriv to decrypt Cpriv and send that to the client.
With Cpriv only the paying client/victim can decrypt the various symmetric keys $K_f$ and use them to decrypt his files.

It is worth to discuss a simpler solution not mentioned in the video where all files have the same symmetric key (and different nonce/IV), and the symmetric key is encrypted directly with Spub. Such a setup will have the single client private key available on the client until encryption is done, This is problematic for the ransomware, as they want the client key to be gone from the client asap making it impossible to stop the process mid way and capture the client key. By making a separate key per file, and encrypting that with a client public key with private key long gone this is averted. Even if you catch the process half way through you can't undue what is done without interacting with the holder of Spriv(paying the ransom).

Think of all the good that could be accomplished if the clever people writing malware actually directed their skills in a positive direction?


Are there any hash functions that use integers of arbitrary bit size (e.g., int63)?

It would be possible to modify some scheme to move use 63-bit words, but that would require cryptanalysis and new choices for constants. I am not aware of any hash families that would be parametric with regard to word size and allow such uneven values.

Instead I would recommend using any existing hash that internally uses 32-bit words and that does not use many shift or rotation instructions. Modular addition, as well as bitwise operations can be computed on 63-bit values while ignoring all but the 32 low bits.

RIPEMD-160 seems like a decent candidate if 80-bit collision resistance suffices, or perhaps RIPEMD-320 if it does not. Only something like one fifth of the arithmetic instructions are rotations. Even if you need 3-4 instructions to implement rotation, the rest of the function should still dominate runtime.

Note that in the case where the limitation is due to tagged integers losing one bit, it may still be possible to do full 32-bit arithmetic, including rotations, on your 63-bit values without extra performance loss. (Depending on the interpreter/compiler.)


GCM decryption and clear text processing

TL;DR: no you should not process GCM decrypted data before the authentication tag has been verified.

GCM mode simply uses counter (CTR or SIC) mode as cipher. For the 12 byte IV you just have to create a counter by adding bytes 00000002 and start decrypting using the given key. You can see a decryption example here. It would be easy to create an example that starts at a different offset in the ciphertext / plaintext as well.

When you process the decrypted data without authentication you will expose yourself to timing attacks and plaintext oracle attacks. Any state that you keep that depends on the plaintext can be altered by an adversary; adversary can flip any bit of plaintext for unauthenticated ciphertext in CTR mode by flipping the ciphertext bit at the same offset.

How badly you are exposed depends of course on the plaintext processing used. I would not underestimate the risk though, even simple decoding of Unicode (UTF-8) characters could leak information. It could also be possible for an adversary to change the state of your service and then try to prevent rollback (e.g. by turning off the power).

You could possibly write the decrypted plaintext to a temporary file. Then you could copy the file to the final destination once the authentication has succeeded. This kind of processing can be performed without too much risk as the contents of the plaintext shouldn't influence the processing of the bytes.

Commonly this issue is sidestepped by encrypting the plaintext in chunks, verifying the authentication tag for each chunk. Note that you would need some kind of protocol to disallow reordering of the chunks - you could use the IV for that. Obviously this also requires additional space to store the authentication tag for each chunk.

And obviously these kind of changes to the protocol need to be performed during encryption; it doesn't influence existing ciphertext.

GCM mode is basically encrypt-then-MAC, where the MAC is generally faster than the CTR mode decryption. In principle it is therefore possible to verify the MAC before decryption. So in principle you could verify and then perform stream decryption, processing the bytes on the go. You would need a specialized implementation for this.

Unfortunately, passing over the same bytes twice could significantly slow down operation as well. In general you are better off trying to speed up GCM decryption in general and cache the results. You could however use this complicated scheme for memory-starved environments.


How to prove that an integer is hard to factorize when sampled from a known distribution

On trail to follow, from Handbook of Applied Cryptography fact 3.7:

Let $n$ be chosen uniformly at random form the interval $[1, x]$.

if $1/2 \leq \alpha \leq 1$, then the probability that the largest prime factor of $n$ is $\leq x^{\alpha}$ is approximately $1+ ln(\alpha)$. Thus, for example, the probability than $n$ has a prime factor $> \sqrt(x)$ is $ln(2) \approx 0.69$
The probability that the second-largest prime factor of $n$ is $\leq x^{0.2117}$ is about $1/2$.
The expected total number of prime factors of $n$ is $ln ln x + \mathbb{O}(1)$. (If $n = \prod p_i^{e_i}$, the total number of prime factors of n is $\sum e_i$.)


Purpose of using a=2 in Pollard p-1 factorization method

Shouldn't it be $\gcd(a^{B!}-1,n)$ for any arbitrary $a$.

Yes, and your code tries calculates it in the while loop. Note: normally

$$M = \prod_{\text{primes}~q \le B} q^{ \lfloor \log_q{B} \rfloor }$$ only primes which are less then or equal to $B$ constitute to $M$. The pseudocode in your slide includes all numbers $<B$ which is not correct, it must be prime less or equal to $B$.

  Why are we choosing $a=2$? is it because it is computationally cheaper to compute powers of $2$? ( left shift ).

We want a random integer $a$ that is co-prime to $n$, i.e $\gcd(a,n)=1$. If 2 is possible choice as in RSA modulus - $n$ is a product of two odd primes, it will be easy to calculate $\gcd(2^{B!}-1,n)$

  moreover, should $B$, be an upper bound of prime factor of $p-1$ or upper bound of prime factor of $p-1$ along with its powers?

$B$ is a smooth number, and in the beginning, you select any smoothness bound for $B$. From Wikipedia code;

  select a smoothness bound B
  define $M = \prod_{\text{primes}~q \le B} q^{ \lfloor \log_q{B} \rfloor }$
  randomly pick a coprime to $n$ (note: we can actually fix $a$, e.g. if $n$ is odd, then we can always select $a = 2$, random selection here is not imperative)
  compute $g = \gcd(a^M − 1, n)$ (note: exponentiation can be done modulo $n$)
  if $1 < g < n$ then return $g$
  if $g = 1$ then select a larger $B$ and go to step 2 or return failure
  if $g = n$ then select a smaller $B$ and go to step 2 or return failure

So the algorithm in sense an adaptive algorithm. In a failure either you can stop or adjust the smoothness bound.


Can I find the IV of a single block of SHA256, given the plaintext and digest?

If we how to recover the previous state of SHA-256 with less than $2^{254}$ expected effort (as measured by number of hash compression operations), then we can find SHA-256 preimages with less than $2^{256}$ expected effort, and hence would be a weakening in the expected SHA-256 cryptographical strength.

Here's how this works; suppose that we can find the previous state with expected effort $M < 2^{254}$.  Then, what we do is select two blocks (with appropriate SHA-256 padding in place for a 56 - 119 byte hash), and find the previous state for those two blocks from the target state; expected effort $2M < 2^{255}$.

Then, we would try various initial 64 byte blocks, and compute a forward hash compression operation on them (using the standard IV); we "win" if the resulting state is either of the previous states from the previous step.  If we assume that the SHA-256 hash compression functions acts like a random number, then the probability of any guess of the initial block would succeed with probability $2^{-255]$; hence this takes an expected $2^{255}$ hash compression operations.

If we find a match, we can immediately construct a message (consisting of the initial block that won, along with the final block that matched it) that SHA-256 hashes to the target value.

Total expected effort: $2M + 2^{255} < 2^{256}$

Notes:

Obviously, if $M$ is significantly less than $2^{254}$, then we'd generate considerably more than 2 final blocks and intermediate states.
I did skip over the point that it's possible that there is no intermediate state that is mapped to the final state via the message block we chose.  This would decrease the limit that $M$ can be somewhat...


Protocol for Sharing Blinding Factor with RSA

First of all, you need to understand what's the point of key blinding in the first place.

First of all, you have a server (who has a private key, and who is willing to decrypt messages), and you have a client (who has a value who he wants decrypted, but is unwilling to tell the server what that value is).  The client might not want to tell the server what the value is to preserve anonymity (e.g. Chaum's ecoin idea, which uses a similar idea with signatures), or perhaps because he is afraid that the server might leak that info (e.g. through a side-channel).

So, what the client does is pick a random value $R$ (and keeps it to himself); the encrypted message $C$, and computes $R^e \cdot C \bmod N$ (where $e, N$ are from the server's public key); we then asks the server to do an RSA decryption of that.

Then, the server computes $(R^e \cdot C)^d \bmod N = R \cdot C^d \bmod N $ ($d$ is server's private key), and sends that back to the client.

Then, the client computes $R^{-1} \bmod N$, and then $R^{-1} \cdot (R \cdot C^d) = C^d$, which is the decrypted (padded) message $P$.

Because we allow $R$ to be any value (relatively prime to $N$), then $R^e \cdot C$ can also be any value, and so the server gets no information about what he's decrypting.

With that background in mind, let us go through your questions:

  Who has control over how $R$ is chosen?

As you can see from the above example, the client does.

  If it's the client, what's preventing him from picking the same value of $R$ every time.

Absolutely nothing.  There's also nothing preventing him from publishing the value $P$ in the Times, if he were so minded.  $R$ is there to protect the client's data; if he doesn't do things correctly, it's his own data that suffers.

  Given that R must be a shared value for every encrypt/decrypt operation

Actually, if you go through the above, $R$ is used only during the decrypt operation (or the signature operation); the original encryptor (the guy who created $C = P^e$ in the first place) need not know it (or even if RSA blinding was being used).  The client needs to use the same $R$ to compute both $R^e \cdot C$ and $R^{-1} \cdot (R \cdot C^d)$, however that's both in the decryption process, and the client never needs to give $R$ to anyone else (in fact, that would rather mess up what $R$ is trying to do)


But advices received from partners and relatives encouraged me to experiment with the idea. I know that some schemes were patented in their beginning: DH, RSA, DES, NTRU, some schemes on ECC.

Note that there is considerable reluctance in significant parts of the community to use any algorithm with any intellectual property claims.  If you patent your algorithm, that pretty much guarantees that no one will use it, unless (or even if) it has very significant advantages over unburdened algorithms. For example, (EC)DSA has extra operations in it to avoid a (now expired) patent. DSA itself was introduced partly due to concerns over patents on RSA. OCB is virtually unused largely because of patents which led to the adoption of the slower CCM. Patents delayed the adoption of elliptic-curve cryptography.

However, to address your questions (and while I am not a lawyer, I do have some familiarity with how patent law works):

  Can you patent a cryptographic scheme and publish a paper opening your method entirely, which is descriptive enough, so its security can be analyzed by the cryptographic community? Could I provide an implementation of the scheme?

Absolutely; a patent (or a pending patent) does not rely on the secrecy of the invention (unlike, say, a trade secret); in fact, the entire point of the patent process is to give you an incentive to publish your invention (by giving you a monopoly on it for a limited period of time).  On the other hand, you have to do things in the correct order.  In the US, you have a year after publishing your invention to file for a patent; in Europe (and, AFAIK, the rest of the world), you don't have any grace period - once you've published, you can't file for a patent.

  Can you patent a cryptographic scheme based on an scheme/idea that was previously patented but lacks of patent nowadays, considering that this scheme is a modification of the original one?

You can, if the modification doesn't itself have prior art, and is sufficiently nonobvious to one "skilled in the art" (and, yes, that is a rather nebulous criteria).

  I've always thought that patenting make your idea less interesting or restrictive because you can't disclose any technical secret related to it, but maybe I'm wrong because I'm lacking of information.

No, after you file for your patent, you can disclose any details you want.  What makes your idea less interesting to other people is that they're concerned about the legal ramifications of using your idea (and you possibly taking them to court for patent infringement).  Now, if you release your patent for general use, that's no longer an issue for them; however it begs the question "why did you file for a patent in the first place?"


Cube-Root attack - RSA with low exponent

As you know, RSA encryption works by raising a plaintext block $p$ to some power $e$ modulo some composite modulus $n$:

$$c = p^e \pmod n$$

Now suppose $p$ and $e$ are so small that $p^e < n$. This is a disaster for Alice, because Eve can retrieve the plaintext by simply calculating the $e$-th root of $c$:

$$p = \sqrt[e]{c} \quad (\text{if }p^e < n)$$

On the other hand, if $p^e \ge n$, then $c$ will not be an exact $e$-th power. In this case, you could try adding integer multiples of $n$ to $c$ until you end up with a number that does work; i.e.,

$$p = \sqrt[e]{c + kn} \quad (\text{for some }k \in \mathbb{Z})$$

Note that this works without knowing the factors of $n$. In practical situations, RSA uses a much larger value of $e$ (usually 65537) and a much larger value of $p$ (through the use of padding), making this sort of attack impossible.

A couple of examples:

Using the same modulus and exponent:

e = 3
n = c7d6bca5802235a56df4faf08d0fb4701e9e94b886a5c3d0c6441c92e3d3a0e6
    d7549720d814961b53385dc1fbd28237b028a93c10d08b2d47bf31c8bd6f7aa8
    062c6d7479a2e12734d17d851955de11382cf42137f1fc40839df2562b7a91dc
    3b6751f6060ceb3090837d760b748997a43a01919a0c8f2c6b1bfb72653de70a
    8ae197eb1c6780a75914cdacf9aca56af35059b728584e9bb284c4791e8cfed1
    73ec641e7cc5b278ff680086b934c0abb2ec1f431b1d2173eac97019ff5100b0
    b510fc87ff47a07e7c748f67c768d7dd739adfdd7d082e933d6038ca554f3282
    d7aa9072028f4353dbef515b8eb6ff5867c039e1bd1f807a0cbed4655862060f

see if you can decipher the following:

(a) A simple example where $p^e < n$ (making the value of $n$ irrelevant):

c = 000608a5a8b32e3b218b49f9f0c33d05f135eff53dabee5ac00ec13e72997ef7
    c4b478d6b95cecc01ebcf7cecf24785ba28b4b88f605ee93d6502f24635624cc
    f4772e0d7334d125e047853c4a42e21d4bc3412729b0d230c1f5d6a2f8272bb1
    8927313328c6e431bf1e38d5200a5ac32293f4d58c467636a20bc7393d7133c3
    65880f07a2a29ad63fb21ebd2011b02dcd298fbd97c70d72fbc5c433a223987d
    898da302aa100efd95f43e7d6698a7eeea05dd97870583f149beda3aa6334ba4
    641c224e8c8f2cd61156abd42e4e3d03070c453656ec072526618e2ad74c87e8
    9c54397de803b8e2347f7daf413695e1df816782758f26a2abfe947c82ce9e9d

(b) A slightly harder one where $p^e$ is larger than $n$. You'll have to test for multiple values of $k$ to crack this one:

c = 9478dff8ca00aa472291b24a2db6288c4a865cfb53bff7c6ecb304a2d506bbbd
    16c4d26584657c17693becbdbba5a9bb18d462d72d52ae10bfe3edf906120bc2
    b0bec55f529f8eb2a0ae6cd997db467c53c463d7ed44790c7917b76dc6992a4c
    db7362e93eb3f4f2bb433d7256793a5992891a86ce87edc4234ec81e83c7ecc7
    d7659fa3639a1e299745c8ef5bd632928cb4871f19a6bd63ec974e45ac132f04
    f53f1e5c0e4a12d008783e31650816d2c78d9ec84ecd828a5ed7d915bf7a9a08
    c23ebb85e69c9c2a3bef0d4a77b28a62db65f437e019062a74891ad17c3a9c58
    ba73644a3097de31dbd5a13349f7a3f031d2352cbba680525e4249147aa58053


What is the value of Q such that Q|P-1 where P is a prime number?

It means $Q$ divides $P-1$. In other words, $P-1$ is a multiple of $Q$.


Elliptic Curve Cryptography messages vs keys encryption

Hybrid cryptosystems, as @kelala has mentioned, are used in practice in favour of public-key encryption systems. It's not a particularity of Elliptic Curve vs Integer-Group based cryptosystems: it's rather that bit-twiddling (symmetric-key) cyphers are much faster than algebraic (public-key) ones.

So, what we do is to create a symmetric key and use a public-key scheme to encrypt it in the KEM/DEM paradigm (and also 2) and then use a symmetric scheme to actually encrypt.

Also, keep in mind that even if you do encryption wholly in an Elliptic Curve, you probably need a hash function at some point that maps the text message (a sequence of bytes) to a field element or a curve point itself.
You can look up the work of Icart, Fouque, Tibouchi, Coron, Maurer and others, for examples of how to do this (depending on the curve family you're targetting)


No, it will be insecure. There are two reasons;

Due to the smaller key size 56-bit; DES was tested for brute-force attack since published.

DES_CHALL, 96 days to find the CES challenge key in 1997.

EFF DES cracker 56 hours to find the CDES challenge key in 1997.

COPACOBANA, an FPGA hardware built for attacking by brute-force for DES, can successfully find the key on average 6.4 days in 2006.
4 . Hashcat; running with two p3.16xlarge instances on AWS, one probably will find the key on average in about 0.9 days. Because that's 46G tries/second per GPU and 16 GPUs.

crack.sh can search the key in ~26 hours with a single machine.

crack.sh also produce a chosen-plaintext attack utilizing a rainbow table to recover DES key in 25 seconds in 2017.
There is a nice secret message in the DES Challange II-2 about this;

$$\text{The secret message is: It's time for those 128-, 192-, and 256-bit keys.}$$

Due to the Small 64-bit block size; DES is not secure under any modes of operation. If the attacker collects blocks encrypted under the same key in total the square root of the possible blocks, there $%50$ chance that the clock will be the same. This will leak information even CBC and OFB.For a 64-bit block cipher as DES, $\sqrt{2^{64}} = 2^{32} \times 8 \text{ B} = 32 \text{ GiB}$ space will be enough.
In our community, there are two nice questions more about the block size;

How does blocksize affect security?
Is a small size block cipher usable?

and a website Sweet32: Birthday attacks on 64-bit block ciphers in TLS and OpenVPN.


How can Cleve's 1/r lower bound on the bias of coin-flipping protocols hold if parties can output random bits?

In a multi-party protocol, if every honest party just outputs a random bit, it's likely they won't all output the same bit and the protocol would be incorrect.

With two parties, the corrupt party can still bias the output. Suppose the corrupt party aborts in the last round whenever the actual protocol output would be 1. If an abort occurs, the honest party outputs a random bit. Then we have two cases, which each occur with $1/2$ probability:

Abort, output random $b \leftarrow \{0,1\}$
No abort, output $b=0$

Clearly the probability of outputting 0 is $3/4$, so there is still bias.


Set an initialization vector to HMAC/SHA different from default in Java

Why are default values for IV (HMAC/SHA) used? What is the reason not expose them to a user?

Actually, if you go through the theoretical basis of HMAC as explored in this paper, they start with NMAC, which is essentially what you are asking for.  That is, it's a nested hash construction (just like HMAC), however instead of prepending the hash with keying material, they set the IV for both levels to keying data.

They then go on to HMAC, and show that HMAC is as secure as NMAC; the prepended keying material (which occupies precisely one hash block) sets the hash internal state to a value which is unpredictable to someone who doesn't know the key.  HMAC also has the advantage that it can be implemented using a standard hash implementation.

Hence, the answer is "you don't need to set the HMAC IV values; the HMAC keys do that for you"


Can Secure Multi-party Computation be used to reconstruct secret shares?

Sure you can.

Suppose there are $t$ shares $(x_1,y_1),\ldots,(x_t,y_t)$ hold by $t$ different parties. Recall that in Shamir secret sharing, the secret is the free coefficient in the polynomial. Then to reconstruct the secret, the parties need to compute jointly:

$$L(0) = {\sum_{j=1}^{t}} y_j \cdot l_j(0)$$

where

$$l_j(0) =\prod_{\begin{smallmatrix}1\le m\le t\\ m\neq j\end{smallmatrix}} \frac{x_m}{x_m-x_j}$$

Usually $x_1,\ldots,x_t$ are public, so all parties can compute all $l_j(0)$ locally. Then what they need to do is to share $y_j$ among them and compute $L(0)$ securely using generic secret sharing based MPC.


Are two outputs of a PRF computationally indistinguishable when using two different keys?

Computational indistinguishability is transitive, the proof can be found in these lecture notes. Informally speaking:

We have an advantage $\epsilon_1$ to distinguish distributions $X$ and $Y$, and we have an advantage $\epsilon_2$ to distinguish distibutions $Y$ and $Z$, and the triangle inequality gives us an advantage $\leq \epsilon_1 + \epsilon_2$ to distinguish $X$ and $Z$. Since both $\epsilon_1, \epsilon_2$ are negligible (to be more precise, negligible functions in some security parameter), their sum $\epsilon_1 + \epsilon_2$is also negligible.

For a pseudorandom function we know that it's indistinguishable from a random function, which is just a uniform distribution for every possible input. So both functions are indistinguishable from the same distribution, and by transitivity we get that they $f_{k_1}(.)$ and $f_{k_2}(.)$ are also indistinguishable.

Edit: This is only true for independent keys, thanks to Yehuda Lindell for pointing this out. The question states "different keys", which might not fulfill this requirement.

If you have dependent keys, then indistinguishability does not necessarily hold. Specifically, let $F$ be a pseudorandom function. Define $F'$ as follows: if the key $k$ is even then define $F'_k(x)=F_k(x)$; else, if $k$ is odd, then define $F'_k(x)=F_{k+1}(x)$. It is possible to prove formally (by reduction) that if $F$ is a pseudorandom function then so is $F'$. Now, consider the case that you are given $k_1,k_2$ with $k_2= k_1 + 1$. Then, with probability $1/2$ it holds that $k_1$ is even. In this case, it follows that $F'_{k_1}(x)=F'_{k_2}(x)$. Thus, $F'_{k_1}(x)\|F'_{k_2}(x)$ is not a pseudorandom string.

Under some related-key assumptions you could prove something, but this isn't standard. It's also probably beyond the scope of this question anyway.


Reusing IV but still generating different code?

The properties of CBC mode are only specific to when you are actually using a key and IV as specified for AES-CBC. That means, using a 128, 192 or 256 bit key - commonly specified as 16, 24 or 32 bytes - and a 128 bit key - as 16 bytes. Many tools allow other parameters such as passwords instead. Some tools, especially online tools, forget to mention that they allow different parameters than a direct key and IV, because they have been written by utter tools.

If you're using a password instead of a key it is likely that a password based key derivation method is used to derive the key. These PBKDF's commonly use a random salt and likely an work factor or iteration count. Because the salt differs each time, the derived key will differ each time as well. So in that case it doesn't matter that your IV is the same twice.

Similarly, if you specify an IV of less than 16 bytes it is likely that memory beyond the IV is used and that the result differs. However, in that case you would not be able to decrypt the first block correctly.

OpenSSL command line - by default - uses it's own PBKDF called EVP_BytesToKey using an (insecure) single iteration and an 8 byte salt. You can see this if you look at the header, as the first bytes spell Salted__ followed by an 8 byte salt (which is indistinguishable from the rest of the ciphertext).

If you want to use CBC as it is specified, you have to use the (uppercase) -K and (lowercase) -iv option and use 32, 48 or 64 hexadecimal digits for the key and 32 hexadecimal digits for the IV. These are hexadecimal representations of the binary key and IV - they are decoded by openssl to bytes before they are used.

So try something like:

openssl enc -aes-128-cbc -e -in text1.txt -out text2.txt -K '000102030405060708090A0B0C0D0E0F' -iv '000102030405060708090A0B0C0D0E0F'

instead. With whatever keys and IV's you want to try, of course.


AES-CTR uses a nonce - a number used once - rather than an IV for creating the initial counter value. This nonce is actually just an octet stream / byte array rather than a number; you could think of it as an encoded unsigned number.

So in principle, CTR mode doesn't require an IV. However, as there are many ways of creating the initial counter value, most implementations simply allow the user to provide it for them. This then is usually called "the IV", as it is called that in other modes of operation such as CBC.

Generally however the full IV is not random; only the first (leftmost) bytes that are part of the nonce are random, if the a random nonce is used at all.

  For example, I'm using AES-CTR.

As each mode uses the IV differently, I'll just focus on AES-CTR.

  I use fixed (random generated) key and random IV.

So that's a bad idea, I would only randomize part of the IV if CTR mode is used. Using a random key is fine of course.

  I know that I have to encrypt key but I don't know about IV.

You only encrypt a key if you need to establish a key with a receiver and store it with the ciphertext, or to protect it locally. But in the end, you cannot encrypt all keys as every encryption will require another key...

You should never ever encrypt an IV and include it in your question. In AES-CTR the encrypted IV would be identical to the first block of the generated key stream that is XOR'ed with the first plaintext block. If you XOR the encrypted IV with the first ciphertext block you would get back the plaintext block. Never-ever encrypt the IV with the key used for the cipher mode itself.

  If I will encrypt 1 block of data with fixed key and first IV.

For AES-CTR the IV will be the first counter block, as indicated in the first part of my answer. There is only one Initialization Vector per message. So there is no such thing as a "first IV" - and definitely not a "second IV".

  then encrypt another block of data with fixed key and second IV

The definition of AES-CTR is that you encrypt the next block of data with the second counter block value, and then XOR it with the plaintext.

If you mean a block of data from a second message, then encrypting with a second random IV is likely secure, but see the description above w.r.t. creating the IV values and remind yourself that collisions may occur if you encrypt many messages this way, as random IVs are vulnerable to the birthday problem (i.e. you may get a collision sooner than you would generally expect).

  - does this violate the security of AES-CTR?

So no, unless...


Any famous approach for analyzing the randomness of data?

In terms of a measure of randomness, the usually accepted measure is Shannon entropy. In this sense for example 2 random bits which are 00 1/2 of the time, 01 1/4 of the time, 10 1/8 of the time and 11 1/8 of the time would represent 1.75 bits of random (from $\frac12+2\times\frac14+3\times\frac18+3\times\frac18$).
In your example then, if we sample $N$ bytes and byte $i$ comes up $b_i$ times we compute $p_i=b_i/N$ and then sum
$$-\sum_ip_i\log_{256}p_i$$
and that is the "proportion" of a byte's worth of random that you are getting with each byte. By taking $N$ larger you get a tighter confidence interval for your estimate and I'll defer to better statisticians on the details.
BUT note that if you generate bytes just by listing them 0, 1, 2,..., 255, 0, 1, 2... then this will score (very close to) 1 even though most people would say this is not very random at all.
For a measure of how likely a sample is to be producing uniform random bytes, you should perform a Pearson $\chi^2$ test on the data.
For more general randomness tests also consider Marsaglia's Diehard tests.


MD-compliant hashes don't really accept arbitary length input, do they?

It depends on the exact Merkle-Damgaard hash.

MD5 will literally take an arbitrary length; that's because the value placed in the padding is actually computed modulo $2^{64}$.

For SHA-1 and the SHA-2 hashes, yes, you are correct; there is an upper bound on the length of the preimages that could potentially be hashed; for SHA-1, SHA-224 and SHA-256, it's $2^{64}-1$ bits; for SHA-384, SHA-512, SHA-512/224 and SHA-512/256, it's $2^{128}-1$ bits.

On the other hand, for all practical purposes, these limits are effectively infinite.  For example, with SHA-1, the limit of $2^{64}-1$ bits, that's $2^{55}$ blocks; even if we were able to the compression function in 10nsec, that means it'd take us over 10 years to hash a single value that size.  It's unlikely that anyone would actually attempt that.


Is this distributed random oracle scheme safe?

Attackers can choose their $M_0, m_0$ pair without solving DLP.

In particular, they generate multiple lists of $M, m$ pairs and try to solve for $l_1 \cdot M_1 + l_2 \cdot M_2 + ... + l_n \cdot M_n = M_0$.

In order to solve this, they no longer have $m_i$ for some $i$. The k-sums algorithm is effectively solving $l_1 \cdot M_1 + l_2 \cdot M_2 + ... + l_n \cdot (M_n - M_0) = 0$.

In this way, they can choose the final value ($M_0$), but are unable to recover anyone else's private values (an $m_i$ that the attacker doesn't own).

This shouldn't an issue for signatures (when computing the nonce) because the signature can never be computed without all the $m_i$. But it won't be secure for other applications.

However, there's another attack, presented in section 4 of https://eprint.iacr.org/2018/417.pdf. This attack relies on multiple parallel signature operations. Note that this attack still works with different messages even though it is only presented with the same message.

Suppose that $i$ indexes the participants and $j$ indexes the messages so that $M_j$ refers to the nonce of the jth message and $M_{ji}$ refers to ith participant's public value used to interpolate for $M_j$. In this attack, the attacker is searching for $M_{ji}$ and $a$ such that $a \cdot \Sigma H(Y||M_j||B) = H(Y||M||B^*)$, where $B^*$ is the message they want to sign.

The generalized birthday attack provides a somewhat efficient way to solve for these $j+1$ unknowns. For example, with a 256-bit hash and 127 parallel signatures, the equation can be solved in $O(2^{47})$, which is significantly less than the complexity of breaking the hash or solving the discrete log.


Is the following PAKE protocol UC secure?

You're right that it's not UC-secure, for exactly the reason you say. It allows offline dictionary attacks. Here's how that problem manifests in the UC model:
Consider this particular environment:

Environment chooses honest party's password $pw$ uniformly from some known  polynomial-size dictionary $\mathcal D$ (without loss of generality $\mathcal{D} = \{1, \ldots, m\}$.
Environment initiates the protocol and waits for honest party to report an output $K^*$
Environment requests from the adversary a sequence $k_1, \ldots, k_m$. The adversary wins the game if $k_{pw} = K^*$.

It is easy for an adversary to win this game in the real world interaction with probability one. The adversary sets $k_i = \mathcal{O}(i,r,r')$.
It is also not hard to see that no adversary can win this game in the ideal world interaction with probability better than $1/m + 1/2^\ell$ (where $\ell$ is the output length of $\mathcal{O}$). Observe the following:

The only way to get the honest party to report output in the ideal world is for the simulator to initiate an online password guess.
Since the honest $pw$ is uniform in $\mathcal{D}$, the probability of this guess being correct is $1/m$.
Assuming the online guess is incorrect, the functionality delivers a totally uniform/independent value $K^*$ to the honest party. In particular, $K^*$ is independent of whatever $k_{pw}$ value that the adversary sends to the environment. So it can match only with probability $1/2^\ell$.

I think the essence of your question relates to the fact that extraction has to happen at the time of the protocol execution (that's what makes it an online password guess).
In this protocol, as soon as the parties have exchanged $r$ and $r'$, the real-world honest party will output a key, so the simulator will need to send a password guess to make the same thing happen in the ideal world.
But what if the adversary hasn't even queried $\mathcal{O}$ yet -- what will the simulator do?
This protocol fails to limit the adversary to one password guess (every time it queries $\mathcal{O}(pw',r,r')$ the simulator would have to know whether $pw'$ is correct, in order to produce a consistent response), and it fails to limit that password guess to the period of time that the protocol is running.


What are coding schemes for timing channels

I am not sure if this is what you are looking for, however, the information theoretic capacity of a timing channel, where delays are manipulated, has been defined and analyzed in a number of papers, by using the Shannon formalism of maximizing the common information between the input and output to obtain/bound the capacity.

There is a tutorial which can get you started here. I am unsure if this tutorial is refereed or not, but it seems to introduce the basic concepts gently.

Basically you consider a queuing system such as ./G/1 (single server, general service time distribution) or ./M/1 (single server, exponential service time) and you manipulate the input arrival distribution to maximize the common information $I(X;Y)$ between the input $X$ and the output $Y$.

The first paper in this area was

V. Anantharam, S. Verdu, “Bits through queues”, IEEE. Trans. Inform. Theory, Vol. 42, No. 1, Jan, 1996

Also, if $C(\lambda)$ is the capacity of the pure timing channel, the quantity
$$
C_I = sup_{\lambda \leq \mu}≤[C(\lambda) + λC_0]
$$
where $C_0$ is the information capacity of the information channel, may indeed be related to the question you asked, about not just delays, but permutations of "marked(?)" packets/impulses in some fashion.

Chasing the references to the Anantharam/Verdu paper is probably a good idea.


How do you prove that if f(x) and g(x) are negligible, then f(x)/g(x) is not?

This is false, take $f(x) = 2^{-2x}$ and $g(x) = 2^{-x}$.


Alice and Bob choose their secret scalars $a,b \in \{0,1\}^{|p|}$.
They compute their public keys $Ga$ and $Gb$ and send the public key to the other.
Alice computes the shared key $k = \text{kdf}(Gba)$ and Bob computes the shared key $k = \text{kdf}(Gab)$.

They can use this established key $k$ as their shared symmetric key. I.e. Use it as the key for AES-PMAC-SIV to send variable-length messages that are both authenticated end encrypted.

Eve is allowed to learn all public keys and ciphertexts. Assuming that at least the Computation Diffie-Hellman and Discrete Logarithm problems are hard, then she cannot recover the shared key.


How can I take advantage of repeated patterns in non random RSA prime factors?

Theorem 1 of "Implicit Factoring with Shared Most Significant and Middle_Bits" by Jean-Charles Faugère, Raphaël Marinier, Guénaël Renault from 2010 deals with factoring products of two primes where some fraction of the MSBs are common to one of the primes in each of the composites. If I read their bounds correctly, their method must only be useful for quite unbalanced primes.

"Let $N_1=p_1*q_1,N_2=p_2*q_2$ be two n-bit RSA moduli, where the $q_i$s are $\alpha$-bit primes and the $p_i$s are primes that share the $t$-most significant bits, If $t>2*\alpha+3$ then $N_1$ and $N_2$ can be factored in time quadratic in $n$"


NIZK proof for Order-preserving encryption

You cannot prove that a ciphertext (produced by an order-preserving encryption scheme) encrypts a particularly plaintext in zero-knowledge, because verification of such a proof would necessarily leak the plaintext.

Perhaps you want to instead prove that the ciphertext is well-formed (i.e., produced by the scheme)? This is possible in the context of site's definition of [OPE][1], namely, a method of encrypting data so that it's possible to make efficient inequality comparisons on the encrypted items without decrypting them, since El Gamal conforms to this definition (see [plaintext equality tests][2]), and NIZK proof systems can be used to prove various properties about El Gamal ciphertexts.

EDIT. The comments note that:

I assumed (possibly incorrectly) that the message was not to be revealed, and
The site's definition of OPE is incomplete.

I've proposed an edit to the site's definition of OPE. This answer only applies to the original definition.


Why does solving the underlying polynomial system "break" the multivariate cryptosystem

Multivariate cryptographic schemes that perform digital signatures like HFEv, FLASH and Quartz have something in common. As opposed to enciphering data like in a normal cryptosystem where a public multivariate polynomial $P(X)$ is given as:
$$P(X) = P(p_1(x_1,\ldots,x_n),\ldots,p_n(x_1,\ldots,x_n))$$
You input the plaintext bits $x=(x_1,\ldots,x_n)$ into $P(X)$ right? Well when dealing with digital signatures we do the opposite. This is, as we are the owners of the construction, given $Y=H(m || salt)$ where $m$ is a message, we can find the plaintext tuple that sends $X$ to $Y=H(m || salt)$ by inverting the construction:
$$X=P(Y)^{-1} = S^{-1} \circ \varphi^{-1} \circ F^{-1} \circ \varphi \circ T^{-1}(Y)$$
which clearly yields $X$ such that $P(X)=Y$. Now Alice sends the tuple $(m,salt, Y,X)$ and Bob verifies as $P(X)=Y=H(m||salt)$.
Thus if Eve wants to forge digital signatures to trick Bob into thinking she's Alice, Eve must solve either the $\mathcal{MQ}$-Problem or the Isomorphism of Polynomials ($\mathcal{IP}$) which both are reasonably hard.


Is this method of string encrypting "uncrackable"?

What you describe is a sightly convoluted version of a substitution cypher.  Every letter in the plaintext is replaced with an integer in the cyphertext.  If I have two 'e's, both will encode to the same value.

Unfortunately, in this case, the algorithm is far from uncrackable. There's a famous phrase, "Anyone can create an encryption algorithm so complicated that even they cannot crack it." This is one of those cases.  All substitution cyphers fall victim to statistical analysis.  If you have any information as to the statistical likelyhood of letters or words, you can rather rapidly deduce the keys.  This kind of cypher was considered unbreakable in the era of Caesar, but since the formalization of probability in the 1600's, this kind of encryption is considered "fully broken."

The fastest approach to break this algorithm is to gather enough characters to be confident that you have two sequential characters (such as an 'a' and a 'b'   or a 'g' and an 'h').  This can be guaranteed in 14 unique characters if you limit yourself to uppercase letters, or 129 characters if you have the entire 8-bit ASCII space at your disposal (the pigeonhole principle guarantees that if you have that many characters, at least one pair of them must be sequential).  Once you have enough characters, simply sort them and find the smallest gap.  The letters with the smallest gap between them are sequential.  Once you have those two, you can do simple algebra to get the two keys.

If you attempt to avoid this hole by only using half of the alphabet (acegikmoprtvxz, for instance), the attacker will see gibberish if they make this attack.  When they realize this, they can simply look at multiples of the key they generated until the messages start making sense.


what is the relationship between epsilon and sensitivity in the Differential-Privacy?

I'll answer the second question first. The two are distinct concepts — there's no way directly compare graphs or results without more info or context.

Differential privacy is usually obtained by 1. computing a function $F$ of the data and 2. adding some noise to the result. The noise must be large enough to hide an individual contribution, and "how well an individual contribution is hidden" is captured by the parameter $\varepsilon$.

But for some functions $F$, an individual contribution can change the true result more than for others functions. For example:

The answer to "how many employees of this company have blue eyes?" can only change by one if you add or remove an employee.
The answer to "what's the average salary of people in this company?" can change by a lot if you remove the CEO's salary.

That concept is captured by sensitivity: the higher the possible change, the higher the sensitivity. And typically, to get $\varepsilon$-differential privacy with a fixed $\varepsilon$, you have to add more noise when the sensitivity is larger (to compensate). That's the typical relationship between the two concepts.


PBEWithMD5AndDES Cipher does not check for integrity first?

Password-based encryption uses a hash function to derive a key from a password and that is the only use of a hash function. PBEWithMD5AndDES itself doesn't provide any authentication (includes integrity) and only uses MD5 for key derivation.

If you want authentication, then you can still use PBEWithMD5AndDES, but you then would have to derive a MAC key from the password yourself and generate an authentication tag by running HMAC(ciphertext, macKey).

But it is not recommended to use DES or even MD5 nowadays, so you should change the encryption scheme nevertheless. If you do, then you can exchange it with AES-GCM which already provides authentication. You still would need to derive a key from a password that you provide. There are many key-derivation functions, but Java provides PBKDF2 in the standard library. Alternatives are scrypt, bcrypt and Argon2.


Question on Miller's algorithm (change the input m)

Consider the rational functions $f_P^k$ and $f_P'$. Since $\operatorname{div}$ is a homomorphism of semigroups (i.e. $\operatorname{div}(fg)=\operatorname{div}f+\operatorname{div}g$), we have
$$\operatorname{div}(f_P^k)=k\cdot\operatorname{div}f_P=k\cdot(m[P]-m[\mathcal O])=km[P]-km[\mathcal O]=\operatorname{div}f_P'\text.$$

Now with theorem 5.36 of "An Introduction to Mathematical Cryptography", this implies that there is a nonzero constant $c$ (from the base field) such that
$$f_P^k=cf_P'\text,$$
therefore the answer to your question is: Up to multiplication by a nonzero constant, $f_P'$ is the $k$th power of $f_P$, and this carries over to the result of evaluating these functions at some point, that is $f_P(Q)^k=cf_P'(Q)$.


Can adding nonces make challenge response authentications weaker?

This is vulnerable to a length extension attack. Given a valid nonce/MAC, the nonce can be extended to forge a new valid nonce/MAC value. This is because $m_4$ is appended to the end inside the outer hash.

How this affects you will depend on how you validate your nonce. But in general, this is not a secure construction.

There's probably more things wrong with it, but this was the one that stood out the most to me.

  Now The Architect™ suggested "Let us put a few more nonces in there, more randomness does not hurt."

Don't fall for this. Saying doing X doesn't hurt is NOT a valid reason do it. You'll end up buying yourself nothing, and possibly decreasing security. And it's also not a standard algorithm, so it won't exist in any programming libraries.


Reusing PGP key when generating SSL Certificate Authority?

No, in general re-using keys is not advisable. Even if you would have a secure token then it would be better to have multiple keys stored in it.

In general the level of security required for certificate authorities is higher than the security required for personal use of a key. If you later want to your CA key within a smart card or HSM then it should also be able to perform your PGP operations. This is not that likely.

You will have the same issue if you want to revoke your CA or private key; keeping a key operational after revoking it for one particular use is not good practice. So a revocation of the key for one use should (and hopefully would) imply revoking it for the other use as well. One good reason of revocation would be to use a key of a larger size for one of the two protocols.

Then there is the problem that some protocols may interact with other protocols, as CodesInChaos already stipulated. It may also be that some protocols are less safe than others. For instance, decryption with an RSA private key is generally considered less secure than performing a signature generation (in general, an attacker has more influence on the ciphertext). So it is common practice to separate encryption and signing keys - see e.g. the key usage attributes in X5.09v3 certificates.

Maybe you could deploy the same access mechanism for the keys though.

Almost forgot: yes, it is possible. RSA keys are generally the same for most protocols - it could be that it is not advisable to have a very short public exponent (say, the value 2 or 3) for some protocols, but that's about it.


What's the ASN.1 structure of ECIES encryption result?

The public key structure is an X.509 SubjectPublicKeyInfo for ECC (public) key, using explicit format instead of (more common and popular) 'named' format. SPKI is a generic ASN.1 structure that supports multiple (and extensible) algorithms:

SEQUENCE {
    AlgorithmIdentifier = SEQUENCE {
        algorithm: OBJECT IDENTIFIER -- identifies the algorithm
        parameters: ASN.1 type and content varies depending on algorithm
    }
    publickey: BITSTRING -- content varies depending on algorithm
}

The algorithm-dependent parts for ECC are detailed in rfc3279 section 2.3.5 and yours has an explicit description of a curve over a prime field with 256-bit prime beginning 8542 in hex, coefficients beginning 7879 and 63e4, base point with X coordinate beginning 421d, and claimed order slightly less than the prime
but cofactor 4 which doesn't make sense to me; and a public key/point on that curve with X coordinate beginning 0ae4.

SPKI is the format Java crypto calls 'X.509' (X509EncodedKeySpec) and OpenSSL calls PUBKEY.

The BouncyCastle IES output is created at the end of encryptBlock in the source here for org.bouncycastle.crypto.engines.IESEngine as the concatenation of 'V' the sender's ephemeral public key, 'C' the ciphertext, and 'T' the MAC tag, without any delimiters or other added structure. Your posted value is 91 bytes, beginning 04 meaning uncompressed, and for a 256-bit curve uncompressed V is 65 bytes, leaving 26 for ciphertext plus MAC, which seems unlikely; could your data be truncated or otherwise damaged?


In theory, it is not:

TOTP, like HOTP, is based on a Hash-based message authentication code (HMAC),
which in turn relies on a cryptographic hash.

Both the key, and the HMAC message (a time counter in TOTP) are hashed using the specified cryptographic hash.

One key goal of cryptographic hashes is:

it should be infeasible to generate a message that has a given hash

By definition, TOTP uses the SHA-1 hash function, which can be considered reasonably secure in this context.
Thus, it is impossible to determine either the key, or the time counter from just the hash value, even less so from the TOTP result, which is only a truncated part of the hash value.

In practice, maybe:

If you know the key you can itterate through a set of likely time counter values (e.g. now +/- one minute; now +/- x hours for timezone issues) and find the correct time counter value.

In fact, this is a variation of a brute force attack, with a limited set of likely inputs.


Short answer: No.

Medium-size answer: only brute-force could give you the answer, and that would take as long as the secret part is safe (=long enought)

Long answer: (not so long because it's already said in many good answers at security.stackexchange and here, too. I'll post links later).

Salts are strings appended to another string (passwords) to avoid some leaks and attacks. The salt is know, it doesn't need to be kept secret.

When you say you have a MD5 hash of some know string + secret part, what you are really saying is that you have a hash, you know the salt, and you need to know the password. Knowing all those is not a big deal, it's how hasing salt + password is supposed to work.

So you really have the original problem on "how to know a password if I know the hash?". The special points of your question is that MD5 is used (and is somehow broken, for certain properties), MD5 is too fast to be calculated so many brute-forces attempts can be made per second, and you don't say / know about how many iterations were used.

In the end, you can do some brute-force attack, probably won't be able to use rainbow tables, can use GPUs to speed up the process, but will be doing the old and good brute-force.


Can I implement key recovery without compromising security?

Delegating the decryption of encrypted data is exactly what proxy re-encryption (PRE) was designed to allow. In particular, there is a variant called time-based PRE that limits the delegation to a time period. See this paper for an example.

That doesn't really help with key recovery, though. You can encrypt the private key using a passphrase the user provides (run through a PBKDF function), but the user is still out of luck if she forgets the passphrase.


DES Encryption Algorithm all 64 bits for key instead of 56 bits

Yes, it would be more secure if they were used correctly. But as it would require a substantially different algorithm, you really would not be talking about DES anymore.

Brute forcing usually scales exponentially with the size of the key. However, if the algorithm is substantially altered then it is required to analyze the algorithm again.

Note that AES is both faster and stronger than DES. There is no need to (substantially) alter DES now there are many better algorithms available.

(Triple) DES is mainly used for backwards compatibility now. The keysize of DES is too small key size to be of practical use; triple DES has a blocksize that is too small to be used for uses in modern modes of encryption (CTR, GCM etc).


Are there any public-key encryption schemes based on DLog?

It is a major open research question whether such a scheme exists, and how to construct one (see, for example, Open Problem 9.10). Of course, we do have schemes like (hashed) ElGamal, which are based on the conjectured hardness of the (computational or decisional) Diffie-Hellman problem. But it is unknown whether either of these problems is equivalent to the discrete logarithm problem (except, of course, in groups where discrete log is easy).


Linear cryptanalysis and number of linear approximations

It most likely assumes both $a$ and $b$ are nonzero in
$$
a \cdot x + b\cdot y.
$$
If either are zero, the overall inear approximation will be insensitive to changes in plaintext (respectively ciphertext) making the overal linear expresion useless to mount a linear attack on a multiround cipher, since the idea is to extract subkey bits by using enough known ciphertext plaintext pairs.


Are there any tools for expressing the cipher operations as a system of equations?

Theoretically, the equations could be derived from the representation of the cipher in a hardware description language like VHDL or Verilog; you implement the cipher as if you want to make a FPGA/ASIC which runs it, but you stop at the symbolic representation of the logic gates (the "netlist"). However, I am not aware of any existing conversion tool which will transform a netlist into a sequence of equations in the right format for whatever equation solver you want to use for performing the attack.


How should I generate secure random numbers deterministically?

Your idea of using a hash function to expand your seed is a reasonable one.  If you want a standardized method of doing so, try HKDF from RFC 5869.  Specifically, I'd suggest something like the following:

PRK = HKDF-Extract("custom salt value", P)

output[i] = HKDF-Expand(PRK, string(i), 256/8)

where "custom salt value" is a unique string identifying your application and, where applicable, any other relevant context, so that reusing the same seed P in different contexts won't yield the same output.  (If you already know that the seed P is unique, entropy-dense and only known to your application, you can skip the HKDF-Extract step and just set PRK = P; see the RFC for more information.)

Of course, any other secure key derivation function, such as the counter, feedback and double-pipeline mode KDFs from NIST SP 800-108, could be used in a similar way.

Alternatively, since your seed P is a random 256-bit string, and the number of outputs you require is relatively small (≪ 264), you could simply generate your outputs using a block cipher with a 256-bit key (e.g. AES-256) in counter mode, using P as the key, e.g. like this:

output[i] = AES-256(P; 2*i) || AES-256(P; 2*i+1)

where || denotes bitstring concatenation, and AES-256(P; c) denotes the encryption of a 128-bit block encoding the counter value c with AES-256 using the key P.

Note that, since a block cipher like AES is a pseudorandom permutation, not a pseudorandom function, the output of this method will never contain duplicate blocks.  Fortunately, in your use case, this bias will not be practically detectable, since (per the birthday problem) the expected number of random 128-bit blocks one would need to observe to actually see a duplicate is approximately 264, i.e. far more than the number you intend to generate.


Are safe primes $p=2^k \pm s$ with $s$ small less recommandable than others as a discrete log modulus?

Short answer: Yes.

The discrete logarithm can be attacked in a multitude of ways: Baby-step giant-step (BSGS), Pollard's Rho, Pohlig-Hellman, and the several variants of Index Calculus, the best of which currently is the Number Field Sieve.

Let $n$ be the order of the generator of our field $\mathbb{F}_p$; it is $n = p-1$. We are trying to find $x$ given $a$ and $b=a^x$ in the above field.

Pollard's Rho and BSGS

In Baby-step giant step, we are trying to find $i$ and $j$ such that $b(a^{-m})^i = a^j$, where $m = \lceil \sqrt{n} \rceil$. Once we find such a pair, the discrete logarithm $x = i m + j$ follows, as $ b(a^{-m})^i = a^j \Leftrightarrow a^{x - m i} = a^j \Leftrightarrow x \equiv mi + j \pmod{n}$.

To do so, we first compute a table of all $a^j$ for all $j$ up to $m-1$. Then we iterate through all $i$ up to $m-1$, and compare $b(a^{-m})^i$ with $a^j$. Ignoring arithmetic costs, the runtime of this method is at most $2(m-1) = O(\sqrt{n})$ (with the same space requirements).

Due to the large space requirements, BSGS is rarely used in practice. Instead, we turn to Pollard's Rho. The crux of this method is to find a colliding nontrivial pair $(i,j)$ and $(k,l)$ such that $a^ib^j \equiv a^kb^l$. It follows that $x = \frac{k-i}{l-j} \pmod{n}$, since $a^i a^{xj} = a^k a^{xl} \Leftrightarrow a^{i + xj} = a^{k + xl} \Leftrightarrow i + xj \equiv k + xl \pmod{n}$.

So Rho comes down to finding a collision quickly. This can be done with various algorithms, Floyd's being the oldest and best known. The good news is that we can try and find a collision without an enormous table; the not so good news is that the algorithm is probabilistic, although the birthday paradox tells us we should expect a collision in about $\sqrt{n}$ steps.

In any case, these attacks are no good against a safe prime, where the order large enough that $\sqrt{n}$ is computationally unfeasible.

Pohlig-Hellman

The Pohlig-Hellman approach relies on the observation that there is an homomorphism $\phi$ from $a$ and $b$ from their group of order $n$, to the subgroup of order $p_i^{e_i}$ dividing $n$. In general, given $n = p_1^{e_1}p_2^{e_2}\ldots p_m^{e_m}$,

$$
\phi_{p_i^{e_i}}(a) = a^{n/p_i^{e_i}}
$$

This allows us to compute the discrete logarithm of $\phi_{p_i^{e_i}}(a)$ and $\phi_{p_i^{e_i}}(b)$, which really is the discrete logarithm of $a$ and $b$ modulo $p_i^{e_i}$. From this observation, it is a matter of computing the logarithm modulo all prime divisors of $n$ (using the methods in the previous section) and combining them together using the Chinese remainder theorem.

If $n$ has many small prime divisors, i.e., it is smooth, this method is very much faster than Rho or BSGS. In a safe prime, however, this is not the case, since the order $n$ is the product $2q$, for a very large $q$. Pohlig-Hellman doesn't help much here.

Index Calculus

Index Calculus is the basis for the best-performing algorithms to compute discrete logarithms modulo safe primes. Suppose we know the logarithms of $2$ and $3$; finding the logarithm of $12$ is easy: $\log_a12 = 2 log_a2 + log_a3$, since $12$ factors into $2^2\times 3$.

We can generalize this method to arbitrary elements. Start by defining the factor base, i.e., all the primes up to some bound $B$. Then, find the logarithms of all the elements of the factor base (this is the tricky part). Finally, factor $b$ into the factor base, and simply add all the logarithms corresponding to the factorization you find. If $b$ does not factor completely into the factor base, multiply $b$ by some known exponent of $a$ and try again.

Finding the logarithms of all the primes up to $B$ requires some trickery. It has two major steps:

For $k_i \in [1..n]$, find (usually by sieving) at least $\pi(B)$ elements $a^k$ that factor completely into the factor base. Store both $a^{k_i}$ and its complete factorization.
Now we have the linear system (modulo $n$):
$$
\begin{eqnarray}
e_{1,1} \log_a 2 &+& e_{1,2} \log_a 3 &+& \ldots &+& e_{1,{\pi(B)}} &=& {k_1} \\
e_{2,1} \log_a 2 &+& e_{2,2} \log_a 3 &+& \ldots &+& e_{2,{\pi(B)}} &=& {k_2} \\
&&&&\ldots&&&& \\
e_{{\pi(B)},1} \log_a 2 &+& e_{{\pi(B)},2} \log_a 3 &+& \ldots &+& e_{{\pi(B)},{\pi(B)}} &=& {k_{\pi(B)}} \\
\end{eqnarray}
$$
Solving the above linear system gives us the needed logarithms for the factor base.

The runtime of this method, for appropriate choice of $B$, is $\exp{((2+o(1)((\log n)^{1/2}(\log \log n)^{1/2}))}$. This is not strictly polynomial, but is a big improvement on the previous methods.

Number field sieve

The number field sieve is currently the best algorithm for both integer factorization and discrete logarithms over finite fields. For the discrete logarithm, it is analogous to the above index calculus, with a few major modifications:

We are working in the number fields $\mathbb{Q}[\alpha]$ and $\mathbb{Q}[\beta]$ instead of the integers; there is, however, a map from such fields to the integers under some conditions. The number fields are defined by the polynomials $f_1$ and $f_2$ of degree $d_1$ and $d_2$; there must exist an integer $m$ such that $f_1(m) = f_2(m) = 0 \pmod{p}$.
The factor base is formed by the primes in both $\mathbb{Q}[\alpha]$ and $\mathbb{Q}[\beta]$, up to bounds $B_1$ and $B_2$.
During sieving, we look for pairs $(x,y)$ such that $N_{f_1}(x + \alpha y)$ and $N_{f_2}(x + \beta y)$ are $B_1$ and $B_2$-smooth, respectively, where $N_{f_i}$ is given by
$$
N_{f_i}(x + \alpha y) = y^{d_i} f_i(x/y)
$$

The speed of the number field sieve hinges on the speed of finding $(x,y)$ with smooth norms $N_{f_i}(x,y)$. In turn, the probability of $N_{f_i}(x,y)$ being smooth is linked to its size: the smaller it is, the more likely it is to be smooth. And in turn, the size of $N_{f_i}(x,y)$ is determined by $x$ and $y$ (obviously), but also by the coefficients of $f_i$! When $f_i$ has very small coefficients, the number field sieve becomes asymptotically faster, from

$$
\exp ( (1.923 + o(1))( (\log n)^{1/3}(\log \log n)^{2/3})
$$

to

$$
\exp ( (1.526 + o(1))( (\log n)^{1/3}(\log \log n)^{2/3}).
$$

When one chooses a prime $p$ very close to $2^k$, it becomes easy to find a sparse polynomial that has a root modulo $p$. In your example, $p = 2^{2048} - 1942289$, we can find the degree $8$ polynomial

$$
x^8 - 1942289,
$$

since $2^{2048} - 1942289 = (2^{256})^8 - 1942289$. This polynomial has very small coefficients, that render the number field sieve for the discrete logarithm in this field much faster that it would be for a random 2048-bit prime.


Can somebody help me understand RC4 Spritz? (Three Questions)

The reference definition of Spritz seems to be: Ronald L. Rivest and Jacob C. N. Schuldt, Spritz - a spongy RC4-like stream cipher and hash function, presented at Charles River Crypto Day (2014).

The code snippet of the question shows how the state of Spritz repeatedly used in DBRG output mode is updated and its next output byte $z$ produced; the state being permutation $S$ coded as $N=2^8$ distinct bytes, and byte variables $i$, $j$, $k$, $z$  (in the context $w$ is a constant odd byte depending on input of the DBRG).

It seems highly unlikely that this code snippet cycles over all the $256!\times2^{4\times 8}\lesssim2^{1716}$ states, or even the $256!\times\lesssim2^{1684}$ values of permutation $S$, for the expected maximum cycle length of an iterated random mapping of a set of size $s$ is $\approx0.7825\sqrt s$. This however is not a proof.

The above leaves entirely open the possibility of analogs to Finney states of RC4 (states that would give RC4 a very short period). It seems quite plausible that there exists such short cycles, and that (contrary to Finney states for RC4) they could be reached for some inputs to Spritz used in DBRG mode. However the design of Spritz strives to make it computationally impossible to reach a desired state, thus exhibiting a state giving a short or moderate cycle (which seems quite possible) would not by itself qualify as a break of Spritz.

I found two reports of cryptanalytic attempts, but neither claims to be even close to practical for the full Spritz, or even practical for a drastically reduced version (with $N=32$ instead of $N=256$ , that is $\approx2^{320}$ potential states instead of $\approx2^{1716}$ ).

Bartosz Zoltak, Statistical weakness in Spritz against VMPC-R: in search for the RC4 replacement (IACR Cryptology ePrint Archive, 2014-12); this claims a distinguisher for a reduced Spritz with $N=16$  (that is, $\approx2^{60.25}$ states) using $\approx2^{41.4}$ bits of output. The attack is not claimed to break the full Spritz ( $N=256$ ) better than the distinguisher for $\approx2^{89}$ output bits acknowledged by the designers.
Ralph Ankele, Stefan Koelbl and Christian Rechberger, State-recovery analysis of Spritz (IACR Cryptology ePrint Archive, 2015-08); the attack is acknowledged to be entirely impractical for the full Spritz (time $2^{1400}$, reducing to $2^{99}$ for $N=32$ ).

Spritz is designed with the intend to fix the known issues in RC4, and I know knew no reason why the techniques used towards that goal would fail.

Update: there is now a true attack on Spritz: Subhadeep Banik and Takanori Isobe, Cryptanalysis of the Full Spritz Stream Cipher, in proceedings of FSE 2016.


Why does GnuPG save an array of remainders when generating prime numbers?

What they're doing is doing a fast test to see if a candidate prime prime+step has any of the smallest 669 primes as a factor (by testing whether prime%p + step is a multiple of the small prime p.  If they do find that the candidate has a small factor, then it is obviously not prime (and so they don't need to spend the comparatively long time running the Fermat test).

That being said, the code in primegen.c could have been done more efficiently.  What is more usually done is creating a sieve; that is, you create an initially clear bitmap corresponding to the first (perhaps) 2000 entries of prime+step; for each small prime p, you compute prime%p, and based on that value, mark off every entry in the bitmap that corresponds to a multiple of p.  Once you've done that, you can then step through the bitmask; any bit which is still clear corresponds to an entry with no small factors; you can then run your expensive primality tests on that.  The advantage of this method is that you need to deal with each small factor only once; this means it is more effective to have far more small primes that you test against (and so you eliminate more composites during the cheap part of your primality search)