Unless you really want to actually "use" the RSA key in a mathematical way, you could actually just derive a password from it using a key derivation function (KDF) and using the certificate as a password...
There are two different kinds of KDFs: those you use when you have a poor entropy and are afraid of Dictionary Attacks (typically if you store humanly memorable passwords) like Argon2, and those that you use when you have a good entropy, which is the case if you rely on an RSA key. In the latter case, the HKDF is well suited for this.
The advantage of using HKDF is that you already have all the nifty feature you should otherwise implement:

you have a Salt, so you can easily generate different keys, if one is compromised, for example.
you have the notion of the label, so you can generate different keys for different usages.
you have the size as a parameter, so you can easily plug in another encryption function in case AES gets broken, without changing the key generation algorithm.

Nonetheless, just hashing it would still be at least as hard as either:

finding your 'deployment' certificate
finding a preimage to that hash

And in case you worry, since an X509 certificate is certainly not a common password, it would require as much computation power to build a dictionary attack against it than to actually brute-force your certificate... (Which is hard.)
Note that 1. is true since we do not consider obscurity to be of any use, so you should assume that the attacker knows how you derive your secret key.
So in the end, if the "secret key" is compromised, finding the corresponding preimage (aka your certificate) of the cryptographically strong hash is hard for any cryptographic hash.
As hash, I personally like Blake2, since it can produce a digest of any size you may need for AES keys, is fast and is robust, plus it sports a Salt, so you can simply change that salt and keep going if a "secure key" is once compromised. But you could go with SHA-3 (aka SHAKE128 if you want 128 or 190 bits AES keys) and a custom salt you append to your certificate, too. Blake2X is also advertised as a KDF when you have a high entropy source.


It is not entirely clear what your question is, so I just try to explain what CCMP and CCM are, and roughly how they work. Please update your question if this does not answer it.

First of, remember that CCM is a general purpose mode-of-operation for authenticated encryption, while CCMP is a specific way of using CCM within the context of IEEE 802.11 (WiFi).

CCM

CCM is a general purpose mode-of-operation for authenticated encryption defined in RFC 3610. However, since your question is asked in the context of CCMP I specialize the description of CCM to that setting. CCM is a combination of CTR mode encryption and CBC-MAC in a variant of MAC-then-Encrypt. Within CCMP, it uses AES as the underlying block cipher,
and takes as input a 128 bit key $K$, a plaintext $P$, associated data $A$, and a 104 bit  nonce $N$.

To process $P$ and $A$, CCM first computes a CBC-MAC over $A$ and $P$ to produce a tag $T$. It then encrypts $P$ using CTR mode encryption to produce a ciphertext $C'$. Finally, it encrypts $T$ using a single CTR block to produce an encrypted tag $C_T$. The output of CCM is $C$ and $C_T$.

What is missing from this description is how CCM constructs the (128 bit) IV block for CBC-MAC and the (128 bit) initial counter value for CTR mode. Both of these are constructed from the 104 bit nonce $N$ as follows:

$\begin{align} IV &\gets Flag_1 || N || Length(A + P)_{16} \\
CTR_0 &\gets Flag_2 || N || 0^{16}
\end{align}$

where $Flag_1$ and $Flag_2$ are two distinct 8 bit values (you can look up their definitions in the RFC).

CCMP

CCM is a stateless authenticated encryption scheme. As such, it cannot protect against replay attacks. Essentially, the purpose of CCMP is to add replay protection on top of CCM by introducing some state. In particular, CCMP  maintains a 48 bit counter called the packet number (PN in your diagram) which is incremented for each encrypted IEEE 802.11 frame. Since CCMP uses CCM, one of its responsibilities is to create the 104 bit nonce $N$. This is what is shown in your diagram above. Basically, $N$ is created from the 48 bit MAC address of the sender ($A2$ in your diagram), the 48 bit packet number PN, and a 8 bit flag $Flag$ which encodes various IEEE 802.11 settings, in the following way:

$\begin{equation}
N \gets Flag || A_2 || PN
\end{equation}$

Thus, when this 104 bit nonce is feed into CCM, the 128 bit IV and 128 bit initial CTR value, will look like this:

$\begin{align} IV &\gets Flag_1 || Flag || A2 || PN || Length(A + P)_{16} \\
CTR_0 &\gets Flag_2 || Flag || A2 || PN || 0^{16}
\end{align}$

This is essentially all that is happening in your diagram above. The value TK corresponds to what I called $K$ as the input to CCM.


How to reverse engineer a cryptography algorithm if some input-output pair is known.

