The difference between these 4 breaking Cipher techniques?

These aren't "attacks" in and of themselves, they are simply a way to classify attacks depending on how many assumptions they make. For instance, if an attack requires plaintext-ciphertext pairs to recover the key, but they don't have to be any particular pairs, that attack is categorized as a known-plaintext attack. However if another attack required the attacker to be able to give input plaintext and obtain the corresponding ciphertext, it would be a chosen-plaintext attack.

To summarize, from weakest to strongest in terms of assumptions made and data requirements:

Known Ciphertext Attack

The attacker is given some ciphertext, but does not know (or does not know exactly) what the plaintext corresponding to this ciphertext is. As with the previous type of attack, he does not get to choose what ciphertexts he obtains, and cannot produce more.

This is the weakest type of attack, as the attacker has essentially nothing to work with except a few ciphertexts obtained from eavesdropping or other. As such, it is typically the hardest to design, but the easiest to implement/carry out.

Example:

Eve steals a bunch of ciphertexts from Alice's handbag, but has no idea what they mean.

Known Plaintext Attack

The attacker is given some plaintext-ciphertext pairs which he didn't choose (say, obtained from an encrypted conversation between two people - he knows what the conversation is about, but he didn't get to choose what was said). The attacker cannot produce more plaintext-ciphertext pairs, he has to obtain them from whoever has the key, for instance by eavesdropping again.

Example:

Eve overhears an encrypted communication from Bob to Alice, and later observes them meeting at Baker Street - Eve can now guess that the communication contained the word "baker street" somewhere, a form of known plaintext attack.

Chosen Plaintext Attack

The attacker is able to select any plaintext and obtain the corresponding ciphertext through that which is known as an encryption oracle, which is a sort of black box that produces the corresponding ciphertext given any plaintext under the sought-after key, but does not reveal the key itself (i.e. you can't crack it open and just grab the key).

Note: there are two types of chosen plaintext attacks. Either the attacker can only submit a set of plaintexts once to the oracle, after which he can no longer use it (batch chosen-plaintext attack), or he can use the oracle interactively, able to select new plaintext based on what the oracle tells him (adaptive chosen-plaintext attacks).

Example:

A poorly designed file storage system uses the same key to encrypt everyone's files, and lets anyone see anyone's files (in encrypted form). Eve knows Bob uses the service, she registers as well and starts encrypting arbitrary files (which she can choose) and looks at the resulting ciphertext. From this she obtains the service's encryption key, and decrypts Bob's stuff.

Chosen Ciphertext Attack

This is essentially the opposite of the previous attack, the attacker can choose any ciphertext he wants and obtain the corresponding plaintext using a decryption oracle. It is however a stronger attack model than a chosen plaintext attack, and the strongest of all four here (but there are even stronger models outside the scope of your question, such as related-key attacks).

Example:

Eve breaks into Bob's house while he is sleeping, and replaces the ciphertext he was going to send to Alice tomorrow with a new one of her choosing. She then eavesdrops on their communications (encrypted or not) the next day to try and work out what Alice read when she decrypted the fake ciphertext (variants of this involve Eve not just creating a new ciphertext, but modifying the existing one slightly).

Encryption and decryption oracles are generally concretized as weaknesses in an interactive protocol which allow an attacker to attempt to impersonate a legitimate user and obtain information from the other party (but there are many other situations that may cause the attacker to have access to an oracle, of course). They aren't actually "oracles" that helpfully assist the attacker, that is only a mathematical abstraction.
As per Kerckhoffs's principle, the attacker is assumed to always know the internals of the cipher used, in addition to whatever plaintext or ciphertext he may have access to.
Note that some of the attack types above are mutually exclusive (for instance, an attack can't be both chosen-plaintext and known-plaintext).
Chosen plaintext/ciphertext attacks are somewhat exclusive to the modern ages of cryptography. In the past, such oracles were difficult to obtain, as physical communication between parties was not easy. However, they were not completely unknown, for instance, during WW2, Allied cryptographers routinely carried out maneuvers to tempt the Germans into sending specific messages encrypted with the Enigma (as an oversimplified example, by destroying an enemy ship, they could then be reasonably sure subsequent transmissions would contain the words "ship" and "destroyed" - a form of chosen plaintext attack, just not with an entirely reliable oracle).


Why should keys be hidden from an eavesdropper for a pseudorandom function?

With $k$ the adversary can compute $F_k(x)$ for some $x$ using the evaluation algorithm, and compare it to the answer of its oracle on $x$.


Yes.  256-bit WEP is insecure.  There are a broad range of attacks against WEP.  Most of them aren't affected by the key length.  Wikipedia has references to many attacks on WEP; for more, read those references.  Don't use WEP.  Go straight to WPA2.


How secure is reducing length and concatentation of hash?

Actually, I believe that both sub128(sha256(q)) + sha128(sha1(q)) and sub128(sha256(q)) + sha128(ripemd128(q)) allow a forgery attack in about $O(2^{70})$ time; hence it would appear to be weaker than SHA-256.

Here's how it works: for both SHA1 and RIPEDM128, there are known ways to find collisions in about $O(2^{63})$ time or so; there are ways that take an intermediate state, and find two different message segments of the same length that both result in the same intermediate state after processing.  So, what we do is find 64 consecutive such different message segments; this gives us a $2^{64}$ wide collision; that is, $2^{64}$ distinct messages that all result in the same hash.  The effort involved is 64 times the basic collision attack, or about $O(2^{69}) time.

Once we have $2^{64}$ messages that are all collisions for SHA1/RIPEMD128 (and hence are collisions over the first 128 bits in the case of SHA1), we SHA-256 hash all of them; with good probability, we'll find a pair that collides in the first 128 bits of the SHA-256 hash.

This pair is your collision over your $L$ function...


What is the meaning of "trapdoor" in cryptography?

A trapdoor function is a function that is easy to perform one way, but has a secret that is required to perform the inverse calculation efficiently. That is, if $f$ is a trapdoor function, then $y = f(x)$ is easy to compute, but $x = f^{-1}(y)$ is hard to compute without some special knowledge $k$. Given $k$, then it is easy to compute $y = f^{-1}(x, k)$. The Wikipedia article also contains a straight-forward explanation.

The analogy to a "trapdoor" is something like this: It's easy to fall through a trapdoor, but it's very hard to climb back out and get to where you started unless you have a ladder.

A hash function is not a trapdoor function because it is not reversible. Instead, it's called a one-way function. A one-way function is similar to a trapdoor function in that it's easy to compute both and it's very hard to reverse both, but there is no special key that allows you to reverse the one-way function.

To compare the definitions of one-way and trapdoor functions, I double-checked teaching sources I'm familiar with, including:

Boneh's lecture notes
Wagner's lecture notes
Bellare-Rogaway's lecture notes
The Handbook of Applied Cryptography (PK systems, hash functions)

They all categorize (sometimes implicitly) trapdoor functions as a subset of one-way functions: Trapdoors are a one-way function with the extra restriction that they have a secret for calculating the inverse.

For example: RSA is a one-way trapdoor function, but SHA-1 is just a one-way hash function. Discrete exponentiation is also (supposedly) just a one-way function, since there's no key information about the group that can be used to calculate the discrete logarithm efficiently.

That said, on a pragmatic note I have noticed that common Internet usage often mixes the terms "one-way" and "trapdoor" interchangeably, which no doubt causes confusion.


Which one is fastest? Karatsuba or Montgomery multiplication?

Summary: Montgomery only aims at modest (if any) speedup compared to classic algorithms; it is popular for other reasons. Karatsuba allows large speedups for very large parameters, but the threshold where it becomes beneficial is often not reached in cryptographic applications. The techniques can be used together.

Montgomery arithmetic is used for modular multiplication and exponentiation, a common operation in cryptography (RSA, some Elliptic Curve Cryptography systems). At the cost of some pre- and post-computation (of mostly negligible cost when the exponent is big enough to be secret), it simplifies the modular reduction steps, specifically with two benefits:

It avoids possible mis-estimation of the quotient, which in classical algorithms leads to a special case; this is beneficial from the standpoint of side channel leakage (e.g. timing attacks); and by the peace of mind it gives (the classical quotient estimation and its special case are hard to get right and test fully).
The Montgomery equivalent of quotient estimation is performed based on the low-order bits of the value to be reduced (rather than high-order), and that eases implementation of multiplication and modular reduction interleaved in the same scan of a temporary result (that interleaving technique in turn limits the width of numbers manipulated to about the size of the modulus, and reduces the number of memory accesses, compared to naively computing a full product then reducing it).

However Montgomery arithmetic leaves the cost mostly unchanged compared to a comparably good implementation using classical algorithms, accounting for both elementary multiplications and memory accesses. Modular exponentiation with $n$-bit numbers including exponent remains of cost $\mathcal O(n^3)$. More precisely, for both Montgomery and classical algorithms using $w$-bit words, interleaved multiplication and reduction, and basic scanning of random exponent: $\approx{3\over w^2}n^3$ multiply-and-accumulate with double-width result, and $\approx{6\over w^2}n^3$ memory accesses (${3\over4}$ reads, ${1\over4}$ writes).

Karatsuba multiplication is a divide-and-conquer algorithm for (non-modular) multiplication, which for $n$-bit integers reduces cost from the $\mathcal O(n^2)$ for classical multiplication to $\mathcal O(n^{\log_2 3})$, that is $\mathcal O(n^{1.58\dots})$.

Applied to modular exponentiation with $n$-bit numbers including exponent, the cost goes from $\mathcal O(n^3)$ to $\mathcal O(n^{1+\log_2 3})$, that is $\mathcal O(n^{2.58\dots})$. One of several methods for getting the benefits of Karatsuba multiplication during modular reduction is pre-computing the (non-modular) inverse of the modulus to slightly more than $n$ bits, which can be done at cost $\mathcal O(n^2)$ (thus negligible as far as $\mathcal O$ is concerned) with classical algorithms.

Karatsuba multiplication is beneficial only past some threshold for $n$. That threshold vary considerably depending on an awful lot of things. In a hardware multiplier optimized for low power, Karatsuba pays for modest $n$. In the GNU MP Bignum Library, there used to be a default KARATSUBA_THRESHOLD as high as 32 for non-modular multiplication (that is, Karatsuba was used when $n\ge32w$ with typically $w=32$); the optimal threshold for modular exponentiation tending to be significantly higher. On modern CPUs, Karatsuba in software tends to be non-beneficial for things like ECDSA over P-256 ($n=256$, $w=32$ or $w=64$), but conceivably useful for much wider modulus as used in RSA.

Karatsuba multiplication can be used together with Montgomery reduction. A good way to do so is by using big segments of arguments upon which Karatsuba multiplication is used. That could be the case for example in an implementation using Montgomery in the overall algorithm, with wide words and a wide multiplier (possibly hardware) using Karatsuba. Sometime Karatsuba is used for multiplication, followed by a separate reduction step using Montgomery; in which case the overall savings allowed by Karatsuba is less than $2$, irrespective of $n$.

I suggest Modern Computer Arithmetic for more details; or the classic but still useful Handbook of Applied Cryptography, especially chapter 14.


There is no simple answer in general to this question. In this specific setting, the zero-knowledge proof is needed to extract the discrete log of the value sent by the party and this is needed in the proof. In some other two-party protocols, this isn't needed. So, there's no general answer.


Let's say we have a ciphertext of length $(N-1)B < n < NB$, for $B$ the blocksize at hand (typically 128 for AES), where the ciphertext is made with $C_1, C_2, C_3, C_4$, with $C_3$ being shorter that the rest.

In order to decrypt a ciphertext made using ciphertext stealing as you drafted, you have to:

Decrypt the ciphertext just like you would for CBC without ciphertext stealing for the $N-2$ first blocks.
Take the latest two blocks ($C_3, C_4$ in your example), and compute the length of the "stolen" ciphertext by computing $n-(N-1)B=a$ and deducing its length $B-a$.
Decrypt the latest block, e.g. $C_4$ into its unencrypted value $E_4$
Xor $E_4$ with the concatenation of $C_3$ and $B-a$ 0s like $C_3 | \underbrace{0\cdots 0}_{B-a}$, to obtain $M_4 | C'_3$
Take the last $B-a$ bits of it, which is $C'_3$ and concatenate it with $C_3$, which you can finally decrypt just like you would usually.

I've committed a cri diagram, using the same colors as you, hope this helps:

Notice that this is assuming the same construction as you used in your graphic. (There are other ways to do it, too.)


Why SM2 ECC parameters does not specify cofactor h?

Elliptic curve can be perfectly defined only with $p, a, b, n, XG$, and $YG$.

Yes, indeed even though it's not the nicest / most convenient set of parameters, this is sufficient to recover the curve order (using Schoof's algorithm) and with that the co-factor.

Of course Schoof's algorithm, while efficient, isn't exactly fast nor widely implemented and therefore usually the curve order and co-factor are supplied.

  Why SM2 does not specify h, while Key Exchange Agreement Protocol
  introduce in SM2 part 3 has used it.

Well, the quality of the linked IETF draft isn't the best, so maybe it was just an oversight.

To answer your question: $h=1$.
This can be verified using the following sage-math instructions:

F=GF(0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF)
a=0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC
b=0x28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93
n=0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123
E=EllipticCurve(F,[a,b])
h=E.cardinality_pari()/n;h

where the last one should return the co-factor $h$ as being $1$.

  I calculate with an online big number calculator, the result is
  slightly greater than 1 (not fully equal).

This formula comes from the Hasse-bound (with $q$ being the curve and $p$ being the field order) $$\left|q-(p+1)\right|\leq 2\sqrt p$$ which assuming $q\geq p+1$ is
\begin{align}
&&q-(p+1)&\leq 2\sqrt p\\
\iff&& q&\leq p+2\sqrt p +1=(\sqrt p +1)^2\\
\iff&& h=q/n&\leq (\sqrt p +1)^2/n
\end{align}
If the last value is barely over $1$, this means that $h$ can only be $1$.


stream cipher and block one, which one is faster to encrypt/decrypt?

It depends on what you're trying to do.

In general, block ciphers are more versatile: anything you can do with a stream cipher can also be done with a block cipher in a suitable mode of operation.  So if there was no other advantage to "pure" stream ciphers (i.e. ones that are not based on block ciphers), everybody would just be using block ciphers.

The main advantages of pure stream ciphers over block ciphers are usually 1) raw speed, and 2) code / circuit size.  The versatility of block ciphers tends to come with some overhead cost, and if you're targeting a very low-end device, you can often squeeze some extra speed out and/or save some memory by only using a purpose-built stream cipher.

(Of course, that only really works if all you need is a stream cipher.  In the past few decades people have gradually woken up to the fact that in many — if not most — cases it's not enough to just hide the data by encrypting it, but you also need to protect it against tampering.  Block ciphers can do that, when used in a suitable mode, but most traditional stream ciphers can't.  So either you need to implement an extra integrity protection layer on top of the stream cipher encryption, or use an "authenticated stream cipher" that has it built in.  Either way, that adds extra complexity.)

So, at least in some situations, stream ciphers can be faster than block ciphers — and, in fact, that's their main selling point.

That said, there are also several situations where block ciphers can beat stream ciphers in speed:

Many modern high-end CPUs provide hardware acceleration for the AES block cipher.  If you're using such a CPU, using that is almost certainly going to be faster than any encryption you could implement purely in software.

(Of course, a similarly hardware-accelerated stream cipher might be even faster yet, and would likely require less space on the CPU chip, but it wouldn't be useful for nearly as many purposes as a block cipher like AES is.  So if you're only going to add extra hardware for one crypto primitive to your general purpose CPU, it might as well be a block cipher.)
Stream ciphers typically generate a sequential keystream, always starting from the beginning of the stream.  So even if you only need to decrypt, say, the last kilobyte of a multi-megabyte message, you still need to generate all those megabytes of keystream first.

There are various ways to work around that, such as splitting long messages into smaller chunks and encrypting those separately.  But many block cipher operating modes offer something even better: the ability to decrypt any block (of, say, 16 bytes for AES) of the ciphertext independently of the others.  If you need fast random access to small pieces of the encrypted data (e.g. to query an encrypted database), a block-cipher-based encryption scheme is probably the way to go.
The same features of many block cipher modes that allow random access also allow decryption (and in some cases also encryption) to be done in parallel by as many processor cores as you happen to have available.  Stream ciphers tend to be limited by their sequential nature to a single core per keystream.  Again, on modern multicore processors, that can make block ciphers significantly faster even without hardware acceleration.

Ps. For more information, you might also want to take a look at this earlier answer I wrote about the differences between block ciphers and stream ciphers, as well as the answers and wiki pages linked from it.


The short answer is yes. It would be considerably more secure.

But nowadays, classical encryption methods like Playfair and Vigenère are so easily broken by computer analysis that they offer next to no security whatsoever. Aiming for something "considerably more secure" than either of these is really setting the bar very low.

Specifically, although the combination of Playfair and Vigenère does reduce the frequency of repeated sequences, it doesn't get rid of them. So you still haven't eliminated the primary weakness of vanilla Vigenère.

For example, if your Vigenère key has length $n$, just one repetition of a word at an interval of $2kn$ places provides enough information to get started on an attack. You obviously don't know what the value of $k$ is, but there's nothing to stop you testing for key lengths corresponding to every divisor of $2kn$.

Even if your plaintext contains no repeated words whatsoever, you're still vulnerable to the same attack if the same word appears in more than one message. (Unless, of course, you use a different set of keys every time, in which case you may as well use a one-time pad.)

This system would also fail according to Kerckhoffs's principle:

  A cryptosystem should be secure even if everything about the system, except the key, is public knowledge.


What do associated data and message numbers mean?

As documented in the call for submissions of the CAESAR competition, an authenticated encryption scheme may have up to five inputs.

The key. This one is obvious. The key needs to stay confidential and once the key is leaked all authentication and confidentiality guarantees are lost.
The plaintext. This is also obvious. This is the message to be encrypted. It is guaranteed, that an (polynomialy bounded) attacker can't alter nor extract any information about the plaintext from the ciphertext.
The associated data. This is mainly meta data. It is guaranteed that an attacker can't alter the associated data, but may read it in clear text. Associated data is commonly used to transport IVs, headers or routing information.
The public message number. This is can be just a part of the associated data, but it also can be an additional fixed-length input. The public message number is guarenteed not to be altered, but may be read in clear text. A reuse of a (public message number , secret message number) pair may result in a complete loss of security guarantees for a given scheme. The use of this number may be to prevent replay attacks and to serve as a nonce for the underlying schemes.
The secret message number. This is a relatively new input. It is the plaintext equivalent to the public message number. Thus, the confidentiality of this number is also guaranteed. The use of this number may be to hide parts of the nonce for the underlying system from attackers or to allow (some sort of) hybrid encryption.


Is it possible to check if a number is the product of two primes without factorizing it?