It is not possible to reverse-engineer a good encryption algorithm from plaintext/ciphertext pairs alone; it might not even be possible to test the validity of a guess unless a matching key is known (but it is often possible to rule out a guess; e.g. if individual cryptograms are 64 bytes, that's not RSA with a decent key size).

Among techniques to reverse-engineer a good encryption algorithm:

Using social engineering/bribery/spying to obtain info; experience proves that even partial info helps a lot.
Obtaining and analyzing a hardware implementation (e.g. using electronic or atomic-force microscopy).
Obtaining and de-compiling the object-code of a software implementation.
Getting extra information from a working implementation using some side channel (e.g. JTAG debug port; micro probing the bus, or for self-contained ICs perhaps with the help of ion-beam implantation technology; power analysis; timing); ideally, the attacker wants to see the data the algorithm is manipulating along its execution; but even lesser information is useful (e.g. if encryption timing varies as a deterministic function of the plaintext value for constant plaintext size, the algorithm is not a plain implementation of Salsa).
Using fault injection to cause nasty things to happen (like, glitching the power supply or lighting the IC with a laser pulse at reset, in hope of entering a debug mode that allows the attacker to reach one of the previous goals); also, careful examination of erroneous data output caused by fault injection might allow confirming an hypothesis on the algorithm, and finding the key.

Reverse engineering a bad encryption algorithm depends very much on the algorithm; sometime it is possible, there are even generic techniques for entire classes of algorithms, see this for anything affine, including linear.


How costly is to find millions of large prime numbers for RSA?

Yes, this is doable.  Here is a construction, built out of several basic primitives:

Let $R$ be a randomized  primality generation algorithm; there are many of them.

It uses randomness, so let's make the bits of randomness it uses explicit as input: $R(c)$ is the output it produces, when given a random number generator that outputs the random bits $c$.
Let $G$ be a cryptographically secure pseudorandom generator: something that stretches a short seed (key) to a long pseudorandom output.  You could use AES in CTR mode, or any stream cipher, for this.
Let $H$ be a cryptographic hash function, e.g., SHA256.

Now, to element $x$, you can assign the prime number $R(G(H(x)))$ to $x$.  It's as simple as that.

This is a deterministic algorithm that will assign a prime to each element, and always assign the same prime to each possible element.  Also, if you generate primes from a large enough range, then the primes will almost surely be distinct.  For instance, if you generate 256-bit primes, then by the birthday paradox, it is essentially guaranteed that all the primes will be distinct (the chances that two different elements $x,x'$ is exponentially small, and negligible in practice).


AES-GCM has the following problems:

In the case of nonce reuse both integrity and confidentiality properties are violated. If the same nonce is used twice, an adversary can create forged ciphertexts easily.
When short tags are used, it is rather easy to produce message forgeries. For instance, if the tag is 32 bits, then after $2^{16}$ forgery attempts and $2^{16}$ encryptions of chosen plaintexts (also of length $2^{16}$), a forged ciphertext can be produced. Creation of forgeries can be instantaneous when enough forgeries have been found.
GCM security proof has a flaw. It has been repaired recently, but the new security bounds are far worse for nonces not 12 bytes long;
GCM implementations are vulnerable to timing attacks if they do not use special AES instructions. The vulnerability remains even if the AES itself is implemented in constant-time. Constant-time implementations of GCM exist, but they are rather slow.
GCM restricts the message length to 68 GBytes, which might be undesirable in the future. The total amount of data allowed to encrypt on a single key is limited by $2^{64}$ blocks, but this number decreases if long nonces are allowed.
Reasonably fast implementations of GCM require specific lookup tables, which do not fit into fast memory (L1 cache or similar) on some architectures.
GCM is vulnerable against cycling attacks; bad values of the internal $H$ key, which can be pre-calculated for specific AES key values, can negatively impact security.


Combining classical attacks and quantum cryptanalysis

The short answer is: Of course! Why not!

It is pretty easy to build an artificial secret key encryption scheme that is based on RSA and breaks if the adversary has a quantum computer*. Of course no one would want to build a symmetric primitive out of number theoretic assumptions as that would defeat the main purpose of being far more efficient than asymmetric crypto (the usual exceptions left aside...VSH...). However, symmetric primitives might provide exploitable structure that we just did not find yet. Indeed, in a far stronger security model where the adversary gets quantum access to honest parties (i.e., the CPA oracle) one can actually break several secret key encryption schemes as they are vulnerable to period finding algorithms. Therefore, the conventional effort of cryptanalyzing symmetric primitives has to be enhanced by the study of quantum algorithms.

[*] capable of running Shor's algorithm, which breaks RSA.


Can one make a secure AEAD from any secure cipher and any secure MAC?

The encrypt-then-MAC paradigm works as long as the encryption is CPA secure and the MAC is secure under the standard definition. However, such a MAC must be secure for multiple messages. Therefore, using GHASH or Wegman-Carter authentication is not sufficient. (Indeed, in GCM, the result of GHASH is masked and not directly output.)

The proof of the general composition appears in two papers: The order of encryption and authentication... by Hugo Krawczyk, and Authenticated encryption: relations among notions... By Mihir Bellare and Chanathip Namprempre.

It is important to note that the paper by Krawczyk actually shows that in some important cases it is secure to MAC-then-encrypt. However, this is only true when the operations is atomic and it is impossible to know whether the MAC was incorrect or another error occurred.

However, in practice this is almost impossible to do right and has been the cause of multiple attacks on SSL over the past years. Therefore, this part of the paper should not be seen as saying that it's OK to every MAC-then-encrypt.


Length of message in RSA and splitting of long messages

Yes, hybrid crytography is generally used; hybrid crypto combines asymmetric cryptography with a fast symmetric cipher to do the bulk of the work.

Either the keys are generated using RSA-KEM (and a Key Derivation Function) or - and this is much more common - a random symmetric key is encrypted using RSA with PKCS#1 padding or the more secure OAEP padding - the key encapsulation talked about in the Wikipedia article.

Messages are usually not split at all; most cryptographic libraries do not directly support concatenating blocks of RSA ciphertext. That is not a standardized mode of operation for RSA.

Keys are not specific to the RSA mode used (just like you can use an AES key for about any kind of mode, ECB, CBC, CTR etc.). Sometimes X.509 certificates do contain a specific signature generation / verification algorithm to be used, but the key is usable for any RSA based algorithm.

Notes:

With most RSA modes for encryption the padding which is required to make RSA secure introduces overhead. The ciphertext will be of the same size as the modulus (in bytes), but the amount of plaintext that can be encrypted is reduced by at least 11 bytes for PKCS#1 v1.5 padding and even more for the OAEP padding modes. Of course for any secure RSA key size there will be plenty of room for a symmetric key - or even an IV, encryption key and authentication key if the protocol requires it.
The message (+ padding overhead) can be of the same size as the modulus, as long as the numerical representation of the input to the RSA modular exponentiation is smaller than the modulus. Otherwise the modular reduction will be performed on the input, which means you would get a value that is one or more times the modulus smaller than the input. RSA modular exponentiation is about numbers, not bits; there are special functions called OS2IP and I2OSP in RSA PKCS#1 to convert between binary and number values.


Case insensitive verification of HMAC / Base64 signature

Your worst case scenario is that all $18$ characters in the Base64 string are letters — this allows for $2^{18}$ possible collisions due to case-insensitivity. A normal SHA-1 hash is $160$ bits, and therefore has $2^{160}$ possible combinations. Divide by the number of collisions, and you have an effective strength of $142$ bits.

That said, I wouldn't necessarily recommend this. Far easier and less dubious would be to use Base32, which only uses uppercase letters.


Difference between salted hash and keyed hashing?

Keyed hashing is usually used to build message authentication codes (MACs), the most common of which is the hashed-based MAC (HMAC).

MACs are basically cryptographic checksums. They are used to detect when an attacker has tampered with a message. Therefore they require a secret key (to be withheld from an attacker) and should be as fast as possible (to reduce overhead).

Salted hashing has a completely different purpose, which you noted. Because they are intended to deter brute-force attacks, they are intentionally designed to be slow. Also, as you said, salts are not assumed to be secret.

You can build a salted hash out of a MAC by using PBKDF2, which basically applies the MAC a lot of times (to make it slower).


"seed" and "seed key" are NIST terminology talking about the X9.31 PRNG.  In particular, it has a state that consists of:

A 3DES or AES key (the "seed key")
A 64 or 128 bit current state (the "seed")

The requirement is to check to make sure that two don't happen to be the same (and give an error indication if they are).

If you're wondering "except for the AES-128 case, don't they have different lengths (and hence always distinct)", well, this requirement got interpreted (at least, for 3DES, when I went through the FIPS process) as "compare the seed to each of the individual DES subkeys, and fail if any of them match"; I presume something similar is done in the case of AES.

And, yes, this requirement is really stupid; it's #1 on my list of "why ignorant bureaucrats should not design cryptographic requirements".

Also, you're probably better off implementing one of the 800-90 RNGs; those are faster, better designed (now that the Dual-EC RNG was removed), and don't fall under this requirement.


Can you help me understand PFS and wPFS?

The difference between weak and strong perfect forward secrecy lies in the capabilities of the attacker. Perfect forward secrecy is strong if it remains secure in the face of an active attacker, while weak perfect forward secrecy's security claim only covers passive attackers.

If I'm not mistaken weak perfect forward secrecy (wPFS) is a term introduced to claim perfect forward security for a 2-message protocol, disregarding MITM attacks.

A quick Google search revealed that this term was probably coined by Hugo Krawczyk in his 2005 paper HMQV: A High-Performance Secure Diﬃe-Hellman Protocol.

I don't know how commonly understood this term is however, so if you're intending to use it for a paper make sure to explain it.


To answer the question we first need to take a quick look at how XTS encrypts data:

$$C=E_{k_1}(P\oplus(E_{k_2}(n)\otimes\alpha^i))\oplus(E_{k_2}(n)\otimes\alpha^i)$$

With $\oplus$ denoting bitwise XOR, $n$ denoting the sector index, $i$ denoting the block index within the sector. $\alpha$ is a polynomial in the $GF(2^{128})$ and is exponentiated appropriately and multiplied ($\otimes$) with the encrypted sector index.

As you can see you don't need to alter either the key $k_1$ or $k_2$ for each sector as the indices will introduce a unique whitening value for each block.


(EC)DSA signature without hashing, or with offloaded hash?

Let's focus on DSA. The signing on a message $m\in \mathbb{Z}_q$ for the suggested "no-hash" protocol is done as follows:

Pick $k\in_R \mathbb{Z}_q$, compute $r=f(g^k)$, where $f(\cdot):=(\cdot \bmod p) \bmod q$.
Compute $s=k^{-1}(m+xr)\bmod q$
Return $(r,s)$ if the signature is not degenerate.

The verification algorithm, on input $(m,s,r)$, checks if $f((g^m\cdot y^r)^{(1/s)})=r$.

The following consists of a forgery on a random message under the key-only attack.

Let $K=g^a\cdot y^b$, where $a,b\in_R\mathbb{Z}_q$
Compute $r=f(K)$, and set $s=r/b$
Return $(r,s)$ as a forgery on $m=(a\cdot r)/b$

(I'll add the references in due course.)


Significance of Extended Euclidean Algorithm in Cryptography

The significance of the EEA is that it gives an efficient way to compute modular inverses. Since computing modular inverses is an extremely common task in practical cryptography (among many others, you need it to derive the decryption exponent of an RSA keypair from the encryption exponent), the fact that it can be performed efficiently, as demonstrated by the existence of the EEA, is fundamental. If it couldn't, many of the cryptographic schemes in use today just wouldn't work.


Let me see if I have this right (and please correct me if I misunderstand; my conclusions depend on the details of this); you distribute images for your firmware device; these images are encrypted with a secret AES key (using AES in CBC mode); the device decrypts the image, and then runs that decrypted image.  The sole check to make sure that the image wasn't tampered with is the hope that a modified image would not decrypt to anything intelligible.

If the above is all true (and personally, I hope that I'm wrong and you're doing more than this), then you have bigger problems than having a fixed IV.

The problem is that you're assuming that an attacker cannot modify the image to make changes that he picked out; the problem with CBC mode is that, to a surprising extent, he can.  Here's one way he can do this: suppose you have a constant initializer in your image, as follows:

  static int important_variable = 3;

Suppose further that the attacker decides that he'd get an advantage if that important_variable was initialized to 5.  What the attacker could do is find where the constant 3 appears in the image, and (here's the tricky bit) exclusive-or the previous block in the ciphertext by 6.  To see what this does, let us review how CBC mode decryption works:

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

(where $C_{i-1}$, $C_i$ are the ciphertext blocks, and $P_i$ is the decrypted blocks.

Now, the attacker has no idea what the key $k$ is, however he doesn't care, he knows that $3 = C_{i-1} \oplus D_k(C_i)$.  By adjusting $C_{i-1}$ into $C'_{i-1} = C_{i-1} \oplus 6$, and making no changes to $C_i$, the modified ciphertext will decrypt there into $P'_i = C'_{i-1} \oplus D_k(C_i) = C_{i-1} \oplus 6 \oplus D_k(C_i) = 6 \oplus 3 = 5$, hence making the change he desired.

The sole disadvange (as far the attacker is concerned)?  The previous block $P_{i-1}$ will decrypt to something unpredictable (because he has no idea what $D_k(C'_{i-1})$ evaluates to), however that block might not be important.

The bottom line: if you care about integrity (as opposed to secrecy), you need to use a cryptographical primitive that gives integrity guarantees (such as a Message Authentication Code or a signature).


TLS - sharing 1792 bits of unidirectional keys

In TLS, the key exchange step results in a key called the master secret which is then derived into as much key material as needed with a custom key derivation function, called in TLS terminology the PRF. It is not slow -- contrary to PBKDF2, the "PRF" of TLS is not for handling password and thus has no need to be slow.


Is it possible to find the key for AES ECB if I have a list of plaintext and corresponding ciphertext?

Assume I have a list of plaintext text and its corresponding ciphertext which was created using a specific key with AES in ECB mode.
Can I recover that key?

No.  This is what is referred to as a known plaintext attack, and secure block ciphers are designed to prevent exactly this kind of attack.  This answer on the Mathematics Stack Exchange goes into more detail about the notion of IND-CPA ("indistinguishability") which AES is conjectured to meet and how that implies that a known plaintext attack is impossible.


Are poly1305 authenticators distinguishable from random data?

No, they are not distinguishable from random.

The Poly1305-AES authenticator is defined as:

$$
(((c_1 r^q + c_2 r^{q−1} + ... + c_q r^1 ) \bmod {(2^{130} - 5)}) + \operatorname{AES}_k (N)) \bmod 2^{128}
$$

Since it is the sum of an AES output and some other number modulo $2^{128}$, it is PRF if:

the AES output is PRF and
the two numbers are independent.

AES output looks like PRF as long as you see less than ~$2^{64}$ of them and $k$ and $r$ are required to be independent (since they are chosen from a uniform distribution), so the authenticators are indistinguishable from random at least as long as you see significantly fewer than $2^{64}$ of them.


Any benefit to writing a message as a mix of 2 languages before encryption?

Historically, there did exist a benefit to using a language that the adversary was not familiar with.  The name for this is code talkers, and the most famous ones (at least in the USA) are the Navajo code talkers of World War II.  The idea was to defeat attacks that relied on statistics about the language used in the plaintext.

In modern cryptography, however, there is no benefit, because modern ciphers are designed to obscure any patterns in the plaintext—even patterns that we haven't thought of.  This is because modern ciphers are expected to be not just "hard to crack," but indistinguishable from random data.

There's a second reason why using multiple languages would not have any benefit, which is that you're using a computer, so no matter what language you use you're still encoding text into a character encoding like UTF-8—and this already gives you statistical patterns that an attacker could look for.

Third reason: English and Japanese are both widely spoken languages with lots of example text available.  There's a reason why code talkers tended to use aboriginal languages.

Fourth reason: Kerckhoffs' principle.  Your cryptographic system should not rely on the secrecy of simple tricks like what you propose.


How to build a secure AE scheme with generic composition?

You might look at EAX mode, which combines a block cipher in CTR mode with a CMAC.  However, EAX does differ from generic Encrypt-than-MAC in that EAX uses a single master key, which would be an absolute no-no for Encrypt-then-MAC.  Normally using the same key for both purposes is quite dangerous, but EAX is explicit about the use of the master key for the cipher and MAC, and EAX comes with a formal proof of security for that usage (and the entire mode).

Given that EAX (and CCM to a less flexible degree) provide a proven method for encrypting and authenticating data, for practical purposes my advice would be to just use one of the well known and trusted AEAD modes.

For theoretical purposes, the answers to Why choose an authenticated encryption mode instead of a separate MAC? and Should we MAC-then-encrypt or encrypt-then-MAC? should give you a good idea of the steps required to define a your own general composition, and how tricky it is to get all of those right.

The EAX paper also describes and proves the security of an EAX2 mode, which is a generic composition approach to create a two key AEAD mode based on a cipher and a MAC.


Are NIST's changes to Keccak/SHA-3 problematic?

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

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

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

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

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

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

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

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


Are there Guaranteed Proof-of-work Systems?

You could use a challenge consisting of multiple subtasks.

For example, provide a unique random string of characters $R$ and ask for $n$ distinct strings that have $R$ as a prefix and whose SHA256 sum ends in $z$ zeros.

In a single hash calculation, the probability of a lucky guess is $2^{-4z}$, so the probability of multiple lucky guesses in one challenge is going to be very small if $z = 10$.

The number of SHA256 calculations needed to pass the challenge is of the order of $n \times 2^{4z}$, but only $n$ hash calculations are needed to check the results (plus a little extra to check that no two strings are the same).


Whether ramp secret sharing possess additive homomorphism?

It does indeed. I've written a bit about this here with code examples: https://mortendahl.github.io/2017/06/04/secret-sharing-part1/#packed-variant.


Replacing a block cipher's key schedule with a stream cipher

The requirements of a key schedule would be easily met by Salsa20, or any PRF for that matter. A key schedule is similar in purpose to a cryptographic hash functions (which Salsa20 is built off of), but the requirements are not as strict. For example, a preimage attack is fatal to a hash function, but being able to calculate the original key given only the round keys is not a huge deal for a key schedule. For this reason, key schedules typically do not involve particularly computationally-intensive operations and instead opt for much simpler and more lightweight algorithms.

From a paper referenced by the answer linked above, there are several classifications of key schedules. A Salsa20-based key schedule would fall under category 2B, the strongest practical category. That is, every bit in the master key influences every bit in every round key. Changing any one bit in the master key will change, on average, 50% of bits in all the expanded round keys.


Is there any benefit to *really* strong passwords?

I'll assume those were generated by selecting characters independently and uniformly at random, out of a set of 95 characters.  Entropy is the base 2 logarithm of the number of equiprobable choices, so each character chosen independently at random contributes $\log_2(95) \approx 6.6$ bits of strength to your password.  So the strength of password_one is about $37 \times 6.6 = 244.2$ bits.

That's already stronger than any cryptographic key will ever realistically need to be—it's comparably strong to a 256-bit key.  It's strong well past the point where the choice of password hashing algorithm is relevant; if people could be reliably counted on to memorize passwords this strong, we wouldn't need such algorithms.  People choose terrible passwords; the often-cited XKCD password strength comic famously pegged passwords like Tr0ub4dor&3 at about 28 bits, and even that is likely much better than average.

That means that your password_one is, arguably, total overkill, because:

Passwords need to be user-friendly.  For example, they need to be convenient to type or input into one's device.
If your password is this crazy strong, that just means that your weak point is somewhere else, and it's likely way, way weaker than the crazy password.  You're well past the point of diminishing returns.

If you're just a regular Jane or Joe who is not subject of special interest by spy agencies and such, I think 80-bit(ish) strength passwords are plenty strong enough for website logins; a 12 character random ASCII character password (e.g., Z;$]bnNvY3I-) is at about this level, and much more convenient than what you're doing.  For password-based encryption you could consider going up to about 128-bit strength.


Does there exist a Cipher / Hash identification tool?

No, such a tool does not exist and could not exist for any modern, secure cipher. If you do not have access to the key, you cannot correlate plaintext with ciphertext. For a hash algorithm, you can heuristically guess what the algorithm may be based on the length of the output, but that would only allow you to classify the digest as being from one of any number of possible hash algorithms. For example, a 160-bit output could be SHA-1, or maybe RIPEMD160, but not MD5.

If you have the input to the hash algorithm as well as the digest, then you can determine with certainty which hash algorithm was used to create it simply by running the input through all candidate hash algorithms and seeing which one results in a matching digest for that input.


How can ECDSA signatures be shortened (to be used as a product key)?

The web site of https://ellipter.com says, they are using encryption.


Is there any benefit to verifying PKCS#7 padding when using AES CBC and HMAC?

In general, use a cryptographic MAC to protect your ciphertext, and verify it first. Emit those errors. Then padding errors should not occur at all.

The "in general" seems to have been used to show that commonly is performed or should be performed. I don't think it had anything to do with the security of the scheme itself.

PKCS#7 compatible padding can range from 1 to 16 bytes for block ciphers such as AES. If your plaintext always happens to be $n * 16 + 15$ bytes in size then your padding would consist of a single byte. A single byte is never enough to guarantee integrity of the plaintext.

Padding isn't a checksum. It doesn't say anything about the value of the plaintext. It tells you only something about the size of the plaintext.

Even if you would be able to use padding as an integrity check then you shouldn't use it for transport protocol security. Padding checks allow padding oracle attacks to be performed. For instance OpenSSL uses sign-then-encrypt and requires special care to avoid padding oracle attacks.

Note that modern protocols often allow modes such as CTR or authenticated ciphers. Almost all authenticated ciphers based on block ciphers are based on CTR (i.e. CCM, GCM and EAX mode are all based on CTR mode to provide confidentiality). CTR doesn't use padding at all. So you can often avoid the use of padding pretty entirely.

This also shows that padding mode is not a requirement to validate the correctness of the plaintext. If it was, all current authenticated ciphers would fail.

Padding should not be used for verifying correctness period. It should just be used for determining the length of the plaintext.

[CHANGED] After verifying the integrity you should check all the padding bytes, if just to verify the correctness of the implementation. Another reason to check the other bytes is to avoid worrying about subliminal (covert) channels. A slight disadvantage would be that you couldn't use the same unpadding code to handle PKCS#7 and the withdrawn ISO 10126 padding (and you should make sure you don't break anything if you change existing code with that in mind).

It does make sense to check if the value isn't out of range, i.e. between 1 and the block size. You don't want to handle issues with index-out-of-range or partial information in the code surrounding the cryptographic routine.

An even better solution would be to use a mode that doesn't require padding at all. A good candidate would be the aforementioned CTR mode of operation which turns AES into a stream cipher or one of the authenticated (AEAD) ciphers.


Is it safe to encrypt a part of the message with RSA and the rest with AES?

You can put in as much data into RSA as it can hold, bar the padding. The padding is required to keep RSA (provably) secure - presuming that RSA is secure itself of course.

So yes, what you are supposing is perfectly possible. It actually has a name: encryption with partial message recovery.

I found one paper that claimed that the security is may not be be provable secure, so beware that you're threading on largely uncovered ground here; there aren't any standardized schemes out there.

It may not be optimal to use current padding techniques as you would about double the randomness in the encryption scheme: once for the secure padding itself and once for the AES key. On the other hand, this is the best you can do with standardized functions libraries.

That said, the overhead of RSA-OAEP is only about 42 bytes, so for a 2048 bit RSA key and a 128 bit AES key (about the minimum key size) there would only be a static overhead of 42 + 16 = 58 bytes, leaving 256 - 58 = 198 bytes for the message itself.

If you require protection against active attacks that may alter the ciphertext you may need to include an authentication tag over the rest of the message, adding another 8 to 16 bytes for e.g. AES-GCM.

I'd propose a scheme such as this:

R = M | RSA-PSS-SHA256(Sk, M)
K = Rand(k)
r1 = s / 8 - 42 - k / 8
R1 = Sub(R, 0, r1)
R2 = Sub(R, r1)
C = RSA-OAEP(Pk, K | R1) | AES-GCM(K, R2)

Where:

M is the message
R is the signed message (using the sender's private key)
K is an AES key of length k bits
Rand is a cryptographically secure random number generator (or key generator operating in bits)
s is the receivers key length in bits
o is the OAEP overhead in bytes (using SHA-1 for the underlying MGF1)
r1 is the size of R1, r2 is the size of R2
R1 is the partial message encrypted using RSA-OAEP
R2 is the partial message encrypted using AES-GCM
Sub takes a substring of the given array and offset, and optional end offset
C is the resulting ciphertext, including the AES-GCM tag

The IV for AES-GCM can be left at 12 zero bytes (as the AES key gets regenerated each time anyway).

Notes:

if you use normal PKCS#1 signing that you leak information about the message that you encrypt. So you should use PSS padding or you should encrypt the signature as well. Above scheme uses a combination of both;
while you're at it you might want to look for RSA-PSS-R, which is a scheme for signatures giving message recovery, defined here and in IEEE P1363a;
to show a more efficient scheme, try this if you're academically inclined - it also includes a proof of security;
it is also possible to use RSA-PKCS#1 and AES-CBCbut beware that those are not IND_CCA secure and that you should not allow padding oracle attacks.


How to perform Shamir Secret Sharing with a Tabula Recta?

Taking the question as literally as possible, I have provided my pencil and paper tables for a scheme among three parties with a polynomial of degree 2 and a field of $\mathbb{Z}_5$ to keep things feasible for a pencil and paper example. Given the tables, in order to reconstruct any secret look up the table to be used by the share from party 1 (table numbers are denoted in a box to the upper left of each table), the row to be used by the share from party 2 and the column to be used by the share for party 3.

I've provided an example polynomial $4x^2+3x+1$ which evaluates correctly to 1, the secret, at $x=0$, 3 when $x=1$, 3 when $x=2$, and finally 1 when $x=3$. Then, to reveal the secret, take these shares and look them up as described. I've boxed in red the correct value from following the described procedure. This set of tables should work for any polynomial valid in the field described and for shares based on players associated with the same values for $x$.
$\mathbb{Z}_5$">


The parameters included in TLS 1.2 server signature in the ServerKeyExchange

Section 7.4.3 specifies this:

  struct {
      select (KeyExchangeAlgorithm) {
          case dh_anon:
              ServerDHParams params;
          case dhe_dss:
          case dhe_rsa:
              ServerDHParams params;
              digitally-signed struct {
                  opaque client_random[32];
                  opaque server_random[32];
                  ServerDHParams params;
              } signed_params;
          case rsa:
          case dh_dss:
          case dh_rsa:
              struct {} ;
             /* message is omitted for rsa, dh_dss, and dh_rsa */
          /* may be extended, e.g., for ECDH -- see [TLSECC] */
      };
  } ServerKeyExchange;

The meaning of digitally-signed is explained in section 4.7. In this case, the above means that the input to the signature algorithm (i.e., that which is hashed) is the concatenation, in that order, of:

the client random (32 bytes), as sent by the client in the ClientHello;
the server random (32 bytes), as sent by the server in the ServerHello;
the encoding of the ServerDHParams structure. This is the complete encoding, including length bytes.

The ServerDHParams structure is itself defined as:

  struct {
      opaque dh_p<1..2^16-1>;
      opaque dh_g<1..2^16-1>;
      opaque dh_Ys<1..2^16-1>;
  } ServerDHParams;     /* Ephemeral DH parameters */

Thus, what goes in the hash function, immediately after the 64 bytes for the client and server randoms, are the two bytes that encode the length of dh_p, followed by dh_p; then the two bytes for the length of dh_g, then dh_g; finally, the two bytes for the length of dh_Ys, then dh_Ys.

Since the ServerDHParams structure is itself sent over the wire as part of the ServerKeyExchange, it is simpler to think of it as follows: what is signed is exactly the concatenation of the client random, server random, and the bytes encoding the ServerDHParams, as sent and received.


Proving statistically hiding for a simple commitment scheme in the ROM

Statistical hiding for a commitment is not about the distribution of inputs associated with a given commitment output, but rather the distribution of commitment outputs associated with a given pair of messages.
What you need to show is that for any two fixed messages, the total variation distance between the two distributions of outputs is small. Now, the statistical distance is a metric and so the triangle inequality applies. A good choice for the third distribution is the uniform distribution on $2^k$ outputs. The random oracle model means that the total variation of the distribution of outputs for a fixed message has small total variation distance from uniform and so by the triangle inequality, the distribution of outputs for two fixed, distinct messages has small total variation distance.


Distributed generation of random numbers

The commit-then-reveal approach above is not secure as it allows an attacker to bias the output by forcing the protocol to restart. For an overview on generation of distributed unbiasable randomness, checkout our research paper: https://eprint.iacr.org/2016/1067.pdf

A Golang prototype of RandHound, one of the protocols proposed in the above article, is available in the DEDIS cothority project of EPFL: https://github.com/dedis/cothority/tree/master/randhound


Some background on formal key-exchange models

The goal of a key-exchange (KE) is to establish a session key between two parties. Naively, we could say that a KE is secure if no adversary will be able to figure out the session key (in full) established between two honest parties. However, in formal security models we take this a bit further and insist that the adversary should learn nothing about the session key, i.e., the adversary should not be able to glean any partial information about the session key from observing (and possibly interfering with) the KE.

This is formally captured by challenging the adversary on a target session of its choice. The challenge consists of first flipping a secret bit $b$ . If $b$ comes up as 0, then we return the actual session key to the adversary, while if it comes up as 1, then we return a randomly drawn key of the same length (completely independent of the KE). Now the adversary is supposed to guess which key he was given: real or random? If he cannot guess which key he was given with much better probability than $1/2 $, then we say that the KE is secure. This "game" is completely artificial of course, but it nicely covers the idea that the adversary should learn nothing about the key, and is an example of the kind of "over-provisioning" present in formal security models.

In addition, we also allow the adversary to reveal the session keys of sessions unrelated to the target session (if we allowed the session key of the target session to be revealed, then the "game" above would ofc be completely trivial to win). What unrelated means can be quite technical to formulate, but intuitively it means that if $A$ and $B$ runs a KE between them, then this is unrelated to the KE session $A$ established with $C$ for instance, (or $B$ with $C$, or $D$ with $E$, etc...). Thus, if the attacker picks the $A \longleftrightarrow B$ exchange as its target, then it should still be allowed to reveal the session key from the $A \longleftrightarrow  C$ exchange. If the KE is secure, then learning the session key from the $A \longleftrightarrow  C$ exchange should not help the attacker learn anything about the session key in the $A \longleftrightarrow B$ exchange.

The UKS attack

In the UKS attack, there are two formally (in the sense of the security model) unrelated KE sessions: $A \longleftrightarrow B$ and $M \longleftrightarrow B$. This allows the adversary to reveal the session key from one, and still pick the other as its target session.

  But, I thought the key is the same in the two sessions...

And this is exactly where the attack comes from! In practice these two exchanges are not unrelated at all, so when the adversary reveals the session key from, say, the $M \longleftrightarrow B$ session, then it also knows the session key of the $A \longleftrightarrow B$ session.
From the point of view of the formal security model, the $A \longleftrightarrow B$ session is still a considered a valid target, so $M$ can trivially win the game (i.e., guess the value of the secret bit $b$).


Given generator $g$ with prime order $k$ in $\bmod P$. Does increasing $P = 2 \cdot c \cdot k +1$ decrease security? Increasing $g$ increase security?

If now the prime value $P$ gets increased for constant $k$ (order of $g$ still $k$) does this decrease the security?

No, for random choice of $g$ among $g$ with large constant order $k$.

  Why this? If $P \rightarrow \infty$ it would be the normal logarithm ..

When $P$ grows, $g$ also grows. So we never reach the threshold where $g^a<P$. Thus we can not use the normal logarithm.

  The smaller the better (for same $k$)?

Uh, no, on the contrary! The above says that larger $P$ does not decrease security. Correspondingly, larger $P$ tends to increase security. However, very large $P$ does not much increase security, because the best known algorithms we have for the discrete logarithm for fixed $k$ and large $P$ perform a number of modular multiplications modulo $P$ that is a function¹ of $k$ only, and the time necessary for a multiplication modulo $P$ grows relatively slowly with $P$: in the order of $O(\log^2 P)$ for the simplest and common methods².

  Any boundary for best security?

Only a lower boundary, and that's a nontrivial subject. The short answer might be: at least $2^{4095}$ (that is $P$ of $2^{12}$ bits) with $P$ not chosen close to the power of an integer.

The long answer includes that security against classical computers (not hypothetical quantum computers usable for cryptanalysis per e.g. Shor's algorithm) is believed to be limited by several possible attacks:

the Number Field Sieve, which efficiency is governed mostly by $P$, and which general form the General Number Field Sieve (the only form likely to be applicable to $P$ not chosen close to the power of an integer, a situation where the Special Number Field Sieve shines) is believed to require a $P$ in the order of at least $2^{11}$ to $2^{13}$ bits for security.
Pollard's rho, which efficiency is governed mostly by $k$, requiring a $k$ in the order of at least $2^8$ to $2^9$ bits for security.
Pohlig–Hellman (and possibly other algorithms) depending on the factorization of $k$, that do not work as well as Pollard's rho when $k$ is prime.

  Would be a higher value for $g$ increase security?

Not much. The influence of $g$ on security is usually neglected for the aforementioned three algorithm. I doubt it can exceed $\mathcal O(\log g)$ (which can be approached in Baby-step/Giant-step). Also, I know no way to select a very small $g$ with order $k$ and $\log_2(k)\ll\log_2(P)$, much less for prime $k$, which is desirable for various reasons including blocking Pohlig–Hellman.

  Or to be more certain would a higher smallest group element $\ne 1$ increase security?

Not that we know. Also I know no way to insure that for large parameters.

What we are discussing is a Schnorr group. There are well established methods to generate these, including from a public seed so as to tame suspicion of weak parameters. See FIPS 186-4, appendix A (which uses $p,q$ where the question and answer use $P,k$).

¹ That function is at most about $\alpha k^2$ for a constant $\alpha$ in the order of $2$ depending on a variety of details. But that's immaterial to the reasoning in the paragraph with this note.

² The cost can get down to $O(\log^{1.585\ldots}P)$ with Karatsuba which sometime is used; $O(\log P\;\log\log P\;\log\log\log P)$ with Schönhage-Strassen which could be of interest for insanely large $P$, and $O(\log P\;\log\log P)$ with Harvey-Hoeven (a bleeding edge result which seems unlikely to have practical application).


Is Mathematics or Computer Science more important for a career in cryptography

This question can be closed because the answers are opinion based. Nevertheless...

It depends. It does not look like they are going to design essentially new algorithms for encryption, signature, voting, etc. They have focus rather on applied aspects. In particular, they expect you to study and evaluate cryptographic algorithms and protocols of specific hardware and software. To be able to do that you definitely need skills in computer science.

Why are you asking about data structures particularly? It is a small topic compared to the others. Yes you should learn it, not because of this job, but because otherwise you will not be able to program.

To your questions: Yes, programming skills are important for this type of job.

Which topics are relevant? For this job following topics seem to be relevant:

Cryptography (of course)
Number theory
Programming
Software Architecture
Computer security
Networking


Pohlig-Hellman: While solving in a subgrp, why is multiplication done mod the parent group's $p$ while the exponent is expanded as per $p_i$ of subgrp

The question's example asks finding the solutions $x$ of equation $a^x\equiv b\pmod p$ given $p$, $a$, $b$, with $p=8101$, $a=6$, $b=7531$. It's stated $a$ is a generator of $\mathbb Z_{8101}$, but it's meant $\mathbb Z_{8101}^*$, which is the multiplicative group modulo $p$. The $^*$ (or $^\times$) means we use the multiplicative law of the ring of integers modulo $p$, or equivalently that we form the group by keeping the elements of the ring that are invertible, as mandated by a group axiom. In particular, that implies we exclude $0$, and any $c$ with $\gcd(c,p)\ne1$.
That Discrete Logarithm Problem is modulo prime $p$, a simplifying special case¹. The aforementioned group $\mathbb Z_p^*$ is thus² cyclic. It has order $n=p-1$, that is $n$ elements which we can designate by their integer representative in range $[1,n]$. The order of any element $c$ of that group, defined as the smallest integer $\ell>0$ with $c^\ell\equiv1\pmod p$ thus divides the order $n$ of the group. We are told that $a$ is a generator, which means the order of $a$ is $n$, and we can check this³.
We are now in the situation where we can apply the general Pohlig-Hellman algorithm as stated in Wikipedia, with their $\mathbb G$ of order $n$ our $\mathbb Z_p^*$ of order $n=p-1$, their $g$, $h$ and $e_i$ our $a$, $b$, and $n_i$ :

The first step in that algorithm is factoring $n$ into $n=\prod{p_i}^{n_i}$, that is $8100=2^2\cdot3^4\cdot5^2$. For each $i$ we'll form a subgroup of $\mathbb Z_p^*$ where we solve a sub-problem.
Each of this sub-problems is $\left(a^{n/({p_i}^{n_i})}\right)^{x_{p_i}}\equiv b^{n/({p_i}^{n_i})}\pmod p$ (per the linked example's notation, which uses $x_2$, $x_3$, $x_5$ where Wikipedia uses $x_1$, $x_2$, $x_3$). Each of this sub-problem is in the (cyclic) subgroup of $\mathbb Z_p^*$ generated by $a^{n/({p_i}^{n_i})}\bmod p$, of order ${p_i}^{n_i}$. We solve each separately using Pohlig-Hellman for group of prime-power order. Calculations involving elements of a subgroup are within the main group, thus in $\mathbb Z_p^*$, thus modulo $p$. Calculations involving exponents (in particular, the solution $x_{p_i}$ ) are modulo the subgroup order, that is ${p_i}^{n_i}$.
Then we join the solutions $x_{p_i}$ in a Chinese Remainder Theorem step, where the coprime moduli are the ${p_i}^{n_i}$, which product is our $n=p-1$.

In summary, all calculations involving a multiplication by $a$ or $b$ are modulo $p$, so as to be in the group $\mathbb Z_p^*$. Same for raising $a$ or $b$ (or a product of powers thereof) to some power. Only operations involving an exponent (that is the integer defining to which power we raise such combination of $a$ or/and $b$) is made modulo something other than $p$: the group order or a subgroup order, thus modulo $n$ where $n=p-1$, or modulo some divisor of $n$.

why are the 3 congruence equations we get for the 3 subgroups also not $\bmod p$. Why are they $\bmod 4$, $\bmod 81$ & $\bmod 25$?

Because they are congruence modulo the orders ${p_i}^{n_i}$ of the 3 subgroups of $\mathbb Z_p^*$ generated by the 3 elements $a^{n/({p_i}^{n_i})}\bmod p$. Relations (multiplicative) in these subgroups of $\mathbb Z_p^*$ would be modulo $p$.

While multiplication in the subgroup is being done modulo $p$, why are exponents in the subgroup expanded modulo $p_i$?

For any finite group $(\mathbb G,*)$ of order $r$ (that is, with $r$ elements), for any $x\in\mathbb G$, it holds⁴ $\underbrace{x*x\ldots x*x}_{r\text{ terms}}=x^r=1$, where $1$ is the neutral of the group.
Therefore, for any integers $s$ and $t$, $x^s*x^t=x^{s\cdot t\bmod r}$, where $s\cdot t\bmod r$ is computed over integers regardless of the group's nature and it's group law $*$. That's why exponents are computed modulo the group order.
When we consider a subgroup of $\mathbb Z_p^*$ (thus where computations are modulo $p$) that has order $p_i$ (as in this sub-question) or ${p_i}^{n_i}$ (as in the overall problem), that subgroup is a group of order $r=p_i$ or $r={p_i}^{n_i}$. When working in that subgroup, we can thus reduce exponents modulo $r$.
Notice that the order $r$ of a finite subgroup always divides the main group's order, here $n=p-1$.

solve it in subgroups ${p_1}^{n_1}$, ${p_2}^{n_2}$, ${p_3}^{n_3}$ etc

It's important to be precise here: we are solving an equation $a^x\equiv b\pmod p$ in a subgroup of order ${p_i}^{n_i}$ of the main group $\mathbb Z_p^*$. Therefore, equations related to exponents are stated (and solved) in the ring of integers modulo ${p_i}^{n_i}$ noted $\mathbb Z_{{p_i}^{n_i}}$ ; while equations related to exponents in the main group are in the ring of integers modulo $n=p-1$ noted $\mathbb Z_n$.

Picky note on notation:
For integer $m>0$, the notation $u\equiv v\pmod m$ is read as “$u$ (is) congruent to $v$ modulo $m$” or sometime “$u$ equal(s) $v$ ... modulo $m$”, as a shortcut for “(the representative of) $u$ equals (the representative of) $v$ in the ring of integers modulo $m$”. That notation means (equivalently):

that $m$ divides $u-v$
that $u-v$ is a multiple of $m$
that the remainder of the Euclidean division of $\left\lvert u-v\right\rvert$ by $m$ is $0$
that exists integer $w$ with $u=(w\cdot m)+v$

The notations $u=v\bmod m$ and $v\bmod m=u$, in which $\bmod$ is an operator combining two integers into an integer, are respectively read as “$u$ equal(s) ... $v$ modulo $m$” and “$v$ modulo $m$ equal(s) $u$”. Both mean (equivalently):

that $u\equiv v\pmod m$ as defined above, and $0\le u<m$
that $u$ is

the remainder in the Euclidean division of $v$ by $m$, when $v\ge0$
$m-1-((-u-1)\bmod m)$, otherwise

When hearing ”$u$ equals $v$ modulo $m$” (without a discernible pause), or seeing $u=v\mod m$ (with extra spacing on the left of $\bmod$ due to the use of \mod rather than \pmod or \bmod), there can be an ambiguity about if $0\le u<m$ is meant, and that maters in some crypto applications. When we write $c=m^e\bmod n$ in RSA, we positively assert $0\le c<n$. For consistency, we want to write $\forall k\in\mathbb N,\;2^k\equiv2^{k\bmod 42}\pmod{43}$, rather than $\forall k\in\mathbb N,\;2^k=2^{k\bmod 42}\bmod 43$, which has counterexample $k=6$.

¹ When solving for $a^x\equiv b\pmod m$ in the most general case of a composite $m$, the outer step could be to factor $m$ as $m=\prod{m_j}^{k_j}$ with $m_j$ prime; then solve each of the problems $a^{x_j}\equiv b\pmod{m_j^{k_j}}$; then join the solutions. Here there's a single $m_1$ (one special case), and $k_1=1$ (another special case).
² The converse is not true, see this.
³ The standard technique is ensuring $a^{n/p_i}\not\equiv1\pmod p$ for each prime $p_i$ dividing $n$. Here $n=p-1=8100=2^2\cdot3^4\cdot5^2$ thus $p_i\in\{2,3,5\}$, and neither of $6^{4050}\bmod8101$ , $6^{2700}\bmod8101$ , $6^{1620}\bmod8101$ is $1$, thus $a=6$ indeed is a generator.
⁴ Fermat's little theorem, in the form $a^{p-1}\equiv1\pmod p$ for prime $p$ and $a$ not divisible by $p$, is precisely a restriction of that statement with $(\mathbb G,*)$ the group $\mathbb Z_p^*$ with $p$ is prime.


Yao's Garbled Circuit with different outputs

Suppose you want Alice to learn $f_A(x,y)$ and Bob to learn $f_B(x,y)$. Then have Alice choose random string $r_A$ and have Bob choose random string $r_B$. The parties should perform a secure computation where both parties learn $(f_A(x,y) \oplus r_A, f_B(x,y) \oplus r_B)$. Basically each party's designated output is masked by a one-time pad that only that party knows.


Modifying a [CRC32] checksum protected file

One fundamental property of CRCs is that if you exclusive-or in the bit representation of the polynomial (which, for standard CRC-32, would be 0x0104C11DB7) anywhere in the message, you don't modify the CRC.

So, the obvious thing for you to try is to exclusive-or that value (and similar, for example, the bit-reversed version of above) and see if that modified version has the same CRC.

Once you have verified the CRC polynomial (and the order in which bits are processed), then it is fairly straight-forward to perform arbitrary changes.


Terminology: Is a block cipher in counter mode still considered a block cipher or is it classified as a stream cipher?

A block cipher is a block cipher. But if it is used within counter mode it becomes a block cipher within a streaming mode of operation. The resulting cipher has the external properties of a stream cipher. The block cipher now acts as a stream cipher. But I would not call it a stream cipher, because that would probably fool readers that the cipher has the internal design properties of a stream cipher.

In other words, streaming modes such as CTR simulate a stream cipher, but it doesn't emulate it. Externally it does show it to have certain properties, but it is does not try to be one internally. For instance, the key remains protected by the block cipher, rather than by properties of CTR which defines how to perform the streaming.

For these reasons I would prefer a sentence like "using CTR mode lets you use a block cipher as a stream cipher" rather than "using CTR mode turns the block cipher into a stream cipher". You could use the term "stream cipher" after such a clarification, I suppose, in case you don't want to get stuck with "block cipher in stream mode of operation" which may be too large / descriptive in texts.


First, there are several certificate-request schemes (and formats) in use. Are you sure this file is supposed to be a CSR in the specific format supported by req namely PKCS10/rfc2986 et pred?

Second, what is actually in the file? Is it actually in PEM format as described in wikipedia's second paragraph i.e. a five-dashes-BEGIN-something line, some base64, and a five-dashes-END-something line, and if so what exactly is the 'something'? Is it CERTIFICATE REQUEST or NEW CERTIFICATE REQUEST or something else? Is the PEM format exactly correct (no missing, altered, or extra characters within the lines of the PEM block -- extra lines before or after are okay)?

If the file is not PEM format, what is it? If it contains unprintable characters, use a hex dump or similar. If you don't recognize it, post it, or at least the first 50-100 bytes, for us to look at.


What exactly is the impact of the hidden subgroup problem on cryptography?

As far as I understand, the HSP is a hard problem such that:

some types of HSP (namely those operating in an abelian group) can (theoretically) be solved efficiently on a quantum computer (assuming one can be built);
many types of public key cryptosystems can be reduced to the HSP: if you can solve the HSP you can break the key.

In particular, integer factorization and discrete logarithm (in any abelian group, which includes elliptic curves) can be reduced to HSP over abelian groups, and thus easily breakable on a quantum computer. This is not really new: Shor's algorithm already does that. It just happens that Shor's algorithm is a special case of HSP.

The interesting part is that lattice reduction can be reduced to HSP over a non-abelian group, for which no efficient algorithm is known yet. So this formalism is actually giving reasons on why lattice-based algorithm may survive in the post-quantum world.

In your summary of HSP, one might add two details: "finding H" really means "finding a set of elements of G which generate H" (i.e. H is the smallest subgroup of G which contains all those elements); and: "given f" means "a black box implementing f is given, and can be invoked repeatedly on any inputs".


Is Mega.nz encryption vulnerable to brute force cracking by quantum computers?

Grover's algorithm on AES-128
If all of the problems of Grover's algorithm are solved then yes, otherwise no!

Grover's algorithm provides quadratic speed up so AES-128 has 64-bit security in the terms of searching complexity of Grover's method.

Grover's attack for AES-128 requires approximately $2^{64}$ successive AES evaluations. That is one has to set up the machine $2^{64}$ times, run successfully, and extract the result. This is not like a for loop on the classical machines.

The attack time is still quadratic and the required gates are not practical and it can be around $2^{86}$ for AES-128.

Graver algorithm can run in parallel, however, running $k$ machines will provide $\sqrt{k}$ speed up, and the above problem will still exist in each copy.

They are a company, if you are going to be their customer ask them to include the easiest mitigation AES-256 if you fear the future. The performance difference between AES-128 and AES-256 is just 40%, that is AES-256 is 40% slower. This is not a big deal in security. It is strange that they don't offer that since the industry sees the AES-256 as the gold standard.

A more realistic attack on AES-128
In MEGA file encryption, each node (file or folder) has its own encryption key. Although AES-128 is secure, with AES-128 the more users the MEGA has and the more file uploaded by the users will create an realistic attack on AES-128, the multi-target attack with parallel versions of Oechslin's rainbow tables.
Finding a key from $t$ targets's expected cost is $2^{128}/t$. Now assume that you have a billion targets. Then, you will be able to find the first encryption key much lower than 128-bit security. The cost would be below $2^{100}$ and the time would be below $2^{70}$. This can be achievable with supercomputers.
Therefore the MEGA must give the option to use AES-256 for their clients. In the end, the encryption is performed on the client-side, that is no cost for the MEGA servers at all.

A Review of Mega from their White Paper
Mega is simply

MEGA is a secure cloud storage and communication platform with user-controlled end-to-end encryption (E2EE). End-to-end encryption means that no intermediary - not even MEGA - has access to the user’s encryption keys and therefore the stored data. However, users have the option to share data (individual files or entire folders), plus the associated encryption keys, with others.

It enables browser-based access to end-to-end-encrypted
cloud storage.
End-to-end encryption
The files are encrypted on the client-side before uploading. If the user wants to share a file, then they share the encryption key of the file with the recipient’s public key. The recipient key can be verified in another channel as the Signal does, and any change will be notified.
Source code transparency
All security-related code work on the user side and Mega releases the source code so that third parties can verify the source code. This is a very important aspect
Privacy
They promise to only keep the user's e-mail and IP address for operational purposes. They promise to not keeping processing activities and the data, though they can see the activity. The files are still encrypted and not accessible to Mega.
Vulnerability management
They want to ensure security on an ongoing basis and they offer a prize for a previously unknown security-relevant bug or design flaw. This is an important aspect since it will attract more people to look at their designs and codes.
They also provide Data Redundancy and compliance with regulatory
requirements. The compliance is an interesting part since, at least now, Australia banned end-to-end encryption. Although the MEGA's service is governed by New Zealand law, it is unclear to me in the case of LAW change.


Simulation Based Proof: What Can / Can not Simulator Do?

There is quite a bit of confusion in your question. First, differentiate between the real and ideal models. The adversary in the ideal model sends the adversary's input and gets its output (and can also sometimes determine if the honest party gets output, depending on the model). We often call the ideal adversary a "simulator" since this is how we build the security proof. Thus, in the case of coin tossing where no party has input, the simulator begins by getting the output. This is allowed by definition.

Now, the simulator typically works by running the real-world adversary. Here it has power. For example, it can rewind the real-world adversary, can look at its random tape, and so on. (This gets complicated depending on the model. For example, in the common reference string model it's different. But let's leave this for now.)

Finally, in a HYBRID model, there are additional issues. In this model, the parties exchange messages but also have access to a trusted party. When simulating a protocol in this model, the simulator actually runs the trusted party for the adversary. Thus, in the ZK-hybrid model, the simulator gets the adversarial prover's input (which includes the witness). This is allowed by the composition theorem of the model being used.

None of this is straightforward, and it's very hard to learn by yourself. I suggest that you look at some videos online; they may help. For example, the Bar-Ilan Winter Schools from 2011 and 2015 cover secure computation and may help you get started.


Let $G=\{a+ib:a,b\in \mathbb{Z}\}$ be the Gaussian integers (something similar can be done with the Eisentstein integers defined via third complex roots of unity as well).
$G$ is the ring of integers of the complex field $\mathbb{C}$. With the inner product of $x,y \in \mathbb{C}^n$ defined via the hermitian inner product
$$
x\cdot \overline{y}=x_1 \overline{y_1}+\cdots+x_n\overline{y_n},
$$
the dual lattice of a lattice $\Lambda \subset \mathbb{C}^n$ is defined as
$$
\Lambda^{\ast}=\{x \in \mathbb{C}^n: x \cdot \overline{u} \in G~for~all~ u \in \Lambda\}.
$$
The lattice $\Lambda$ itself is of course the set of all vectors
$$
\xi M,
$$
where $\xi=(\xi_1,\ldots,\xi_n) \in G^n$ is arbitrary and $M$ is a complex $n\times m$ generating matrix for $\Lambda.$


How to determine the multiplicative inverse modulo 64 (or other power of two)?

A boring method is to carefully apply the (partially) extended Euclidean algorithm.

But in the question, the modulus is a power of two (specifically $2^6$), and we can use that
$$a\,x\equiv1\pmod{2^k}\implies a\,x\,(2-a\,x)\equiv1\pmod{2^{2k}}$$
from which it follows this fact:

  if the modular inverse of $a$ modulo $2^k$ is (the lower $k$ bits of) $x$, then
  the modular inverse of $a$ modulo $2^{2k}$ is (the lower $2k$ bits of) $x\,(2-a\,x)$
  (where negative integers are in 2's-complement convention, dominant in modern CPUs).

This not-so-much-known fact allows computation of multiplicative inverse modulo $2^k$. We start from an inverse $x$ of $a$ over few bits (that can be $x=a$, perhaps $\bmod 7$, which is the inverse for any odd $a$ over three bits), and iterate $x\gets x\,(2-a\,x)$, possibly truncated to the number of known-correct result bits. That number of bits doubles at each iteration, thus about $\log_2(k)$ steps are enough, and it is only used product, subtraction, and bit truncation on values no wider than $k$ bits. That is blindingly fast compared to the Euclidean algorithm's $O(k)$ steps; and eases getting data-independent execution time, which comes handy in some cryptographic computations (e.g. the preliminary computation of $m'$ in Montgomery multiplication, algorithm 14.36 of Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone's Handbook of Applied Cryptography).

I learned the technique from Colin Plumb's Computing multiplicative inverses (post on sci.crypt with Message-ID: <1994Apr6.093116.27805@mnemosyne.cs.du.edu>, 1994). His statement applies to inverse modulo a prime power, and points the relation to the Newton's iteration for finding $x = 1/a$ in $\Bbb R$.

A modern exposition, with benchmarks, is in Jean-Guillaume Dumas: On Newton-Raphson iteration for multiplicative inverses modulo prime powers.

A bibliography, and other techniques faster than the Euclidean algorithm, are in Çetin Kaya Koç: A New Algorithm for Inversion mod $p^k$.

Here, to perform the desired computation quickly, we use $k=3$, $a=47$, and compute $a\bmod2^k=47\bmod8=7$, which multiplicative inverse modulo $8$ is also $x=7$. Now we compute
$$\begin{align}
(x\,(2-a\,x))\bmod2^{2k}&=(7\,(2-47\times7))\bmod 64\\
&=15\end{align}$$

Hence the desired modular inverse of $47$ modulo $64$ is $15$.


How does a preimage attack on MD5 break the security of HMAC-MD5?

I fail to see how an hypothetical black box doing a (first) preimage attack on MD5 could be turned into an attack on HMAC-MD5, even if that box was able to effortlessly find the admissible combinations of prescribed unknown bits in an otherwise known message, given the hash; for example, if that box returned the (likely: very few, like less than 3) possible first 128 bits of message, given rest of message and hash.

And I'm at least convinced that a key-recovery attack on HMAC-MD5 requires more than a few preimage attacks on either MD5 or its round function.

Updated rationale: a successful attack on HMAC-MD5 can't be made by guessing a key $K$ of $k$ bits using a preimage attack on either of the two MD5 composing HMAC, taken in isolation.

The output of the outer MD5 (the one with opad) is known, but one not knowing $K$ is facing the situation where the first $k$ bits of the hashed message are unknown, as well as the 128 bits produced by the other MD5 (that involves the unknown $K$ thru at least two rounds, thus is essentially random). A preimage attack on the outer MD5 is thus expected to return about $2^k$ solutions (each yielding a combination of $K$ on $k$ bits, and the result of the inner hash on 128 bits). We have to weed out which is the right $K$, which requires about $2^{k-1}$ tests involving the inner MD5 and the $K$ tested, to check if that matches the last 128 bits of the preimage. We have hardly reduced the effort compared to a brute force attack. The alternate strategy of computing the full HMAC-MD5 for each $K$ suggested by the preimage black box is no better, under the reasonable assumption that these $K$ are random-like, thus have moderate overlap.
The output of the inner MD5 is not known, thus a defining hypothesis of a preimage attack is not met.

If we break HMAC-MD5 into individual rounds, we similarly conclude that a preimage attack on any round taken in isolation can't break HMAC, because the attack is no better than brute force, or/and because the round's output is unknown.

However, if a preimage attack on MD5 (or/and its round function) was possible, the security argument we have on HMAC-MD5 would vanish, and the prudent thing would be to act as if HMAC-MD5 was broken.


Why can we not use the group $Z_{p}^{*}$ for cryptography?

You can use the multiplicative group $\mathbb{Z}_p^*$, provided you use a key long enough to be secure.

Diffie-Hellman key exchange, DSA and the ElGamal cryptosystem were originally defined based on the hardness of the Discrete Logarithm Problem (DLP) over finite fields.

The challenge is that since then several methods have been found to reduce the complexity of the DLP (e.g. number field sieve, Pohlig-Hellman algorithm, Pollard's Rho algorithm). Consequently for these algorithms to be secure today it is necessary to use long (>3072 bits) prime fields. Additionally, since the scaling of hardness is sub-exponential in p, doubling the hardness of the problem requires that p is increased by much more than 2 (so secure key lengths will grow near-exponentially over time).

The advantage of using cryptography over elliptic curve groups is that you end up with smaller key lengths and ciphertexts for equivalent hardness (e.g. 256-bit ECC versus 3072 bit) and it scales better (so doubling the complexity means adding a single bit instead of adding many bits).


$\mathbb{Z}_n^*$ doesn't mean $\mathbb{Z}_n - \{0\}$. You must remove all elements that are not invertible mod $n$, which is equivalent to keeping only the elements that are coprimes to $n$.

So, $\mathbb{Z}_n^* = \{x \in \mathbb{Z}_n : \exists x^{-1} \in \mathbb{Z}_n \} = \{x \in \mathbb{Z}_n : gcd(x, n) = 1\}$.

This is necessary since all elements in a group must have inverse elements (regarding the group operation). In $\mathbb{Z}_n$, the group operation is $+$, so, any $x$ has $-x$ as inverse mod $n$. But in $\mathbb{Z}_n^*$, the operation is the multiplication, so, some elements might not have inverses mod $n$.

For instance, take $\mathbb{Z}_9$. The elements $0, 3, $ and $6$ are not invertible mod 9 (we can't multiply them by other element and reduce mod $9$ to obtain $1$). Therefore, $\mathbb{Z}_9^* = \{1, 2, 4, 5, 7\}$.


Why not just encrypt the message and the hash of the message to achieve cryptographic integrity?

I'll take this in parts:

  But this is clearly not the case when you're doing Encrypt Then Mac. When you do that you provide authentication to something that already has authentication (to decrypt we need to know the key).

Encryption, by itself, does not provide authentication.

  why use a MAC when we can use a hash instead: E(m|h(m))?

Here is a simple counter example to your proposal. Say I know that m="Transfer \$1000 to Mikeazo", and you use a stream cipher (or stream like mode) to encrypt that and the hash of the message. I know how to compute h(Transfer $9999 to Mikeazo). I also know what bits to flip in the encryption to get everything to check out okay.

Now, you may be thinking that this attack is only valid since I assumed a stream cipher and how about other modes (e.g., CBC). Well, here are the details on an attack with CBC.

When we design cryptographic primitives, we want them to be as secure as possible, and even provably secure (given a reasonable set of assumptions) if possible. That is why we do things like Encrypt-then-MAC as opposed to your proposal. Encrypt-then-MAC is provably secure.


ElGamal with elliptic curves for security

But, if i want to proof the CPA security for ECC-ElGamal, then, what hard problem should i based? DLP?

It's fairly easy to show that it is equivalent to the DDH problem.
Reducing CPA security to DDH:
Given a public key $aG$, and the possible encryption of a plaintext $P$, which is $X, Y$; if it is in fact ECC-ElGamal, then $X = bG, Y = abG + P$ for some random $b$.
Then we check whether $aG, X, Y-P$ is an DDH-triplet; it's easy to see that if we were given an ECC-ElGamal ciphertext, then it is.
Reducing DDH to CPA security:
Given a potential DDH-triplet $X, Y, Z$ (which is $aG, bG, abG$ if it is a triplet), then we select an arbitrary plaintext $P$, and pass to our CPA-oracle the public key $X$, and the ciphertext $Y, Z+P$; if it says that this is an El Gamal encryption, then we say that it is a DDH-triplet.


No, because then you could calculate $z_1 \oplus z_2 = (m_1 \land m_2) \oplus (m_1 \lor m_2) = m_1 \oplus m_2$.

In practice, you can only find $m_1 \oplus m_2$ if both $m_1$ and $m_2$ are encrypted with the same OTP (i.e., $(m_1 \oplus y_1) \oplus (m_2 \oplus y_1) = m_1 \oplus m_2$).

So without any knowledge of $m_1$, $m_2$, $y_1$ or $y_2$, there is no way of magically eliminating both of the OTP key streams $y_1$ and $y_2$.


RSA - Does knowledge of part of the ciphertext decrease encryption security for the rest of the ciphertext?

No known, modern cipher should be vulnerable against known plaintext attacks. Now just RSA 2048 is not likely to be used on all the text, and RSA encryption can be implemented in different ways, but it is unlikely to the extreme that the protocol is vulnerable against known plaintext attacks. It may of course well be vulnerable against other attacks, such as padding oracle attacks on PKCS#1 v1.5 padding, if that is used.

So you can create a string as large as you want and still be secure against known plaintext attacks, no matter how much of it is guessed or gets known otherwise.

Hah, and I looked up the standard after I wrote this answer and got this in return. It doesn't contain known plaintext attacks of course, that would be too easy. But it does use PKCS#1 v1.5 - which may be vulnerable and AES-CBC without authentication which is even more likely to be vulnerable (ugh).

The paper by the way has been "withdrawn for non scientific reasons" - probably to hide it under the carpet, but you can still download it if you know how to retrieve old internet content (deliberately not linked). Here is the security advisory that links to the missing paper.


Can homomorphic encryption achieve program integrity (verification) in the cloud?

Can I use homomorphic encryption to keep cloud computation confidential and also guarantee the integrity of computation?

You're looking for verifiable computing:

  Verifiable computing (or verified computation or verified computing) is enabling a computer to offload the computation of some function, to other perhaps untrusted clients, while maintaining verifiable results. The other clients evaluate the function and return the result with a proof that the computation of the function was carried out correctly.


Brute force attack on DES + property of DES

You are right that a brute force attack on DES requires a single plaintext/ciphertext pair; another plaintext/ciphertext pair is useful to confirm the result once found (and rule out a false positive).

No, $DES_{k_1}(x) = DES_{k_2}(x)$ does not imply $k_1=k_2$; the same holds with high probability for any ideal cipher with the same parameters as DES, modeled as a key-dependent family of random permutation (explicitly finding a counterexample requires significant work, but still much less work than a brute-force key search: that's essentially a collision search, memory or/and cycle-finding can help; in fact that is an interesting hands-on computer project).

DES key search with a single plaintext/ciphertext using a black-box DES implementation requires $2^{56}$ invocations at worse (we discount the "optimization" of concluding after $2^{56}-1$ keys did not match that the single remaining one must be right, which is unrealistic, and saves only $2^{-56}$ of the effort with odds $2^{-56}$). That is "in time $2^{56}$" (the default assumption is a sequential attacker). There will be $2^{55}$ invocations on average (the expected time/effort). Chance/risk (depending on point of view by attacker/user) that the key is found after only $2^t$ tests is $2^{t-56}$ for $t\le56$ using sequential key search, or $t\ll56$ using random key search.

Notice that if one has two pairs $(x,E_k(x))$ and $(\overline x,E_k(\overline x))$, the DES complementation property gives $E_k(\overline x)=\overline{E_\overline k(x)}$ and allows to half the work, for we can test $k$ and $\overline k$ in a single operation. Also notice that in a computer program (rather than a black box) we can change the keys in a manner such that a little of the work with earlier keys is reusable, saving some time; and more generally test $t$ keys with appreciably less work than what's required for $t$ encryptions with arbitrary different keys.

The DESCHALL project and EFF DES Cracker have been historical demonstrations that the DES key space of $2^{56}$ was too small even for civilian application in 1998.


WinZip allows enumeration of the file names contained within.  Try WinRAR or 7zip instead. WinZip AES-256 also uses CTR mode.

Both PGP and AES-256 in CTR mode are both currently considered "strong."

Can you provide more details about what exactly you're looking to do, or in what context you are evaluating safety and security?


Can I use a government-issued certificate in Outlook?

If your email is indeed in the cert and the key usage is there, you would expect that you can sign with it, providing that:

the certificate is compatible with the email client;
the signing generation is compatible with the email client;
that you have the entire certificate chain present (otherwise the receiver may miss an intermediate certificate).

And of course the receiver must have a compatible mail client as well and trust the (root) certificate of that government in his own certificate store.

If the Outlook mail client - or any other mail client - is compatible depends on the details. They can often be made compatible by including specific plugins.

Note that Outlook, like many other Microsoft products, depends on the PKI capabilities of the host operating system, i.e. Windows.


What does MULx operation in SNOW 3G correspond to?

It essentially is the value $02 \times V$ in the field $GF(2^8)$, and so MulxPOW(V, I, c) is essentially $02^i \times V$ in the field $GF(2^8)$, where $c$ specifies the representation used.

What is a representation: there are a lot of ways to map between 8 bit values and the members of the abstract $GF(2^8)$ field, and a number of those mappings are plausible (unless $GF(p)$, which has an obvious mapping between integers in the range $[0, p-1]$ and members of that field - so obvious that we typically ignore it).

What Snow does is use several different mappings (representations) for the various SBoxes, by specifying different $c$ values for the different sboxes.


AES-CBC ciphertext manipulation with known IV and plaintext!

This question is educationally illustrative and deserves a good answer.

Because in CBC, $C_i = E_k(C_{i-1} \oplus P_i)$, and $C_0 = IV$, you can alter any bit in the first block by changing $IV$ without affecting later blocks and won't get caught because there isn't a MAC tag.

Take a look at this graph:

0123456789abcdef // numbering
{"admin": 0, "us // json token
ivivivivivIviviv // init vec
~~~~~~~~~~^~~~~~ // change

This shows once again why message authentication is important, and symmetric-key encryption should follow AEAD paradigm.


DES: histogram differences between plaintext and ciphertext

Lookup avalanche effect either in wiki or our tags here. Essentially, the slightest change (any single bit) of the plain text leads to 50% of all the other bits (on average) changing across the full width of DES' 64 bit block size.  This totally obfuscates any correlation between the plain text characters.

"Caesar" cipher doesn't exhibit avalanche being only a substitution. It simply keeps the correlations and encodes them to other letters.


Benefit of using random key in Shamir's Secret Sharing

There are no security advantages to evaluating the polynomial at random places instead of sequential. The information theoretic security proof of Shamir secret sharing does not depend on the evaluation points being chosen in any specific manner.


There's always the old Polig-Hellman system, with:

$$C = M^k \bmod p$$

where $M$ is the message, $C$ is the ciphertext, $k$ is a (secret) key (any integer relatively prime to $p-1$), and $p$ is a large public prime.

Decryption can be done as:

$$M = C^{k^{-1} \bmod p-1} \bmod p$$

To address your requirement, given $k_{A_1}, k_{A_2}$, you can select a random $k_{B_1}$ (relatively prime to $p-1$), and then compute $k_{B_2} = k_{A_1} k_{B_1} k_{A_2}^{-1} \bmod p-1$, and Bob's your uncle.


Spelunking through https://crt.sh, one finds a CA certificate for RSA Data Security, Inc., from 1994, but the oldest certificate it has issued has a validity period starting only on 1998-02-13.  That doesn't mean that that CA didn't issue certificates before—maybe the records in crt.sh are incomplete.  Indeed, pursuing the PostgresQL interface doesn't reveal any non-CA certificates until 1997, for www2.superb.net, which strongly suggests the records are simply incomplete.

To do further research, with a bit more effort, you might query the EFF's SSL Observatory database.  Netcraft also alleges to have data about historical certificate trends, in exchange for money, but it's not clear that they have the actual certificates or just some summarized properties like what serial number and what type of key.


What mathematics do I need to study in order to understand fully homomorphic encryption?

Knowing more about your background, you will definitely want to brush up on some abstract algebra. The book I link to below is pretty popular and introductory. I think it's just at your level. Also, understanding concepts like groups, rings (see below), homomorphisms, and fields are useful in understanding modern crypto. You won't be wasting your time at all.

Probably the most important skill is that vague term known as mathematical maturity, part of which includes

  fearlessness in the face of symbols

Along with this is understanding how to read a mathematical proof.

You should know about provable security as well, in particular how a problem can be reduced to another, such as how the security of the lattice shortest vector problem (SVP) can be reduced to the security of RLWE.

You should be familiar with big-$O$ notation.

You should be familiar with probability distributions, in particular the uniform and Gaussian distributions, and what it means to sample from a distribution.

As mentioned in the comments, you need to learn some abstract algebra. Back in the day, I learned enough to start from Pinter's A Book of Abstract Algebra. It has some very gentle prerequisites. You'll definitely need to learn about rings and quotient rings (RLWE means "ring learning with errors").

You'll need some linear algebra (especially norms and inner products) and lattices.

You'll need some algebraic number theory (see section 5.1.1).

Now, this is a lot, and I don't know if you just want to "get the gist" of the paper or hopefully start contributing original research. But again, "mathematical maturity", or trying to cultivate it, is the most important thing regardless!


How to efficiently generate a random safe prime of given length?

There is no more efficient way of generating a safe prime. Even in OpenSSL's optimized code, it can take a long time to generate a safe prime (30 seconds, a minute, 2 minutes). Run "openssl gendh 1024" on your computer to see (on my 2015 MacBook pro it can take a long time, but the variance is really high so try a few times).

The comments talk about safe primes for RSA. Indeed, safe primes are not needed for RSA. However, they are needed for generating parameters for finite-field cryptography (Diffie-Hellman over a finite field), and for other applications in cryptography. For example, zero-knowledge range proofs use a group with an unknown order, and this is defined by an RSA modulus and Pedersen commitments over that modulus. When using safe primes, this ensures that the group is large and furthermore that a random group element is a generator with overwhelming probability. See Section 1.2 of Efficient Protocols for Set Membership and Range Proofs for more about this particular application.

So, in more advanced cryptography, there are plenty of applications for safe primes (indeed, RSA encryption is not one of them).


RSA: how does it work and how is it more secure than symmetric systems

With regards to the public vs private keys, in RSA, the public key is used to encrypt information, the private key is used to decrypt it. Given only the public key, all you can do is encrypt. So, you can publish that online somewhere (key distribution is a very different problem). Anyone can use it to encrypt a message to you and only you can decrypt it.

Think of it this way. You give your friend a padlock and a wooden box. The padlock is unlocked. Your friend can put anything they want in the wooden box, put the padlock on, and lock the padlock. Now, only you, who knows the combination, can get at whatever was place in the box. In this example, the padlock is the public key, the combination is the private key. Having possession of the padlock (the public key) should not easily reveal the combination (the private key).


Anything known about this variation of Diffie-Hellman key exchange protocol?

... instead of addition of random errors I'm proposing deterministic erasure of the lower part of the data.

Truncation instead of addition of noise is an optimization that some LWE schemes use already.

  ... I'm wondering if anything is known about the security of this protocol? Has anything been published about this sort of technique, or is there some obvious attack that breaks it?

The more pertinent difference in your proposal is that it uses a one dimensional vector. There does exist a dimension/modulus size tradeoff for the LWE problem. But the problem is very sensitive to the concrete parameters that you instantiate it with.

An obvious algebraic attack might not be able to solve the problem, but you might be surprised at what the LLL algorithm can do. Understanding how to use LLL to actually do so is challenging. There are lots of papers about it.


Analysis of Repeatedly Enciphered Plaintext using Same Algorithm / Key?

Eventually, it will cycle, but it'll almost certainly take far longer than your lifetime to do so.

If that sounds too flip, here's the mathematics.  Assuming AES is secure, then the probability it will revisit the original plaintext after at most r repeated encryptions is just r/2128.  (This follows from a standard fact about the cycle structure of a random permutation.)  For the values of r that can realistically arise in practice, this probability is negligible: less than the chances of getting hit by lightning, twice.

Is there some known number r such that r repeated encryptions are guaranteed to bring you back to the plaintext you started with?  Yes, for instance: r = (2128)!, i.e., 2128 factorial.  Or, r =  lcm(1, 2, 3, ..., 2128) also works.   However, this is a stupendously, ridiculously large number.  So it's completely irrelevant in practice.

Bottom line. If you've got a secure block cipher, you don't need to worry about cycling.  It's not an issue.  It just ain't gonna happen.


For hardware encryptions, is it possible to know the key by analysing the hardware?

That really depends on the device. Usually there is a full, layered, key management scheme. That may involve a key in ROM, but that's then just use to load the next keys for the higher layer in persistent memory (flash or EEPROM mostly). In the end session keys are generated in transient memory (RAM).

It's very likely that if you find a key in ROM that that key is only used to load the initial software. The keys to actually encrypt the (credit card) data are likely to be in EEPROM somewhere, possibly encrypted with a static key in the software.

"Hardware encryption" usually means that the encryption algorithms themselves are in the chip. That makes them less vulnerable to side channel and fault injection attacks. It will usually also give a large performance enhancement; 8 and 16 bit CPU's are not too efficient with block ciphers like AES.

Sometimes a key store is however implemented using hardware. The key that protects the data in that key store may be in ROM.


What does the '.' dot symbol mean in the ChosenPlaintext($\cdot$) part?

It means that you, the adversary, may call this function with any value replaced for $\cdot$. This is useful if you want to give the adversary access to a partially applied function, e.g. $E(K,\cdot)$ the pre-keyed encryption function so that the adversary gets to see encrytions without learning the key.

  I hope someone can walk through what this is doing step by step in English.

You should really ask the person having presented / created this or their support staff for confirmation, but I think the idea of the slide is to give you some intution of common operations that an adversary might do and not lay out any specific concrete adversary.

If a=b goto ..., an adversary may commonly check / compare the content of two self-computed variables, e.g. when attacking a stream cipher which suffers from IV-reuse $a$ may be the keystream from one chosen plaintext-ciphertext pair and $b$ the keystream from the challenge ciphertext XORed with $m_0$. The goto is just there to show that adversaries can skip execution steps / break out of loops if some condition holds.
Else m=a, a default action to be taken when a previous if did not hold, e.g. to preserve loop-invariants.
c=ChosenPlaintext(m), the adversary may ask for encryptions of arbitrary data before and after submitting the challenge messages. This could e.g. be useful when the encryption function is stateful if you want to force a specific state for the challenge query.
d=c XOR b, the adversary may want to make computations on query results and / or other variables.
If 1=1 then m0=a, m1=b the adversary may select their challenge messages conditionally based on previous computations.
c=ChallengeCiphertext(m0,m1) the adversary can submit (once) a pair of messages to get the challenge ciphertext.
d=ChosenPlaintext(m0) submitting challenge messages to the encryption oracle is a totally fine thing for the adversary to do and may actually break deterministic schemes.
Return 1 and halt, the adversary can just return a fixed value, or some variable content or some expression and decide to stop execution.


What are the exceptions to Kerckhoffs's principle?

Kerckhoffs's principle: A cryptosystem should be secure even if everything about the system, except the key, is public knowledge.

The principle does not state that it is unconditionally unacceptable to keep your algorithm or system a secret. (This answer provides an image of the original text Kerckhoffs used.)

Just keeping the used algorithm a secret is not itself a violation of the principle - as long as it would be secure even if the algorithm was known. AES would be secure even if it is known that you used it, keeping the fact that you used AES a secret does not hurt anything. In fact, it is possible that it could provide an additional layer of security, and can be used to provide "defense in depth".

NSA suite A/suite B is a good example of this: It is not an exception to Kerckhoffs princpiple, because the system would (most likely) be secure even if you knew what algorithms they were using. It simply adds a theoretical additional layer of difficulty if you don't know what they are using.

As for banks, I am not necessarily qualified to speak about their systems, as I do not know them; However, it is plausible that some of them were created quite a while ago, and consequently may not necessarily utilize all the best practices that we would build a new system with today. "It's in production already" can be hard to argue with.

As for Microsoft, well, you say they "get away with it" - many if not most people are not exactly thrilled about their decisions to keep everything a secret; However, they do that for way more then just the crypto API, and such decisions are probably made from a business perspective, rather then a crypto one.

edit: Apparently, if you are really so inclined and willing to sign stuff, you can view some of Microsofts source code. While that's not exactly "open", it implies that you could find out what they were doing if you really wanted to.

However...

Sometimes violation of the principle is simply an attempt to compensate for the inadequacy of the algorithm/system by keeping it a secret from the adversary - this is the situation where the principle will end up making a difference.

This has proven itself to be a poor strategy - instead of allowing the problems to become known so that they can be fixed, they chose to cover them up and hope that nobody finds them. When "hope" appears as an factor in your crypto-system, that's a sure sign of a problem.