Given a 613-bit integer, it is easy to check that it is composite (and we assume that's been done). It can be hard to factor, but that's feasible with GNFS, including with ready-made tools (see Luke Valenta, Shaanan Cohney, Alex Liao, Joshua Fried, Satya Bodduluri, Nadia Heninger's Factoring as a Service), and that's one sure way to demonstrate how many factors it has.

We can do better! We can use Lenstra's ECM repeatedly, with parameters and runtime tuned to find factors less than about 205 bits. That's within reach of the best current implementations, see Paul Zimmermann's list of ECM factoring records. If that fails, then it is a very strong indication that there is no factor 205-bit or less, thus there must be only two factors (for the product of three or more 205-bit integers has at least 613 bits). If that succeeds, we can test the primality and/or factor the rest.

I believe the tool of choice is GMP-ECM.

Edit: That is not generalizable to much larger integers. Starting about 800 bits, it becomes quite hard to tell apart those with two factors, and those with three factors of about equal size.


What is best practise for salting and multiple-hashing of passwords?

Current best practice does include bcrypt, which is the same as PHP's built in password_hash() function. Future best practice will probably be Argon2.

Other widely used secure KDF options include PBKDF2 with SHA512 or SHA256 as the hash function, and scrypt. scrypt and bcrypt differ from PBKDF2 in that they can use large amounts of memory, and thus resist cracking on commodity hardware better, which has more processing power than memory in the context of hash brute forcing.

bcrypt and PBKDF2 do have a specific issue, which is that a large password can cause the algorithm do behave in a way one would not expect. In bcrypt, there is a hard limit on input text, and a long password is simply truncated. In PBKDF2, the password is used as a direct input to HMAC, and if it is too large, the hash function must process the data more than once. My fix is to simply hash the password once with SHA512 before sending it to the KDF, as that makes the password input 64 bytes, which is within the bcrypt limit, and needs only a single hash with PBKDF2-SHA512.

Storage in the database is also an issue. Best practice is to use either the Modular Crypt Format or the PHC String Format. The trend is to use the PHC format over MCF as it is still based on MCF, but more flexible, and with more specific rules. PHC format with parameters allows forwards/cross compatibility and easy migration.

An example PHC format string:

$bpmhash_sha512$i=5,l=48$caaaaaaaaaaaaaaaaaaaaaaaaaaaaaab$HvrCpcKm209ikRst7gpsWbh1p5QyiA33R6iovxo0da6CX+lU1wKw0SserPtb6U3O

Where :
algorithm = bpmhash_sha512 (pbkdf2 with 1 round prehash)
i = the round count as 5
l = the output in bytes as 48
salt = caaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
hash = HvrCpcKm209ikRst7gpsWbh1p5QyiA33R6iovxo0da6CX+lU1wKw0SserPtb6U3O


Using rainbow tables to find encryption keys of block ciphers?

Define a function that takes the 4-bit plaintext identifier and the 36-bit key as input. For the purpose of the rainbow table you can treat it as an opaque 40-bit value.

The output of this function is the ciphertext you get when you encrypt the plaintext corresponding to the identifier with the specified key.

One you have this function, you can proceed with the rainbow table creation like you'd do for any other function.


Concerns about use of MAC in my specification

The pseudocode has a serious issue: changing the value of nonce2 in an otherwise valid cryptogram is not detected, and results in invalid deciphered plaintext. That would be fixed by

encrypt(password, string):
  nonce1 := generate_random_nonce()
  nonce2 := generate_random_nonce()
  key := derive_key(nonce1, password)
  encrypted := nonce2 || cipher(nonce2, key, string)
  return (nonce1 || encrypted || mac(key, encrypted))

but leaves two lesser issues:

The same key is used for cipher and mac; when not done properly, that can be a bad thing, and is a known recipe for disaster, e.g. if both cipher and mac used the key as an AES key for CBC encryption and CBC MAC, rather than using a carefully thought authenticated encryption mode like AES-GCM-SIV. With cipher chacha, and mac blake2b which is based on the chacha core, we should at least worry (even though I see no attack right now), and perhaps use something like proposed by Maarten Bodewes in that other answer.
We are told that derive_key is pkcs5_pbkdf2; this does key stretching, which is indispensable for any password; but PBKDF2 does not leverage the RAM and possibly multiple CPUs available at no cost to legitimate users, hence is orders of magnitude less safe against serious adversaries (using ASICs or FPGAs for password searching) than something state-of-the-art like scrypt.


How can one show that an ElGamal-like signature verification scheme is valid?

Your scheme is not the "true" ElGamal signature scheme: you swapped $x$ and $k$. I assume that $m$ is the hash of the message to sign, not the message itself.

Your scheme is sound, which means that the verification algorithm will return "ok" for a signature which has been generated as you suggest. To see that, remember Fermat's Little Theorem which says that for a prime $p$ and every integer $a$ (not multiple of $p$), we have $a^{p-1} = 1 \pmod p$. This means that when dealing with exponents, we can compute them modulo $p-1$.

So, when looking at your verification equation:

\begin{eqnarray*}
    (g^x)^s r^r &=& (g^x)^{x^{-1}(m - kr)} (g^k)^r \cr
                &=& g^{m - kr} g^{kr} \cr
                &=& g^m
\end{eqnarray*}

Soundness means that the algorithm works as intended, not that it is secure. This specific variant of ElGamal has been proposed in 1990 by Agnew, Mullin and Vanstone (the article is called "Improved Digital Signature Scheme based on Discrete Exponentiation"; I could not find a freely downloadable version). It has then been studied in a more general framework, called Meta-ElGamal Signature Schemes. As far as I know, it is still believed secure, but uninspiring (thus understudied), because, like most ElGamal variants, it leads to rather large signatures. DSA is preferred.


In which disciplinary category can cryptography be put?

It is multidisciplinary because it's a branch of mathematics and freely borrows from other branches such as statistics or algorithms.

I'm not so sure if it's cross-disciplinary. Although companies that make secure products (ie. products that use crypto facilities) employ cryptographers, cryptography in itself is a purely theoretical discipline that doesn't concern itself with implementation details that much (but Crypto.SE often does).

You could say it's interdisciplinary because it is a parent of quantum cryptography but I can't think of a justification for calling it cross-disciplinary.


How can I generate a brief (100) stream of random numbers, not using the computer or throwing dice?

Do a long jump, measure the distance in millimeters, take it modulo 10.

Repeat 100 times.

Another idea: use clock timer that shows milliseconds, start it and then turn off after some time, look at the last digit.


Chosen Ciphertext Attack on the Public Key in PGP

TL;DR: This attack extends the standard chosen ciphertext attacks on RSA and ElGamal to the hybrid encryption setting, but requires some huge IFs which no longer even have a slight possibility of being fulfilled.

To understand this attack, one first needs to understand how data is encrypted for PGP according to this snippet. Let's assume you have a recipient key $pk$, a message $m$, an encryption function $E_{pk}( \cdot )$ (either textbook RSA or textbook ElGamal), a random, symmetric key $K$ and a well-known symmetric cipher $E_K( \cdot )$. Now form the ciphertext $C$ as $C=E_{pk}(K)||E_K(m)$ with $||$ denoting reversible pairing (e.g. you can extract both parts later on).

The next step is to note that you can arbitrarily, multiplicatively modify the message in textbook RSA and textbook ElGamal, by performing specific (simple) operations on the ciphertext - only knowing the public key. Note that you can apply the two linked attacks on the encrypted "header" $E_{pk}(K)$ from above.

Now you use these attacks and change the $K$ value to $K'$, preferably in a clever fashion. If the cipher is suceptible to related-key attacks you generate the related keys for this attack this way and then apply your attack on it, possibly by abusing the user as a decryption oracle. Now it also may be, that you stumble across something a ciphertext that looks weak under the new key and allows you to deduce some information from the cipher text about the key, thus easing a brute-force attack.

Is this attack still feasible nowadays? As always, it depends.
The similar encryption mechanisms RSA-KEM and ECIES use a hashing function in between the symmetric cipher and the public key encrypted symmetric key, so they are immune.
If you use RSA-OAEP or an IND-CCA2 secure variant of ElGamal, you're also safe, as the malleability property no longer applies.
Additionally, authenticated (symmetric) encryption also makes this sort of attack much harder, as you first need to find a related key, that doesn't yield an invalid tag and thus reduces you amount of information from "a full decryption under this related key" to "a message whether decryption succeeded under this related key" which is likely not enough for a recovery attack.

If your cipher is (sufficiently) resistant to related-key attacks and doesn't have "weak ciphertexts", you're also safe. Most decent modern ciphers are "sufficiently safe" against related-key attacks, even AES which had some devestating experiences with these attacks is still safe enough.

It's especially the last mitigation that applies nowadays. Nearly everybody is using AES or a comparably strong cipher and thus the required related key attacks do not exist and this is more of a theoretical weakness, than a practical one.


PRNG that takes input a $n$-bit string and gives output a $2n$-bit string?

It can be consctructed in many different ways.

I will just give an example using HMAC-$\mathcal{H}$ where $\mathcal{H}$ is a hash function which returns a $x$-bit hash.

So if you want to use a PRNG which takes $n$-bit inputs and returns $2n$-bit output, you could act this way:

Divide the input into $\frac{x}{2}$-bit blocks $B_i$
For each block $B_i$ computes $B'_i = \text{HMAC-}\mathcal{H}_K(B_i \space || \space i)$ where $K$ is the symmetric key used for the HMAC computation and $||$ denotes concatenation.

In that case, note that the property $n$-bit input returns a $2n$-bit output is confirmed only if $n \mod \frac{x}{2} = 0$, but you can still truncate the result after HMAC computations to get the expected output length.


Advantages and possible usages of encryption schemes with probabilistic decryption

Since when decrypting we always want to get the correct message back, there's no reason why we would want to make this ambiguous. It would have no security advantage (if the adversary can guess with any non-negligible probability, you have already lost, so ambiguous decryption can't make that harder). Thus, unlike probabilistic encryption, which is needed for security, probabilistic decryption is an undesired property that sometimes arises when trying to construct schemes. For example, with the naive Rabin, it just happens to be a property of the number theory used. The additional work required to make Rabin a trapdoor permutation is necessary to make it useful.
Thus, the only reason why randomized decryption (with a probability of error) exists is when this is what some constructions unfortunately give us. (This can be viewed in some sense as an advantage - if we weren't able to allow decryption errors, we wouldn't be able to build these schemes, some of them having advantages.) There are some examples of this: NTRU and the Ajtai scheme based on lattices. As a result, there has been some theoretical work on removing errors from encryption schemes that have them. Most notably, I recommend reading the paper Immunizing Encryption Schemes from Decryption Errors by Dwork, Naor and Reingold.


Zero-knowledge-proofs on committed value

Yes, user $A$ can produce such a proof - indeed, any statement in NP (i.e., for which it is possible to verify that a given solution is valid, which is obviously the case here) can be proven in zero-knowledge.

In general though, proving non-algebraic statements of this kind (involving evaluations of hash functions, rather than algebraic manipulations such as exponentiation) is more costly and less easy than proving algebraic statements. Yet, this kind of questions have been considered at length. There are currently three main approaches:

Using garbled-circuit-based techniques, see e.g. this paper and some follow-ups
Using MPC-in-the-head techniques, introduced in this seminal paper and subsequently improved in Zkboo, ZKB++, and this recent paper.
A slightly different approach was taken in Ligero, using error-correcting codes, achieving a cost that scales only with the square root of the size of the circuit representing the statement (all previous solutions are linear).

Other techniques can also apply here, depending on your other constraints: should the prover be efficient? The verifier? Do you need the proof to be non-interactive? As short as possible? For each case, different solutions exist and provide various tradeoffs.


R-LWE instantiation with non-power of 2 polynomial

On the IACR eprint archive there is a paper entitled "Even More Practical Key Exchanges for the Internet using Lattice Cryptography" by Singh and Chopra that discusses using other cyclotomic fields which provide the same security guarantees as the power of 2 cyclotomic case.

One reason why these other cyclotomics are not as popular is that the speed of the Nunber Theoretic Transform in these other cyclotomics is not as computationally efficient.  Nevertheless as you point out there is a legitimate tradeoff between parameter sizes and computation.


How to stop an attacker from repeating the same ciphertext?

Your question appears to be conflating the ideas of IV and antireplay protection; actually, they don't have anything to do with each other.

The IV (in CBC mode) is a randomly selected value chosen by the encryptor; it can be sent along with the ciphertext (as we don't care if the attacker knows it).  It's there so that if we decide to send the same message twice (or send two similar messages), the ciphertexts look completely unrelated (and hence the attacker doesn't gain any information).  It doesn't help with antireplay; however, it was never designed to.

As for antireplay (rejecting identical messages), well, there are two standard ways for addressing it.

The first way is to have the receiver remember which messages it has already received.  That can be easier than you might think; if the sender includes a sequence number (which it increments each time it sends a message), the receiver can just check that with the last sequence number is saw; if it hasn't increased, it can reject the message.  Now, this might have an issue that, for you, doesn't make it work; when either system restarts, how do both sides know which sequence number to use?  When we use this strategy, we reset the sequence numbers to known values when we initially negotiate keys; it sounds like you're using configured keys, and so that doesn't work.
The other strategy would be a challenge/response protocol; we have the receiver send a value (which can be random); and then the sender includes that value in the encrypted message, and then the receiver checks to see if the value in the message matches the value it sent out.  In your case, it might look like this:

  PC: "I want to send you a command"

  Device: "OK, use the value 0x314159"

  PC: "Turn MACHINE1 on; value 0x314159; reply with value 0x271828"

  Device: "OK, command accepted; value 0x271828"

Note that the first two messages don't really need to be encrypted; there's nothing useful that the attacker can learn from them.

I included the reply value (chosen by the PC) so that the attacker can't simulate the device accepting the command when it really hasn't.

The third issue is "how do you make sure that the attacker can't gain anything from modifying the messages".  Obviously, an attacker that can change arbitrary messages can forbid any communication (by simply jamming the RS-232 signal); cryptography can't solve that problem; the best it can do is to make sure that's all the attacker can accomplish.

You mention a MAC (Message Authentication Code); that's the correct solution for this problem.  For each encrypted message, you would compute the MAC (which is the function of the message and a secret key); you send this value along with the encrypted message and the IV.  When the device receives it, it also computes the MAC, and compares the value it computes with the value in the encrypted message.  If the two values are the same, it knows that the message was not modified.

Without this, it's possible that an attacker might be able to modify encrypted messages; for example, he might be able to modify an encrypted "Turn Machine 1 on" message into an encrypted "Turn Machine 2 on" message.  It strikes me that avoiding such a possibility is worth doing.

With the resources you have, the easiest MAC would be a CBC-MAC.  To implement this, you would take your message (including the IV), prepend the message length if you support variable length messages, and then ask your CBC hardware to encrypt it, using a fixed IV (all 0's work), and a different AES key than you use to perform the actual message encryption.  Then, you take the ciphertext, and discard everything except the last 16 bytes; that's your MAC.

The receive side would do the exact same thing; they'd take the received message (not including the MAC), possibly prepend the length, and ask their hardware to encrypt it (yes, encrypt, not decrypt) with the same fixed IV, and look at only the last 16 bytes of the resulting ciphertext, and compare that with the MAC included in the received message.


Fully Homomorphic Encryption: Going from an integer to bits

One possible solution for you is to use a Bit Extraction Circuit. The references are framed in terms of MPC but they should be applicable. If you want something more specific/efficient to homomorphic encryption, it will depend on the scheme.

O. Catrina and S. Hoogh, “Improved primitives for secure multiparty
integer computation,” in Security and Cryptography for Networks
(SCN’10), ser. LNCS, vol. 6280. Springer, 2010, pp. 182–199.
O. Catrina and A. Saxena, “Secure computation with fixed-point
numbers,” in Financial Cryptography and Data Security (FC’10), ser.
LNCS, vol. 6052. Springer, 2010, pp. 35–50.
I. Damgard, M. Fitzi, E. Kiltz, J. B. Nielsen, and T. Toft, “Unconditionally secure constant-rounds multi-party computation for equality,
comparison, bits and exponentiation,” in TCC’06, ser. LNCS, vol. 3876.
Springer, 2006, pp. 285–304.


Difference between MAC(key, msg) and SHA(key || msg)

With the capacity of SHA-3[1] against length extension, It doesn't need HMAC where the key is used twice to build a secure MAC. Instead one can design with prepending the message with the key. Actually, NIST already standardized this into The KECCAK Message Authentication Code KMAC.

With the fixed key and message size, your scheme can be considered as keyed MAC. There is one drawback in your case, the message length prohibits MAC arbitrary messages.

Also, your scheme has a collision where $\operatorname{SHA}(key_1\mathbin\|message_1)=(key_2\mathbin\| message_2)$[2] i.e. the key is used as the message and message as the key ($key_2 = message_1$ and $key_1 = message_2$).

Stick to standards. With KMAC you can MAC arbitrary lengths and have desired output lengths with the help of the cSHAKE128 (XOF - Extendable Output Functions) and have domain separation and even you request different output sizes for the same input, the output will be different.

[1] One can use Blake2 and Skein, too. Those are also resist to length extension attacks

[2] Here we assume that SHA is not SHA-1 or SHA-0. Also note that the SHA-512/256, SHA-512/224, SHA-384 have resistance to length extension attacks. Those are designedNIST  after SHA3


If you compute a base of a the dual lattice, and then check that the inner product of the point and the vector if this base are all integers:
To compute this base it's $\mathbf{B}(\mathbf{B}^{T}\mathbf{B})^{-1}$:
https://cseweb.ucsd.edu/classes/wi12/cse206A-a/LecDual.pdf


You should read this article about Security of DGHV Encryption.

Oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any complexity class. Even undecidable problems, like the halting problem, can be used.


How can CBC-MAC be secure when message length is fixed?

What you think of is called an extension attack and it turns out that this is the way to go if you would like to break the general CBC-MAC when the message length is not fixed.

All that an adversary needs to do is to mount a chosen message attack.
Suppose he asks for the tag on the message $m=m_1||m_2||...||m_l$. The resulting CBC MAC would be $MAC_k(m)=t$. But now the adversary can easily find another message with a valid tag by extending his original message $m$ by  $m_1\oplus t||m_2||...||m_l$. By looking at the CBC-MAC construction its easy to see that the tag on the new message
$m'=(m||m_1\oplus t||m_2||...||m_l)$ is also $t$, what is in fact an  existential forgery.

This is a reason why the CBC MAC is just secure when the message length is fixed. The detailed security analysis of CBC MAC and some work arounds for the case where the message length is not fixed can be found in this paper:

Mihir Bellare, Joe Kilian, Phillip Rogaway, The Security of the Cipher Block Chaining Message Authentication Code, Journal of Computer and System Sciences, Volume 61, Issue 3, December 2000, Pages 362-399 http://dx.doi.org/10.1006/jcss.1999.1694.


Are cryptographies based on bitwise operations considered secure?

If I understood correctly (using uppercase notation for public keys and $\lor$ instead of "|" to indicate the logical or) your scheme is:

Public Domain $g \in \mathbb{Z}$
Alice Private Key $a \in \mathbb{Z}$
Alice Public Key $A=a \lor g$
Bob Private Key $b \in \mathbb{Z}$
Bob Public Key $B=b \lor g$

Shared Secret = $a \lor B = b \lor A = a \lor b \lor g$

Then I would say your system is insecure as an attacker can recover the shared secret using only the public keys as:

Shared Secret = $A \lor B = (a \lor g) \lor (b \lor g) = a \lor b \lor g$
(Given the property that $x \lor x = x$)


Is it okay to use an HMAC of the plaintext and a (possibly distinct) key as the IV for symmetric cryptography?

The scheme you describe is essentially same as the "SIV construction"* introduced by Rogaway and Shrimpton in their 2007 paper "Deterministic Authenticated-Encryption: A Provable-Security Treatment of the Key-Wrap Problem".

This construction takes a PRF (such as HMAC) and a conventional IV-based encryption scheme (such as, say, a block cipher in CTR mode), and constructs a deterministic authenticated encryption scheme by first feeding the plaintext (and any associated header fields) into the PRF to obtain a pseudorandom authentication tag, and then using this authentication tag as the IV for the cipher.

In the paper, Rogaway and Shrimpton show that, assuming that the underlying PRF and cipher are secure**, the resulting scheme satisfies a security definition they call DAE security.  They supply several equivalent versions of this definition, of which perhaps the easiest to paraphrase in plain English is the two-part version given in the appendices, which says that a determinstic encryption scheme is DAE secure if:

a (polynomial-time) attacker, given access to the encryption oracle, is unable to distinguish it (with non-negligible advantage) from a random oracle with the same output length, and
the attacker, also given access to the decryption oracle, is unable to forge a message (that is, produce a valid ciphertext that it did not receive from the encryption oracle) with non-negligible probability.

They also define a related security notion called MRAE, or misuse-resistant authenticated encryption, which is basically the same as DAE security except that the encryption and decryption functions take an additional (public) input called a nonce.  They show that:

any DAE secure encryption scheme that supports associated data (i.e. additional header fields that are authenticated but not encrypted) can be used as an MRAE scheme, simply by treating the nonce as part of the associated data;
when used with a random nonce (of sufficient length), an MRAE secure encryption system is a secure nonce-based authenticated encryption scheme in the conventional sense (and, in particular, is IND-CCA2 secure); and
when the nonce is repeated, omitted, or even controlled by the attacker, an MRAE scheme still remains DAE secure.

In conclusion, yes, this is indeed a secure way to construct a deterministic authenticated encryption scheme — assuming, as always, that the implementation is correct, the underlying primitives are secure, and none of the assumptions of the proofs are violated.
It does leak slightly more information than randomized encryption schemes, namely whether or not two plaintexts are identical, but no more than that.  (Of course, like all general-purpose encryption schemes, it also leaks information about the length of the plaintext.)

Also, a particular detail to pay attention to, when implementing this construction in environments where timing or other side channel attacks may be possible, is that both the PRF (e.g. HMAC) as well as the encryption layer need to be checked for such vulnerabilities.

(In conventional Encrypt-then-MAC schemes, the MAC layer is not vulnerable to most kinds of side channel attacks, since it only operates on data that has already been encrypted.  Of course, even for conventional schemes, comparing the authentication tags can be vulnerable to side channel attacks, so... it just goes to show that one needs to be careful when implementing crypto.)

*) Not to be confused with the SIV mode of operation they define later in the paper, which is an instance of the SIV construction using a block cipher in CTR mode as the encryption layer, and a multi-input variant of CMAC as the PRF.  Yes, it's a bit confusing.

**) The specific security property they require of the cipher is IND\$ security, or indistinguishability from "fake" cipher that outputs purely random ciphertext.  The main difference between IND\$ and standard IND-CPA or semantic security is that the former does not permit any detectable redundancy in the ciphertext, even if it leaks nothing about the plaintext.  It seems to me that the difference here is mostly technical, and that an IND-CPA secure scheme could be used just as well, if the definition of DAE security was also relaxed to permit such redundancy, yielding something like a deterministic analogue of RCCA security.


Mathematical calculation to determine probability of observing the character space used for a set of string inputs

Well, assuming that the router selects each character of the password in a uniformly and independently distributed fashion, then the probability of an individual character not being a specific character $c$ is:

$$1 - 1/62$$

(where the alphabet size is 62).

Hence, if we generate $n$ characters, the probability $c$ never occurs is:

$$(1 - 1/62)^n$$

Now, we have 62 possible values of $c$, and we want the probability that all of them occur somewhere to be high (say, $>0.99$), and so we have:

$$62 (1 - 1/62)^n < 1 - 0.99$$

Evaluating this, we get $n > 537$, or 67 8-character passwords.

The exact value you obtain will depend on the size of the alphabet (which you might not know precisely when you start), and the desired failure probability.  In addition, this is pessimistic in the sense that if you see every alphabetic character other than n, it's plausible that n can occur (and you just didn't happen to see it).  On the other hand, the router may be programmed to avoid the 1, I, l characters (because they may be easily confused in some fonts), and so that might not be quite so dreadfully pessimistic.

Pedants will note that this analysis isn't precisely correct (as the probabilities aren't independent; each character of the password is some $c$, and so multiplying the nonoccurance probability of each individual character by the number of characters isn't actually justified), however I believe that it's close.


Comparing DES and DES-X variation: $Enc(m) = DES_{k_1}(m \oplus k_2)$

The hint that you have given is simply saying that, if you have more than one (better many) plaintext-ciphertext pairs;

First, apply the n-pad attack to recover the real $k_2$ by;
$$p_1 \oplus p_2 = m_1 \oplus m_2$$
$$p_1 \oplus p_3 = m_1 \oplus m_3,\ldots$$etc. Once you recover one of the $m_i$'s than $$ p_i = k_2 \oplus m_i$$ is enough to extract the $k_2$
Then apply the usual brute-force with $k_2$ is known.

Note: your DES-X is not using key whitening which uses 3 keys, not 2.


They are actually the same, because you missed W^=V in the second link. When you work out the XORs, you arrive at the same constants.


Using what we already know about the data to decrypt it?

I recommend you will read a bit about chosen-plaintext attack.
If the scheme you are using is CPA-Secure then even when an adversary is choosing two different plaintexts, giving them to the challenger and then the challenger picks one of them, encrypts it and sends it back to the adversary - the adversary won't have an efficient algorithm to find out which one was encrypted.

AES-CBC with random IV is assumed to be CPA-Secure if my memory don't betray me. So, If you are using the encryption right, the knowledge of the structure of the plaintext should not help you.


Finding a Caesar cipher key given encrypted message and part of decrypted message?

For the Caesar cipher there are only 25 possible keys (and the key $k=0$ which degenerates into the identity function, ciphertext = plaintext).

Just try all possible shifts one by one starting from $k=1$ to $k=25$ (this constitutes a brute force attack). After each shift you need to validate that it results in an intelligible plain text by decryption of the ciphertext. For the Caesar cipher brute force attack is efficient.

Now if you have plaintext and corresponding ciphertext pair work become more easy you don't need to do brute force attack. As in generic Caesar cipher encryption/decryption is defined as

$$C = (P + K) \bmod 26$$

$$P = (C - K) \bmod 26$$

Then from above $K = C - P$ (for each corresponding ciphertext / plaintext character).

For example if the plaintext is "abc" and the ciphertext is "def". Then teh 'd' zero-based index is $3$ within the alphabet. And the and 'a' location is $0$ then $K=3-0=3$


Clarification of RFC2246 with regards to Finished Message

This is an error in RFC 2246 corrected at https://www.rfc-editor.org/errata_search.php?rfc=2246 and in the subsequent version TLS RFCs 4346 and 5246.
It derives from SSLv3 on which TLSv1.0 was mostly based, now available as RFC 6101 if you want to compare them. You'll see SSLv3 had

enum { client(0x434C4E54), server(0x53525652) } Sender;

(which are the ASCII strings "CLNT" and "SRVR" respectively) and specified that Sender is included in the hash calculation which in SSLv3 was a concatenation of doubled MD5 and SHA1 keyed hashes. TLSv1.0 changed this to finished_label with the values "client finished" and "server finished", included in the PRF defined elsewhere in the document as the XOR of doubled MD5 and SHA1 HMACs, where each HMAC is itself a doubled keyed hash.


Can I say "I have encrypted something" if I hash something?

Encryption algorithms and hash algorithms both belong to the realm of cryptography but are two different things: Encryption doesn't contain hash functions.

As stated on Wikipedia:

  In cryptography, encryption is the process of encoding a message or information in such a way that only authorized parties can access it and those who are not authorized cannot.

An encryption algorithm turns some data into a ciphertext which can later be decrypted again to its original content by using the encryption key.

If you generate a hash of some data it can't be "reversed" back into its original content, because a hash function is (theoretically) a one-way function with loss of data.


Why standard deviation of BLISS is so high?

I am assuming you are asking why the standard deviation in BLISS is high compared to that of the errors in encryption schemes.  The answer is that the errors in encryption and the random variables with high standard deviation in BLISS (and other lattice signatures) play very different roles.  In encryption, one simply needs to generate an error $e$ such that $(a,as+e)$ looks random.  You don't need to have a high standard deviation at all for that.

In BLISS, the random variable $y$ that has a high standard deviation is used for masking the secret.  In particular, a part of the signature is an element $z=y+sc$ where $s$ is a part of the secret and $c$ is the challenge.  What is needed for security is that the distribution of $z$ is completely independent of $s$ -- this ensures that signatures do not leak the secret.  The best way we know of how to do that is generate $y$ according to a discrete gaussian distribution of standard deviation proportional to $\|sc\|$ and then do rejection sampling. That is why in BLISS the $\sigma$ is of size proportional to $\|sc\|$.


I made an encryption device for school how can I make it better?

The folks here aren't keen on performing analyses of encryption algorithms, and a load of code in git doesn't help much with that either unfortunately.

What I would say though is that you seem to have yourself a stream cipher.  Have a look at chapters 5 & 6 of Handbook of Applied Cryptography.

One of the issues will be your random numbers.  Consider that any computer can easily just try all 30,000 of them sequentially until the message makes sense. We can just do this and it's called a brute force attack.


Is ShiftRows(SubtBytes(x)) = SubtBytes(ShiftRows(x)) the same for the same entry : in AES

There is no theoretically required here.
ShiftRows changes the position of bytes, regardless of their value
SubBytes changes the value of bytes, regardless of their position
Therefore the order of these operations does not matter


If $f()$ can be modeled as a random function (that is, if each output for a distinct input is independent of all other outputs), then this is a well studied problem in probability theory, known as the Coupon Collector's Problem.

The link I gave you gives more details; the bottom line is that you start getting good probability of seeing all possible sequences after around $C n 2^n$, for a constant $C$ not too far from 1 (and whose actual value depends on what "good probability" actually is).

Of course, if your theoretical hash function doesn't act randomly (for example, there are pairs of inputs $A \ne B$ where we're guarranteed that $f(A) \ne f(B)$), this analysis does not apply.


What is the probability to produce a collision under two different hash functions?

A "simple" answer (but somewhat wrong) would be the following: define function $H$ which is the concatenation of MD5 and SHA-1; i.e. on input $x$, $H(x)$ will be the 288-bit string consisting of MD5($x$) (128 bits) followed by SHA-1($x$) (160 bits). If you have distinct two messages $x$ and $y$ such that MD5($x$) = MD5($y$) and SHA-1($x$) = SHA-1($y$), then, by definition, $x$ and $y$ are a colliding pair for $H$. Since $H$ has a 288-bit output, finding a collision for $H$ requires an average effort of, at most, $2^{144}$ invocations, since that's the best you can expect from a "perfect" hash function.

What's wrong in the paragraph above is that the $H$ function, as described above, is far from the "perfect" state. In 2004, Joux published (Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions) an attack that works on "iterated" hash functions such as MD5 and SHA-1, which shows that even if MD5 and SHA-1 were both ideally strong (given their output size), the concatenation would not be stronger than the strongest of the two. In other words, even without leveraging known attacks on MD5 and SHA-1, a collision on the concatenated hash function $H$ can be found in about $2^{80}$ invocations. This work was generalized in 2006 by Hoch and Shamir (Breaking the ICE - Finding Multicollisions in Iterated Concatenated and Expanded (ICE) Hash Functions).

Now, both MD5 and SHA-1 have known structural attacks. In an answer to a previous question on that subject, @poncho explains how to use the known attacks on SHA-1 (with cost $2^{61}$) to make a simultaneous MD5+SHA-1 collision in effort $2^{67}$. Amusingly, this does not leverage any specific weakness of MD5; it would also work for a perfect 128-bit hash function instead of MD5.


Do PGP keys with expiration date set expiration date in Encrypted messages too?

It is the keypair that is doing the encrypting, not the one doing the decrypting, that the expiration date applies to. And yes, they will be able to decrypt it after one week. In fact, they will always be able to decrypt it. The expiration date only applies to the key and is nothing more than a gentle reminder that the key is supposed to be replaced and should no longer be used for encryption (for public keys) or signing (for private keys). There is nothing stopping anyone from decrypting data that was encrypted with an expired public key. Unless a revocation certificate is generated and imported, an expired public key can have its expiration date retroactively modified by the holder of the private key. This is common practice.

If a public key has passed its expiration date, most PGP programs will warn you if you try to encrypt a message with it. There is nothing fundamentally that prevents you from forcing encryption, although some programs may refuse to encrypt with it and do not provide any override option. In those cases, forcing encryption with an expired public key is as simple as changing your computer's clock.


I haven't seen much analysis on using ordinary hashes for content authentication. Can anyone can give me a pointer on whether this is safe?

With good choice of primitives it is. Public key signatures use a hash function in a similar way to identify the message signed.

However, where a MAC only needs what amounts to second preimage resistance, a hash function also typically needs collision resistance, since an attacker can calculate an arbitrary amount on their own. (This is why SHA-1 is being deprecated in signatures even though there's no indication it isn't preimage resistant.)

HMAC is also stronger than the hash function it uses. So while SHA-224 is strong, you will have lower security with it than with HMAC-SHA-2. Technically, it may mean you don't even have 128-bit security – "only" 112-bit.

You don't actually need to use the checksum itself in the HMAC. You can instead use a full SHA-256 (or SHA-512, which may be faster). If you want to truncate – length extension attacks aren't an issue because of the HMAC – only truncate it when writing the checksum, but not when calculating the HMAC. Assuming you don't need as much confidence when detecting corruption, you could even truncate the checksum to only a few bytes and save some space.

I.e.

hash = SHA-NNN(ID | IV | len | encrypted)
checksum = truncate(hash)
sig = HMAC(ID | len | hash)
message = ID | IV | len | encrypted | checksum | sig

(Having ID and len in the HMAC seems unnecessary, but doesn't hurt.)


Is there any difference between cryptography and cryptology?

Today, indeed the the terms "Cryptography" and "Cryptology" can mostly be used interchangeably.

Historically things have been more interesting though, where Cryptology was the umbrella term for Cryptanalysis and (constructive) Cryptography. For example the Handbook of Applied Cryptography (chapter 1 PDF) has the following definition (page 15) of "Cryptology":

  Cryptology is the study of cryptography (Definition 1.1) and cryptanalysis.

with "Cryptanalysis" being defined as (on page 15)

  Cryptanalysis is the study of mathematical techniques for attempting
  to defeat cryptographic techniques, and, more generally, information
  security services.

and "Cryptography" being defined as (on page 4)

  Cryptography is the study of mathematical techniques related to
  aspects of information security such as confidentiality, data
  integrity, entity authentication, and data origin authentication.


Is there an efficient algorithm that allows to obtain a uniform distribution of all possible $4$-bit permutations from a single keyless $4$-bit S-Box?

In Haskell the recursive function

f s x = s (g 16 (x `div` 16) (x `mod` 16))
  where g 1 _ = id
        g n x = t (n-1) (x `mod` n) . g (n-1) (x `div` n)
        t x y z = if x == z then y
                            else if y == z then x else z

runs for any function s that is a permutation on [0..15] through all permutations on [0..15] if you let x run through all numbers 0...20922789888000*16-1.

Of course, s doesn't matter much, so I'd set s = id, and look at the definition of g using t: t x y is simply exchanging the values x and y, keeping all other values the same.

Now g n x is a(n arbitrary!) permutation on [0..n-1] depending on x: x mod n determines which element to exchange with n-1 (all other elements are untouched) and x divided by n is used as parameter to for defining recursively g (n-1).

If you pick n uniformly from 0..20922789887999, the permutation g n will be a uniform random element of the symmetric group on [0..15].


Multiplying two additively shared values

This cannot be achieved information-theoretically. This is typically the task that requires multiparty computation protocol to be achieved. In particular, the common method for what you want is called "secure multiplication protocol", and is in general constructed from an additively homomorphic encryption scheme (over the ring $R$), or from oblivious transfer.

Exemple with the encryption scheme:
Alice holds $p_a,q_a$; Bob holds $p_b,q_b$. Alice picks an encryption scheme $E()$ and sends the public key to Bob. She keeps the secret key. Then, she sends $E(p_a), E(q_a)$ to Bob, who computes (using the homomorphic properties of the scheme $E()$) and sends back $E(p_aq_b + r_1), E(p_bq_a+r_2)$, where $r_1$ and $r_2$ are fresh random coin. Alice decrypts these values and get $(u_1,u_2)$. She computes $n_a = u_1 + u_2 + p_aq_a$; Bob computes $n_b = -(r_1 + r_2) + p_bq_b$. You can see that $n_a + n_b = (p_a+p_b)(q_a+q_b) = pq$; the fact that this does not reveal $p$ nor $q$ can be proven assuming the encryption scheme is IND-CPA secure (id est indistinguishable against chosen plaintext attacks).

To answer your second question, if $pq$ is hard to factor, then even knowing it, it is computationally infeasible to recover the shares of $p$ and $q$ of the opponent - however, it does obviously not leak "nothing" in an information theoretical sense.


How can two parties offline generate a sequence of corresponding key pairs that are still sufficiently random

If RSA is not a requirement, here's a potential solution that uses ECC.
A generates a key-pair, $p_0, P_0$. A and B share a secret $s$ and the public key $P_0$. To move to the next key-pair, A multiplies the private key by $s$ and B multiplies the public key by $s$, so that the key-pair is $p_n = s^np_0, P_n = s^nP_0$ at step $n$.


Any ideas on login using Digital Signature PKCS

Web application, using modern browsers, may access user's Certificate Store or USB Token or Smartcard (through Certificate Store using CSP in token driver) through Browser Extension.

Methods like java applets, Active X, etc are being phased out from the new Modern Browser offerings. Recently much is being talked about WebCrypto API but as of now, WebCrypto API does not provide access to (Windows) or any other Key stores or local crypto USB/Smartcard device.

For Authentication from Browser using Digital Signature, one such free Chrome extension available is Signer.Digital chrome extension. Local system (host running behind the chrome browser on windows) setup may be downloaded from https://download.cnet.com/Signer-Digital-Chrome-Extension/3000-33362_4-78042540.html
 Installing this host and restarting Chrome will automatically add Signer.Digital Chrome Extension

The actual working of this extension is illustrated here

Javascript to call method from extension:

To Register Certificate on Server:

//Get Selected Certificate Information
SignerDigital.getSelectedCertificate()
    .then(
        function (CertInfo) {
    //Success returns Certificate Subject and Thumbprint
        },
            function (errmsg) {
                //Send errmsg to server or display the result in browser.
              }
     );

To authenticate or Login using Digital Signature:

SignerDigital.signAuthToken(authToken, "SHA-256")       //or "SHA256"
    .then(
        function (SignData) {        //Success returns Signed Auth Token
        },
            function (errmsg) {
                //Send errmsg to server or display the result in browser.
              }
     );

To sign PDF:

    //Calculate Sign for the Hash by Calling function from Extension SignerDigital
    SignerDigital.signPdfHash(hash, $("#CertThumbPrint").val(), "SHA-256")      //or "SHA256"
     .then(
            function (signDataResp) {
              //Send signDataResp to Server
        },
            function (errmsg) {
                //Send errmsg to server or display the result in browser.
              }
     );

If Failed: returns error msg starting with "SDHost Error:"

Disclosure: I work for CISPL which offers Signer.Digital Browser Extension


Is a Qualified Digital Certificate backward compatible with existing certificate code?

TLDR: yes.

Qualified Digital Certificate is not a specification aiming at insuring interoperability. It purposely does not even specify a precise cryptosystem (see comment). Thus in principle there is no sure answer to that question.

However Qualified Digital Certificate only requires common X.509 features, modern Microsoft Cryptography API is flexible in what it accepts, and because it is common certificate issuers typically take care of going by whatever requirement it sets. Thus my bets are on: likely yes, and I'd be surprised if a little care in parametrization at key generation and procurement of the certificate did not make it possible.

Note: Qualified Digital Certificates does not imply Qualified Digital Signature, and there is a long way from the former to the later.


Are there any encryption schemes that enable to permute homomorphically?

One can do bounded-length "composition of permutations on the ciphertext"

by Evaluating Branching Programs on Encrypted Data.

Public key length and ciphertext length both scale linearly with the number of permutations.

Leveled FHE can evaluate arbitrary-length compositions of permutations, since iterated composition of permutations can be carried out in low depth. $\:$ (So, one does not need full FHE.)

I don't know of any less general methods than that for arbitrary-length compositions.


Plaintext formation for checking avalanche effect

No.  You cannot use decimal numbers (or ASCII characters for that matter).  You have to use binary.  Your algorithm will be operating in binary as do digital computing devices.  If you were to use ASCII chartacters as you have, you'd only be testing the printable range of byte values.  You'd have huge gaps in the test inputs and no continuity.  You might only test 50% of the possible range, depending on your interpretation of what a printable ASCII character is.  If you've defined your P1 and P2 as integers, then the gap will be even bigger (= 10/256%) as you're now restricting yourself to integer parsable characters.

So in the Java language, P1=0b1110011 and therefore P2=0b1010011.  You randomly flip them.  In Java that's easy as you can use BigInteger for that and it handles arbitrarily sized integers and their random generation.

There's some more detail of the test procedure in this, this and this other answer.  Good luck with your normal curve.


Understanding a method of vector multiplication

I can't completely answer your question, but I don't see how sage can't compute the polynomial multiplication - are you computing in the residue ring modulo $x^n + 1$?
The following executes within a few hundreds of milliseconds on my computer:
R.<x> = PolynomialRing(GF(2), "x")
RR.<z> = R.quo(x^57367 + 1)
RR.random_element() * RR.random_element()

Maybe you can use this to debug your implementation.
Hope I could help!


Encryption Key derivation from numeric PIN?

It is common that the attacker has at least as fast platform as somebody generating the key. Thus, brute force attacker can test all 4 digit PINs in 1000 seconds or 17 minutes (based on 100 ms seconds mentioned in the question).

BTW, it is fairly common to use larger iteration counts than minimum of 1000 and longer times (like anything that takes 1s to process. On modern platforms, counts of 10000 or 100000 can be completely reasonable). In addition, it is common to punish wrong attempts with delay to slow down guessing.

In case the attacker has access to some computing power, like ASIC circuitry designed for cracking PBKDF2, they may be able to break the secret, for instance, 1000 times faster i.e, the could guess 10000 pins/passwords per second (assuming key derivation takes 100 ms seconds on the device).

--

For PIN and PBKDF2 to be secure against attacks, it is often mandatory to do these:

Attacker cannot get direct access to the storage on the device (to get values needed for breaking the secret offline with specialized devices)
The device does not allow to try many PINs very quickly (increasing delay after trying).
Too many miss attempts lock the device.

But, generally using good passwords is much more secure than using PIN codes.
This is my earlier answer on security of PIN or password when materials needed for brute forcing are available for the attacker.


Padding Oracle: Why should padding be 0x01?

That is the way the PKCS#7 standard works. This standard is the "most used padding method in symmetric ciphers". Which is why most descriptions of the padding oracle attack simply assume that padding scheme. Other padding schemes are likely also vulnerable.


What's the reason for applying the hash twice when hashing with salt?

This construction has two advantages over a plain hash of param1||param2:

It's immune to length-extensions
You can't get collisions of the form param1=A||B param2=C vs. param1=A param2=B||C.

But neither of those is relevant to password hashing, so it doesn't offer any advantage there.

The construction looks like it's inspired by HMAC:

$$ HMAC(K,m) = H((K ⊕ opad) ∥ H((K ⊕ ipad) ∥ m)) $$

But of course for password hashing one would not use such fast hashing constructions. Correct choices are scrypt, bcrypt, and PBKDF2. These have a designated salt parameter, so they don't need such an ad-hoc construction to mix salt and password.

This system has one big advantage though: You can upgrade existing hashes to it, without knowing the plaintext password. Essentially you treat $ hash(pass) $ as the new password. When upgrading an old system from a plain, unsalted hash, I'd use something like:

$ PBKDF2(LegacyHash(password), salt) $


The text you quoted appears to be incorrect; as specified, it doesn't always work (as you found out).

$y_1^m y_2 = g^{\sigma_1} y^{\sigma_2}$ will hold in general if both of the following are true:

$$a_1 m + b_1 \equiv \sigma_1 \pmod{p-1}$$

$$a_2 m + b_2 \equiv \sigma_2 \pmod{Order(y)}$$

Note: it is possible for the equation to hold in other conditions, but because $y$ has no known relationship with $g$, it would be infeasible to find other solutions for non-toy instances of this problem, even for the valid signer.

However, the text specifies that $\sigma_1$ and $\sigma_2$ are computed modulo $q$; if $q < p-1$, then neither of these equations are guaranteed to hold.

I can see two obvious ways to fix up this method:

Specify $q = p-1$; then both $\sigma_1$ and $\sigma_2$ will satistfy the above conditions (N.B.: all possible values of $y$ have an order that is a divisor of $p-1$)
Allow any $q | p-1$; however, specify that both $g$ and $y$ must be of order q.

Also, as specified, this scheme would appear to be insecure as a signature scheme; with two valid signatures, an attacker should be able to recover $a_1, a_2, b_1, b_2$, which is the private key.


The minimum of 40 bits is conventional; below 40 bits of key material, RC4 (or practically any cipher without some built-in key stretching) is just too unsafe.
At some point in history, in many countries, ciphers with a key above 40 bits where illegal in some usage (in USA: export; in France: use, sale, export); thus cipher designers wanting to prescribe something as secure as possible often used that 40-bit limit.

The maximum of 2048 bits is a consequence of RC4's key scheduling. Quoting Wikipedia's page on RC4

for i from 0 to 255
    S[i] := i
endfor
j := 0
for i from 0 to 255
    j := (j + S[i] + key[i mod keylength]) mod 256
    swap values of S[i] and S[j]
endfor

We see that 256 passes are made, and each pass manipulates 8 bits of key; above $8\cdot256=$ 2048 bits, extra key material would be ignored.

Anyway, array S[] remains a permutation of 256 distinct values, hence can hold a maximum of $\log_2(256!)\approx$ 1684 bits of entropy, and that key size limit of 2048 bits is only a practical issue when the key is not truly random in the first place.

In order to strengthen RC4 against weakness in its key scheduling / setup (leading e.g. to break of WEP encryption), it is advisable to stretch the size of the key material (e.g. to the maximum of 2048 bits) using a pseudo-random transformation (alternatively, or in combination, the first 256 or 512 bytes generated can be discarded). And if the original key is low-entropy (e.g. a password), it must be strengthened by a slow key derivation function in order to resist brute-force password cracking. Both can be done using scrypt with dkLen=256, and other parameters set as appropriate for the environment.


Choice of multiplication polynomial in Rijndael s-box affine mapping

As I have duplicated your question by mistake and non of us have had an answer, I request help to the authors to know why those parameters where selected like that.

The affine transformation is a vector space operation $(\mathbb{F}_{2})^8$, and the simplicity comes from the fact that, from the bunch of possible transformations the one used can be also described as a product in a polynomial ring modulo $x^8+1$.

Above the criteria that the matrix (or the multiplicand constant in polynomial view) must be invertible and the vector (or the addition constant) has avoid fixed point neither opposite fixed points, they have simply picked some from the set.

The timing feature is useful when the S-Boxes are calculated on the fly, but with them pre-calculated the difference doesn't matter (I think).


Rapid partial block decryption of compute intensive full encryption

The following mostly solves the problem as expanded in comment, but not quite: decryption is not $O(1)$.

We use some purposely slow hash function $H_w$ (where $w$ is a workfactor parameter for e.g. PBKDF2-HMAC-SHA-256, Scrypt, Argon2, Baloon..).

We define parameter $s$, the encryption overhead in bits per chunk; and $t$ which controls the average number $2^t$ of invocations of $H_w$ for (the first) encryption of a chunk. Decryption does just above one invocation on average, and seldom many, when we assume $0<t<s-6$. Example parameters can be $s=32$, $t=20$.

Chunk $c$ is enciphered using AES-CTR, IV of $c\ll8$ (which for up to 4KiB chunk ensures no IV reuse), and an AES key $k_c$ (of say $b=128$ bits) determined as follows:

Using auxiliary fast Key Derivation Function, both encrypting and decrypting parties compute $\operatorname{KDF}_k(c)$ of $2b$ bit (where $k$ is the overall encryption key), and split the outcome into $\widetilde{k_c}$ and $k'_c$ each $b$-bit. The auxiliary KDF can be HMAC-SHA-256. The final $k_c$ is determined from $\widetilde{k_c}$ and $k'_c$ as follows.
The party that encrypts

sets $k_c\gets\widetilde{k_c}$;
tests if $H_w(k_c)\bmod2^s=0$, and if not sets $k_c\gets k_c+1\bmod2^b$ and retry (assimilating integers modulo $2^l$ and $l$-bit bitstrings per big-endian conventions);
computes $n=k_c-\widetilde{k_c}\bmod2^t$ and includes that 48-bit $n$ as a prefix of the ciphertext chunk;
sets $k_c\gets k_c\oplus k'_c$;
now has the final $k_c$, and encrypts the chunk.

The party that decrypts

extracts $n$ from the ciphertext chunk's prefix;
sets $k_c\gets\widetilde{k_c}+n\bmod2^b$;
tests if $H_w(k_c)\bmod2^s=0$, and if not sets $k_c\gets k_c+2^t\bmod2^b$ and retry (which should happen rarely);
sets $k_c\gets k_c\oplus k'_c$;
now has the final $k_c$ (always the same as used for encryption), and decrypts the chunk.

For large $k$, the observation of $n$ from ciphertext leaks no useful information to an adversary, assumed with no access to $k$, $k'_c$, and the final $k_c$ (the system is also protected from leaks related to $H_w$, $\widetilde{k_c}$, or intermediary values of $k_c$, e.g. by timing attack). The CTR IV unique per AES block ensures that multi-target search of $k_c$ do not apply.

Possible improvement: we can add one bit of overhead set on encryption to tell if $H_w(\widetilde{k_c}+n)\bmod2^s=0$, which occurs in most cases, and decreases the decryption overhead dramatically.

Note: a former version had no $k'_c$, and $n$ could leak some information. This revised version can thus be safely used with $b=128$, rather than the original $b=192$.


Why is padding the plaintext with a random string before encryption worse than OAEP / PKCS#7?

The padding used for RSA is not the PKCS #5/#7 padding (as you seem to suggest in your own answer), but the Wikipedia entry seems to refer to PKCS #1 v1.5 (RFC2313)) which uses a padding

00 || BT || PS || 00 || D

where for RSA encryption we start with a 0x00-byte (to guarantee that the resulting number is below the modulus), then use BT (Block Type) equal to 0x02, the padding string (PS) is at least 8 long and consists of random non-zero bytes, the single 0x00 is added followed by the actual data being encrypted (D), and so that the total length equals the effective length in bytes of the modulus.

The padding can then be uniquely removed because the start of the RSA-decrypted block should follow this pattern that we can check, and we strip random bytes until we meet the first 00, after which we have the data.

The problem lies in implementations that check this padding and that somehow leak (e.g. by the different possible error responses, or time used for checking etc.) how exactly the padding removal failed (no start 00, no 02 byte, padding too short, data unexpected length..) and attacks were developed based on that (see Bleichenbacher oracle etc.). So the padding does work, but it is "ad hoc" (it has no proof of security) and it's too easy to do the checking in a wrong way. Hence OAEP, which has more of a theoretical basis.


Does a one-time pad of digits 0-9 have any weaknesses?

The one-time pad can be made of digits 0-9, and you can read more about that here. One could also use binary digits, 0 and 1, or letters such as A-Z.  Those three alphabets are the most common.

Are there any cryptanalysis methods that that allows for that wouldn't
apply to a one-time pad composed of letters?

No, there are not.  A properly generated one-time pad is going to have equal strength no matter whether it is composed of letters A-Z, numbers 0-9, or the binary digits 0 and 1.
The CIA, for example, was fond of using one-time pads composed of numbers 0-9 during the Cold War.
However, in practice, using numbers or binary could possibly introduce errors because of fractionation.  In other words, using letters might be more straightforward.

One thing that occurred to me is that since letters can't be shifted
by more than 9 places, it ought to show very small peaks in its
frequency distribution...

Don't worry about that.  It is not the case.

The question is probably equivalent to whether a Gronsfeld cipher has
any weaknesses that a Vigenere cipher doesn't.

One can see what you mean by this, but Gronsfeld and Vigenere are a very different kind of cipher from the one-time pad.


What's the appeal of using ChaCha20 instead of AES?

I believe there are three main reasons why ChaCha20 is sometimes preferred to AES.

On a general-purpose 32-bit (or greater) CPU without dedicated instructions, ChaCha20 is generally faster than AES. The reason for this is the fact that ChaCha20 is based on ARX (Addition-Rotation-XOR), which are CPU friendly instructions. At the same time, AES uses binary fields for the S-box and Mixcolumns computations, which are generally implemented as a look-up table to be more efficient.

AES's use of a look-up table with an index derived from the secret makes general implementations vulnerable to cache-timing attacks. ChaCha20 is not vulnerable to such attacks. (AES implemented through AES-NI is also not vulnerable).

Daniel J. Bernstein is having significant greater-than-average success in advertising his algorithms. (I'm not implying there are no merits. I'm just stating the fact that his algorithms have success in terms of deployment).

Of course, other reasons justify the choice of AES instead of ChaCha20.
To name a few:

Dedicated instructions on high-end CPUs
Amount of received cryptanalysis
Availability of studies on side-channel (other than cache timing) protections


Is it proven that breaking RSA is equivalent to factoring as of 2021?

There is no proof that the integer factorization is computationally difficult and similarly, there is no proof that the RSA problem is similarly difficult.
The RSA problem
RSA problem is finding the $P$ given the public key $(n,e)$ and a ciphertext $C$ computed with $C  \equiv P^e \pmod n$.
Factoring $\implies $ the RSA problem
This is the easiest part. If we can solve the factoring problem then we can solve the RSA problem by factoring the modulus $n$. This implies that the RSA problem is at least as easy as factoring. This doesn't eliminate the case that it might well be easier.
The RSA problem  $\stackrel{?}{\implies} $ Factoring
The most well-known work on the reverse of the problem goes back to 1998

D. Boneh and R. Venkatesan Breaking RSA may not be equivalent to factoring

We provide evidence that breaking low-exponent RSA cannot be equivalent to factoring integers. We show that an algebraic reduction from factoring to breaking low-exponent RSA can be converted into an efficient factoring algorithm. Thus, in effect an oracle for breaking RSA does not help in factoring integers. Our result suggests an explanation for the lack of progress in proving that breaking RSA is equivalent to factoring. We emphasize that our results do not expose any weakness in the RSA system.

Here, we should note that the RSA problem is the decryption of a specific ciphertext, whereas the factoring reveals the private key $d$ thus all ciphertext under encrypted the same public key.
If we consider the problem of finding the private exponent $d$ then it is proven by Miller to be computationally equivalent to factoring $n$;

1976 Riemann's Hypothesis and Tests for Primality

The below work went on the generic ring model ( in short: a ring has no special property than being a ring) and show the equivalence;

2009 - Divesh Aggarwal and Ueli Maurer - Breaking RSA Generically is Equivalent to Factoring

We show that a generic ring algorithm for breaking RSA in $\mathbb Z_N$ can be converted into an algorithm for factoring the corresponding RSA-modulus $N$. Our results imply that any attempt at breaking RSA without factoring $N$ will be non-generic and hence will have to manipulate the particular bit-representation of the input in $\mathbb Z_N$. This provides new evidence that breaking RSA may be equivalent to factoring the modulus.

This work creates a strong belief in the reverse problem; factoring is equivalent to the RSA problem, however, no proof yet!
Also a notable work on comparing $e$-th root algorithm with the factoring algorithms to see the trend;

2007: Antoine Joux and David Naccache and Emmanuel Thomé When $e$-th Roots Become Easier Than Factoring

We show that computing $e$-th roots modulo n is easier than factoring n with currently known methods, given subexponential access to an oracle outputting the roots of numbers of the form $x_i+c$.

As a result, we still have;
$$\text{the RSA problem} \stackrel{?}{\implies} \text{Factoring }$$

If factoring can be solved in polynomial time ( a common belief noted by Meir Moar) then by using the reduction from Hamiltonian Path to Factoring as Haldeman did in their DNA factoring then with the Karp's 21 reductions we can solve the $NP$-complete problems in polynomial time with factoring.

Dan Boneh's article with 977 citations is a good starting point to see the RSA's 20 years;

1999: Dan Boneh - Twenty Years of Attacks on the RSA Cryptosystem


Why a bulk encryption key and frequently used key needs to have a shorter lifetime?

Most symmetric encryption techniques use an $\text{IV}$. An important characteristic is that the $\{key, IV\}$ pair must never be reused.
The $\text{IV}$ is randomly generated for every use, and some cipher modes (eg: GCM) break it down into one part for the nonce, one part for the counter. eg: for a 128 bit $\text{IV}$, the nonce is 96 bits, the counter is the remaining 32 bits.
The counter usually starts at $0$ for every data and is incremented for each block. So we only care about the nonce.
Given a 96 bit nonce, the birthday paradox tells us that the probability of nonce reuse after $2^{32}$ uses is approximately $2^{-32}$. The $2^{32}$ reuse probability is recommended by NIST.
To reach $2^{32}$ uses in a week, we need to perform approximately $7000$ operations per second. This is not an outrageous number, link-level encryption can easily handle this.
So with heavy usage of a symmetric key, we want to make sure we limit the number of uses to something well below the probability of nonce reuse. Taking safety margins into account for the above example, we might pick one day as a reasonable lifetime.


Shortcuts / practicality of brute forcing block cipher (AES) + ECB with known plaintext

For a key recovery attack, you'd basically need to break AES itself.  There are no known practical key recovery attacks on AES (and if there were, it would not be considered safe to use), so your pretty much only hope would be to find some kind of side-channel attack on the AES implementation, or on the overall crypto framework it is part of.

Alternatively, if you suspect that the keyspace is small enough (e.g. if the key is derived from a passphrase which might not have enough entropy), you might be able to find it with a brute force attack.  The chance of such an attack succeeding depends entirely on two things: the size of the keyspace you need to test, and the speed at which you can try the keys.  The latter, in turn, depends on the computing hardware you have available (and, of course, your skill in utilizing it) and on the complexity of the key derivation process.

Padding oracle attacks, in any case, are specific to CBC mode, and do not allow key recovery.  ECB mode, while insecure in other ways, does not suffer from them.


New Improved Probabilistic version of RSA

The paper is rather sloppily written, however it can be changed into the correct statement.

The statement in the paper is:

  She takes randomly elements $f \in F^*_p$ and checks whether or not $f^{2x}=1$. With probability at least $1 − 1/\ell$ she finds $f$ of order $\ell$.

As written, that's wrong.  However, if we modify it to:

  She takes a random element $f \in F^*_p$ and computes $g = f^{2x}$; if $g \ne 1$ (which will happen with probability $1 − 1/\ell$), then $g$ will be of order $\ell$.

Then it is a correct statement (and is the standard way of generating random elements of order $\ell$).

There are a number of places in the paper like this; places where, as written, it doesn't make much sense, but if you know your number theory, you can deduce what the author actually meant.  I suspect that this can be modified to make a secure cryptosystem; however whether it does have any advantage over RSA (and whether it's actually safe for multiple users to use the same modulus and different exponents) is far less clear.


How to secure Elliptic Curve ElGamal encryption against known plaintext attacks?

Is there any way to compute a different $R$ for every block of data, without using much resources and that too quickly ?

There's no common way. Standard practice is hybrid encryption per ECIES.

In a nutshell, ECIES is the same as EC-ElGamal with regard to $E$, $G$, $\text{privatekey}$, $Q$, $k$, $C$, $R$, but the shared secret $R$ is used (after a key derivation step) as the key to a symmetric authenticated cipher that conveys the message $m$. This removes the burden of mapping $m$ to a point on the curve, which severely limits the size of $m$, and typically is iterative thus has the potential to leak information about $m$ by side channels.

  Does reusing the same $R$ for another message break security (in EC-ElGamal)?

Yes. Assume $m_0$ and $m_1$ mapped to $P_0$ and $P_1$ are encrypted with the same $R$, into $C_0$ and $C_1$. It holds $C_0=R+P_0$ and $C_1=R+P_1$, therefore $P_1=P_0-C_0+C_1$. Thus $m_1$ can be found from $m_0$ and ciphertext. With $R$ fixed, the cipher is insecure under known-plaintext attack.

Additions per comment:

Even if the attacker has no knowledge of a plaintext $m_0$, s/he does learn something about the plaintext. In particular she can tell if $m_0=m_1$, since that's equivalent to $C_0=C_1$. This qualifies as a break, since the objective of encryption is to prevent adversaries from learning anything about plaintext (except its length). As an example, this allows to distinguish between a routine Have a quiet nightshift Joe ($m_0=m_1$) from an exceptional Launch missile to target A ($m_0\ne m_1$).
Doubling $R$ at each message would be extremely insecure. It would hold $P_j+P_j-P_{j+1}=C_j+C_j-C_{j+1}$, and that allows to decipher any message sent encrypted twice, as $P_j=P_{j+1}=C_j+C_j-C_{j+1}$.


Requirements for the modulus in the Massey-Omura three pass protocol

How many bits long should the prime modulus $M$ be in order to be
  secure?

The modulus $M$ should be long enough to prevent discrete logarithms from being computable.
As of 2015 this means 2048 bits length is fine, but for other (official) recommendations you should consult keylength.com

  Should the $M$ be secret?

You can make $M$ secret but making it public shouldn't affect security as long as it's large enough to prevent any discrete logarithm computations from succeeding.

  Should the M be generated every time or it could be reused to generate new keys?

Usually it is rather computationally intensive to generate such moduli. Again, you can generate a new modulus every time if you fear there may be unknown backdoors in public parameters or you want to dodge something like Logjam, but if the modulus is long enough you don't have to generate new moduli on every connection.


Which public key cryptosystems are not based on number theory?

Yes. The McEliece cryptosystem using Binary Goppa codes has withstood cryptanalysis to date. Its hardness is based on decoding. I should note that it has been broken for certain classes of codes.

Another common example is the Merkle-Hellman knapsack cryptosystem. Unfortunately it was broken. It is likely possible to build a secure cryptosystem based on the knapsack problem. I wanted to at least mention this line of work.


Using Diffie–Hellman without a key derivation function

Could we fix this by choosing an element $g$ that generates a large subgroup (of $\Bbb Z_p^*\ $), all of whose elements are quadratic residues? Concretely, we could take $p=2q+1$ for a large prime $p$ and then find an element which generates the order $q$ subgroup.Now, if Diffie–Hellman is done with this group element, any eavesdropper knows the lowest order bit of the shared secret. So I could just remove this bit and use all the higher order bits as the one-time pad, and no information about the shared secret leaks.

That's not safe. Problems:

What the adversary learns is not the low-order bit of the Diffie-Hellman shared secret $a$ as stated. Rather, what leaks is the Legendre symbol $\bigl(\frac ap\bigr)=a^q\bmod p$, which is always $+1$. Therefore, even if we remove the low-order bit, the adversary still learns something about the shared secret, and that's an advantage.
E.g. with $p=23$, $q=11$, $g=3=7^2\bmod p$, the adversary knows that $a$ is among the powers of $g$ modulo $p$, that is $a\in\{3,9,4,12,13,16,2,6,18,8,1\}$ (which low-order bits are rather haphazard). Thus for example if the ciphertext is $101_2$, the adversary can tell that the plaintext can not be $000_2$, because that would imply that $\lfloor a/2\rfloor=000_2\oplus101_2=101_2=5$ thus that $a\in\{10,11\}$, which can't be since $\bigl(\frac{10}p\bigr)=10^q\bmod p\ne+1$ and $\bigl(\frac{11}p\bigr)=11^q\bmod p\ne+1$.
That attack also works for large $p$ and in practical scenarios. E.g. if a name on the class roll was enciphered, then at the cost of two Legendre symbol computations per name on the class roll (one for each of the two possible DH shared secrets), an adversary likely could rule out with certainty about a quarter of the names (those with two negative results), and find another quarter (those with two positive results) among which the actual name is more likely to be than for the remaining of the class roll.
The high-order bit of $a$ expressed as a fixed-length bitstring of $\lceil\log_2(p)\rceil$ bits is not well distributed.
If $q$ has moderate prime factors, then I can't rule out that much more than one bit of information about the shared secret could leak due to the Pohlig-Hellman algorithm.

I conjecture that this variant is safe (ind-CPA):

Pick $p$ a safe prime (that is $p=2q+1$ with $q$ prime), $p$ large (e.g. $4096$-bit), and not of the special form $r^e\pm s$ for small $r$ and $s$.
Chose $g\in[2,p-2]$ such that $g^q\bmod p=1$, implying that $g$ is a generator of the subgroup of the quadratic residues of $\Bbb Z_p^*$, which has prime order $q$.
Perform DH as usual, yielding shared secret $a$.
Truncate $a$ to its e.g. $\lceil\log_2(p)\rceil-k$ low-order bits yielding $a'$, where $k$ is a security parameter (e.g. $k=128$, giving a $496$-byte $a'$).
Use $a'$ for XOR-encryption of a plaintext at most as large as $a'$ (or best, devote some of $a'$ to provide integrity of the message using universal hashing à la Carter-Wegman).

Argument: DH's security hypothesis tells that $a$ is computationally indistinguishable from a uniformly random quadratic residue in $\Bbb Z_p^*$, since that has prime order. I conjecture that these quadratic residues are well-enough distributed on $\Bbb Z_p^*$ that $a'$ is computationally indistinguishable from uniformly random, with the advantage vanishing as $\mathcal O(2^{-k})$.

This is possibly the simplest academically correct way to perform ind-CPA public-key cryptography on a link spied by a passive adversary. But caution: this not commonly used. The accepted practice is to feed the DH shared secret $a$ thru a Key Derivation Function, or Pseudo Random Function / hash such as SHA-256, and use the outcome as a key for an authenticated symmetric cipher such as AEAD_AES_256_GCM_SIV of RFC 8452.