Is there an outdated or insecure hash algorithm thats output can be easily reversed back into the input?

Depending on what you want to do, maybe you can take a cryptographic hash function and truncate it. Adjust the length of the truncation to how much effort you want the preimage calculation to be. This is a valid way to create a proof-of-work mechanism. For example, if you want to require a party to perform about $2^{m+n}$ operations where $2^m$ is the estimated cost of hashing a very short string, then:

Generate a random $s+n$-bit string and calculate its hash $h$.
Send the hash $h$ and the first $s$ bits of the string and request a preimage.
Read back a string and check that its hash is $h$.

(The salt length $s$ needs to be sufficiently long to prevent pre-computing possible inputs.)

With any cryptographic hash function in good standing, and even with most of the ones in bad standing such as MD5, the fastest way to find a preimage is brute force searching among all $n$-bit strings.

If proof-of-work is not what you're after, then maybe you can use a non-cryptographic hash, for example a CRC. In general, hash functions that aren't specifically designed to be cryptographic hashes have a low probability of accidental collision (but it's easy to craft a collision deliberately), and they're easy to invert.

Of course, “inverting” the hash will find a preimage, not necessarily the string you started with.


If you knew $pq$ and $p+q$, you could find $p$ and $q$ by algebra. If you knew $pq$ and $(p-1)(q-1)$, you could find $p+q$. Now $e_1d_1-1$ and $e_2d_2-1$ are both said to be multiples of $\phi(n)$, so their greatest common divisor should be a (smaller) multiple of $\phi(n)$, from which you could easily guess $\phi(n)$.

I've probably said too much already, given that this is a homework assignment.


estimating entropy/randomness as fail-safe mechanism

Such practices are commonly applied to results of some random number generators, but less often to other applications.

There is one very common such fail-safe test

NIST's FIPS 140-2 requires very simple contiguous test for random number generation: store previous generated block and compare. Only if the block is different it is assumed that the RNG did not fail.

From FIPS 140-2 4.9.2:

  Continuous random number generator test. If a cryptographic module employs Approved or non- Approved RNGs in an Approved mode of operation, the module shall perform the following continuous random number generator test on each RNG that tests for failure to a constant value.

More entropy tests

The standard (FIPS 140-2) used to require more tests (mono bit test, poker test, runs test, long runs test). These tests give fairly good estimate of if input appears random. These were decommissioned, because they work better with NDRBG than RNGs required by the standard (see FIPS 140-2 Annex C if you need details), and because for some cases it is excessive requirement to produce 20000 bits for analysis (it may be that you just needed one 128-bit key). AIS31 standard used to evaluate true random number generators uses some very similar tests.

Used in practice

These tests are useful against some hardware random bit generators and for this reason, Linux rngd program is running the tests (previously part of FIPS 140-2) to ensure quality of entropy gotten (for example from /dev/hwrng) and to ignore inputs which appear non-random.

You may use Linux rngtest program to apply these tests to data of your choice, for instance, examine output of (possibly) buggy encryption software.


It seems to be asked textbook RSA with plaintext and ciphertext in the set $\{1,2,\dots,25,26\}$. That's wholy unreasonable, for in RSA the public key gives the mapping of plaintext to ciphertext, and with such small set it is trivially inverted. Let's see how it can be done nevertheless.

Textbook RSA operates on the set $\{0,1,\dots,N-1\}$ with $N$ the product of distinct primes. In order to use the desired set, I propose to use $N=26=2\times13$, and assimilate $0$ with $26$. We can now use textbook RSA, where encryption goes $C=P^e\bmod N$ ($P$ is the plaintext, $C$ is the ciphertext that the question calls $E$, and $e$ is the public exponent).

$\lambda(N)=\operatorname{lcm}(1,12)=12$, the public key $e$ must be coprime to that, and $e\times d$ must be one above a multiple of $\lambda(N)$, therefore we must have $e$ one of $1$, $5$, $7$ or $11$, with $d=e$ (within some multiple of $12$). $d=e$ means encryption and decryption are the same operation. Beside, ciphertext and plaintext are identical for $e=1$.

For example, with $e=5$, the plaintext $P=2$ is enciphered into $C=P^e\bmod N$, that is $C=2^5\bmod26$, that is $C=6$. And $C=6$ is deciphered into $P=C^d\bmod N$, that is $P=6^5\bmod26$, that is $P=2$.

We end up with a dumb mono-alphabetic substitution cipher with only four possible keys, one of which leaving plaintext unchanged, all with three fixed points $1$, $25$, $26$, and such that encryption and decryption are the same.


Comparing two encrypted numbers using El Gamal without using decryption

I believe you're having trouble with achieving your goal, because it actually goes against the security property of ElGamal:

I don't know how deep your cryptography background is, but the security of ElGamal is IND-CPA. It basically states, the attacker chooses two messages, gets back the encryption of one of the message, and he has to choose which message it was and retrns 0 or 1. If IND-CPA holds, then there is no stragety better than guessing that one bit(with negligible difference).

If you have an operation for comparison without decryption, then the above security game is easy: The attacker can encrypt both messages. And he could also encrypt an intermediate value and use the comparison to immediately find out which one it was.

About your general idea, using the multiplicative homomorphic property:

Kep in mind, that you are operating modulo some number. Formally, it's a finite field. But there is no comparison of elements in finite fields. The only way to achieve that, would be to limit the size of the numbers somehow, that you never trigger the modulo operation. That means, you have to keep the products below the modulus, otherwise the simple formula $a < b \Leftrightarrow ar < br$  is not valid any more. At least in general, without some additional constraints, e.g. that $a$ and $b$ are close together.
But then, anyone who sees $ar$ and $br$ can also compute $gcd(ar,br)$. That is divisible by $r$, and if $a,b$ are coprime, it is exactly $r$. It's easy to get $a$ and $b$ then.

So for the purpose of security, this step is exactly the same as giving $a$ and $b$ directly for comparison.

To your acutal question:

There are a few things, which you could use. But they are constructs of scientific papers, not something that you can find fully implemented in libraries:

Order preserving encryption, e.g. see this question or Order-Preserving Symmetric Encryption, Boldyreva et al., 2009
searchable encryption, see this question or our tag for it, or Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions,  Curtmola et al., 2006

Order-preserving encryption preserves elements order, so the comparison of the plaintext is just comparing the ciphertexts. However, this comes at a cost: The ciphertexts are usually quite a bit larger than the plaintexts. Searchable encryption is a powerful construction, which could be adapted for your comparison case.

But with ElGamal, you're not going to be able to achieve that without decryption and comparing the plaintext.


This problem is equivalent to the discrete logarithm problem, right?

As written, the problem is informationally secure; that is, you haven't given enough information for anyone (even a computationally unbounded adversary) to solve it.
Here is a simplified version of the same problem: I am thinking of two numbers; one of them is 42; is that the first number I'm thinking of, or the second?
I suspect that you're giving the adversary more information (and whether the problem is reducible to DL would depend on what that more information is)

Update (now that you have revised the question): it's fairly obvious that your problem is no harder than DL (that is, with a DL oracle, it is straight-forward to solve your problem).
Going back the other way, it would appear to depend on what the hash function $H$ is.  For example, if $H(x)$ is defined to be the lowest bit of $x$, that is, $x \land 1$ (which is stretching the definition of hash function a bit), then an Oracle that solved your problem with that specific $H$ could be used, given $g^z$, to recover the lsbit of $z$ (by passing the public keys $(g^1, g^z)$, $(g^0, g^z)$, and $dpk = g^1$); given an Oracle recovering the lsbit, it's straight-forward to read off the bits of $z$ sequentially.
On the other hand, if $H$ is constrained to be a real hash function (say, SHA-3), it's far less clear how such an Oracle could be used.  One issue is that, when you submit a query to the Oracle, $dpk$ is constrained to correspond to one answer or the other; given that you have no knowledge of $z$, you can't compute a reasonable guess of $H(z)$ (or $H$ of any nontrivial linear function of $z$), and there is no other obvious way to proceed.
Now, given that the protocol is secure (assuming DLogs is hard) for the silly $H(x) = x \land 1$, it sounds plausible that it's also secure for $H(x) = \text{SHA3}(x)$; however it wouldn't appear we know how to prove that.


Is it possible to build a compact proof of the sum of all even numbers of a dataset?

Let's ignore the zk requirement. And focus on compactness. If we have a merkel tree and I swap just one element at random so one of the hashes is invalid and doesn't match the data. We get a merkel tree with almost all valid hashes. Someone would have to verify all of them to catch the foegery. If you only sampled a few paths you would gain little confidence.
Any extra calculations you require on the tree could be done onhe forged version. I'm afraid your request is impossible.


CBC mode decryption for the first block is defined as:

$$P_0 = IV \oplus D_k( C_0 )$$

where $P_0$ is the first plaintext block, $C_0$ is the first ciphertext block, and $D_k$ is the decryption by the block cipher using the key $k$.

This can be rearranged as:

$$IV = P_0 \oplus D_k( C_0 )$$

which allows you to reconstruct the IV, if you know the key, the plaintext and the ciphertext.


Recover key given partial key, IV and cipher text using CBC mode

A known IV doesn't help: it's meant to be public.

Even if you know a part of the key then there's still no attack that's easier than trying all possible keys. Knowing a part of the key merely makes the set of possible keys smaller.

Knowing even a large amount of plaintext and ciphertext doesn't help to recover the key. As long as you haven't fully found the key, having access to plaintext-ciphertext pairs doesn't help recover the key more quickly. And knowing part of the key does not help to generate new valid plaintext/ciphertext pairs.

So leaking a small part of the key does not weaken the system. The problem with leaking a small part of the key is that when this happens, it's usually difficult to ensure that only a small enough part of the key is leaked, where small enough means “so that my adversaries can't brute-force the key”.

Note that, as Luis Casillas points out, here I'm assuming that the underlying block cipher is an ideal cipher, which is a good enough assumption for block ciphers that are used in practice. (Not in theory though — related key attacks do exist on AES, for example, but they're theoretical: they still require an unfeasible amount of computation). See Luis Casillas's answer for a more correct explanation.


Why not use an algorithm's code rather than data itself for one time pads?

Generating a pseudo-random stream from a key, and XORing that stream with the data to encrypt, is done on a regular basis. That's how most stream ciphers work, e.g. the well-known RC4, and also applies to block ciphers in counter mode. This is not "One-Time Pad", by definition, since OTP requires the key stream to be truly random (that's the condition from which the OTP unbreakability comes). Such stream ciphers still share with OTP the absolute necessity of never reusing a given keystream for two distinct messages, so the encapsulating protocol must take care to renew keys when needed. In SSL/TLS, a new session key is generated for each connection, so when a stream cipher is used (RC4), things are safe.

There are quite a few stream ciphers which have been seriously looked at by cryptographers, who found nothing bad to say about them; see the eSTREAM portfolio for a selection of those.

Chaos, fractals and so on, are not the right tool for cryptography. A chaotic system is just a producer of values which "jump around" in a seemingly random fashion. Statistical analysis tools could be defeated by a chaotic system. But statistical analysis tools are dumb: they are designed to analyze physical phenomena. For cryptography, we want to defeat an intelligent attacker who has a copy of the same software than the one you use, save for the keys themselves. For instance, a Linear Feedback Shift Register has very good statistical properties and produces bits which statistical tools will declare "plausibly random". But for a $n$-bit LFSR, it suffices to observe the first $n$ bits of output to learn the complete internal state, and predict all subsequent output with 100% accuracy (even if the LFSR structure -- the corresponding polynomial -- is unknown, $2n$ output bits are sufficient for that, with Berlekamp-Massey algorithm).

In short words, if you use fractals or a chaotic system in a homemade loop, you will make a cryptosystem apt to defeat a chimpanzee. We cryptographers usually aim a bit higher than that.

Also, secrecy of "the code" (i.e. software) is usually not assumed, because it is very hard to achieve. Software exists in some permanent storage, on a computer hard disk; there's source code somewhere; it is bulky. Keeping code confidential is hard, and even harder is knowing how much confidential it is. This is why cryptographers talk about keys: they split the "code" (e.g. a pseudo-random stream generator) into an algorithm, which is public and becomes software, and a key, which is a small sized parameter which concentrates confidentiality. A typical key is a sequence of, say, 128 bits, small enough to be handled and protected properly (it can even be remembered by a human, and typed back when it is needed -- thus, no need for storage on a hard disk).


Given a sha-512 hash of a value picked at random from the $2^{128}$ key space, how hard would it be to recover the original value?

The answer, as SEJPM pointed out, is "no, a work effort one the order of $2^{128}$ SHA-512 computations would be infeasible, even by a three letter agency".

However, the other question was "would constructing a rainbow table be the most efficient attack?"  The answer is "it depends".

If the attacker was interested in just one SHA-512 hash, and had no expectation of ever needing to attack another hash (or, at least, one with the same salt; for example, known bits that are also included along with the 128 unknown ones), then constructing a rainbow table is wasted effort.  The takes a constant factor more work than simple brute force (just trying all possible 128 bit values, and hashing them), and has a probability of failure (if none of the chains happens to hit the target value, the rainbow table lookup will fail).

On the other hand, if the attacker expected to have a series of SHA-512 hashes, all of the 128 bit keys (and all the other parts of the hash the same known values), then constructing a rainbow table makes a lot of sense; yes, constructing it takes a long time (infeasibly long in this case), however once you've done it, looking things up in it doesn't take that long at all.


What is a simple information authentication protocol for constrained devices?

Your initial idea is good. What is needed here is a challenge response protocol but rather than key agreement we need to authenticate a piece of data.

device issues challenge:(device id , nonce)
server signs and replies with MAC and data:(data,mac(device_key,nonce||data))
device verifies mac

As long as nonces don't repeat the data must be re-MACed by a party knowing the devices secret key and the device can be sure it has fresh, valid, data.

all that's left is picking a MAC function. You want a low cost keyed MAC. SHA256 and other well known hash functions are expensive because they need to resist collisions when the adversary can see their internal state and using them for MACing a message is wasteful. Less expensive MAC functions exist.

Here are a few mac algorithms that would work well:

CBC-MAC_AES (use this if you have AES hardware)
CBC-MAC_SPECK64/128 (designed by NSA (do you trust them?), likely <200 bytes code size on 8bit platform but similar on 32bit platforms)
Siphash (on Atmel AVR requires 1500 bytes code 42 bytes memory)

note on CBC_MAC: The wikipedia page mentions an IV which prevents replay attacks. IVs must be both unique and secret. If you have a secret IV used elsewhere, it can be reused with some caveats. The IV can also be generated from a nonce by encrypting the nonce. In your application though you can just prepend the nonce to the data before MACing.


PKCS#7 Signed Data contains always different signature

That's likely because the data used for the signature generation actually changes between the signing. That would e.g. be the case if that data contains the signing time. Note that within CMS the data is not directly signed; it is first hashed, put in a structure and then that's what is getting signed.
Also note that inclusion of the local time generated by the system is not the same thing as using a time stamping service.


What kind of encryption function is also used for decryption?

poncho and SEJPM more or less answered your question in the comments: If $f(f(m)) = m$, then the function can be revered to as a "self-inverse", or more formally, the function is said to be an "involution".

Be careful with a cipher that is an involution: There is a notable difference between a cipher that is a full involution and one that is not: Namely, if the cipher is an involution, then access to an encryption oracle is equivalent to access to a decryption oracle.

A stream cipher with exclusive-or as the key stream combining function is a notable example of an involution:

$c := E(m) = keystream \oplus m\\m := D(c) = E(c) = keystream \oplus c = keystream \oplus keystream \oplus m$


Can one reduce the size of ECDSA-like signatures?

ECDSA is actually a kind-of computational zero-knowledge protocol, played by the signer, with a "reduction function" as impartial verifier. For that matter, ECDSA is not very different from plain DSA.

Things basically go this way. There is a known public group $\mathbb{G}$ which I will denote additively, with $G$ as generator, and of size $q$ (a known prime integer). For DSA, $\mathbb{G}$ is the group of integers or order $q$ modulo a prime $p$ ($p$ is a bigger prime, such that $p-1$ is a multiple of $q$) with the multiplication as group law; for ECDSA, $\mathbb{G}$ is an elliptic curve (or a subgroup of an elliptic curve).

The signer knows a secret value $x$, an integer modulo $q$. The public key is $Q = xG$ (for DSA, with the multiplicative notation, public key is $g^x \mod p$). The underlying computational zero-knowledge proof protocol works like this:

Prover wants to prove to the verifier that he knows $x$, but without revealing $x$.
There is a known parameter $h$, a non-zero value modulo $q$.
Prover (aka, the signer) selects a random $k$ modulo $q$, and computes $A = kG$. He sends $A$ to the verifier; this is a commitment (by sending $A$, the prover marks that he has chosen some value $k$, which he will not be able to change later on in the protocol; but he does not actually reveal $k$).
Verifier chooses a challenge $r$ (supposedly random value modulo $q$) and sends it to the Prover. The cornerstone of the protocol is that $r$ is chosen after the commitment (the Prover cannot compute a specific value of $k$ which depends on the value of $r$).
Prover sends back $s = (h+rx)/k \mod q$ where $h$ is a non-zero. The verifier checks that this value matches the commitment and challenge by computing $(h/s)G+(r/s)Q$ which must be equal to $A$.

What goes on here is that the Prover commits to a random value $k$ and then proves that he knows $x/k$ (this is quite similar to the Schnorr identification protocol).

To turn this interactive protocol into a non-interactive signature scheme, we must replace the bit about the random challenge by something which can be computed by the signer alone, yet still be convincing enough about its "randomness" (as I said above, the protocol is good as long as the value $k$ cannot be chosen with a specific challenge $r$ as target); we also need to "inject" the signed message somewhere. So we do the two following things:

We say that the parameter $h$ will be the hash of the signed message.
We define the challenge $r$ to be the result of the evaluation of a given known function $f$ over $A$. The function $f$ can be quite arbitrary as long as it is deterministic and "somewhat uniform" over a big enough range of output value. For instance, if $\mathbb{G}$ is an elliptic curve, we can choose $f(A)$ to be "the $X$ coordinate of the curve point $A$, converted to an integer and reduced modulo $q$".

And, voila! you have DSA (or ECDSA).

The important point here is that the identification protocol is "computationally zero-knowledge" (i.e. yields no usable information on $x$, at least for a computationally bounded adversary) only because $k$ is chosen randomly and uniformly modulo $q$ every time the protocol is executed (i.e. for every signature). Indeed, the protocol does reveal quite a lot of information on $x/k$ (modulo $q$). But, as long as a fresh $k$ is used every time, the attacker is still short of information. In entropy parlance, we could say that $x$ is $n$ bits of entropy, the random $k$ injects $n$ extra bits of entropy, and the protocol reveals $n$ bits; so, if we run the protocol $z$ times, the total entropy is $n+zn$, and $zn$ bits have been revealed, to there still are $n$ bits of entropy unknown to the attacker -- precisely the private key $x$.

The seemingly redundant nature of (EC)DSA signatures comes from that point. We need to inject some entropy in the system, of a size similar to that of $x$. So, for instance, if we use a 160-bit private key $x$, there must be close to $2^{160}$ possible signature values for a given message $h(m)$, and since a signature on a message must not be valid for any other message, we still need $2^{160}$ distincts sets of signatures. Hence $2^{320}$ possible signature values altogether, for a 160-bit private key.

This extra size is consubstantial to the use of an underlying challenge-response identification protocol as the basis for the signature scheme, so we find it also for all kinds of derivative of the Schnorr identification scheme (including Schnorr signatures, ElGamal signatures, KCDSA...).


How many p and q pairs are there in a 1024 bit modulus?

Given a 1024 bit modulus, how many pairs of 512 bit p's and q's are there that would be able to be combined to create a 1024 bit modulus for use in RSA?

The fundamental property is that any integer is a product of a unique multiset of primes.  As such, given an integer $n$ that is a product of two primes, those are the only two primes that, multiplied together, produce that $n$.  So, the answer is 1 (if you ignore swapping which prime you call $p$ and which you call $q$).  The fact that factorization is difficult means that it's hard to produce $p$ and $q$ given $n$; however that doesn't change the fact that $p$ and $q$ are unique).

  Given a 1024-bit modulus, how many pairs of e and d could one come up with?

That is a harder question to answer; given that there is no natural bound on how large $e$ and $d$ can be (as you can find arbitrarily large values that work), one answer might be "infinite".

If we ask for the number of $e, d$ pairs where both are limited to $\textit{lcm}(p-1, q-1)$ (which may sound like an odd limit, but turns out to be reasonable), well, we first note that $e$ can be used as a public exponent iff it is relatively prime to $\textit{lcm}(p-1, q-1)$.  In addition, for any $e$ which can be used as a public exponent, there is a unique $d$ within the range that works as the decryption exponent (which is why that odd looking limit is a reasonable one), hence counting potential $e$ values is equivalent to counting $(e, d)$ pairs.  And, given that the number of values relatively prime to $\textit{lcm}(p-1, q-1)$ is $\phi(\textit{lcm}(p-1, q-1))$, well that's your answer (or one less, if you don't count the $e=d=1$ pair.


How to calculate size of a codebook lookup table to break block cipher?

Where is $2^{16}\cdot16$ bits coming from?

The $2^{16}$ term is the number of possible 16-bit blocks. The $16$ bit term is the space needed to store a block (that can be a block of ciphertext, with the plaintext used as index; or vice versa). The two are multiplied to get the total size, much like the price for $n$ things is $n$ times the price for one thing.
If we added the number of plaintexts and ciphertexts blocks, we'd get a number of blocks, not a size. And while we need to be able to manipulate all the plaintexts and all the ciphertexts, we do not need space to store both all the plaintexts and all the ciphertexts: one kind comes for free as the index of the table, which uses no space. Much like if we want to store what output from 0 to 9 correspond to input 0 to 9, we need 10 digits (like 8730629415), telling that 0 corresponds to 8, 1 to 7, 2 to 3,… 9 to 5; rather than 20 digits.
In this table of $2^{16}$ values, there are never two identical values. That makes it slightly compressible, down to $\log_2((2^{16})!)$ bit, a 9% saving.
Such a table needs not cover all plaintext/ciphertext pairs to be useful. A much smaller table can allow some attack. For example, a table with $2^8$ entries instead of $2^{16}$ allows decryption of about one block out of $2^8$.


"hex" vs. "base64" encoding when enciphering

Does encoding choice play a significant role in encryption for a cipher?

No.  Ciphers operate on bit strings.  It is far more important to focus on what kind of ‘cipher’ it is and what security goals it provides: you generally want an authenticated cipher like NaCl crypto_secretbox_xsalsa20poly1305 or AES-GCM, and you definitely don't want to reach for the letters A-E-S directly yourself.  Focus on security contracts.

  From security point of view, can the wrong encoding choice affect the outcome?

Not as far as the cryptography is concerned, but complicated encoding methods can pose security problems of their own:

If you apply a base64 encoder/decoder to the plaintext rather than ciphertext you might leak information about the plaintext via timing side channels in a naive array lookup for hexadecimal digits.
If you apply compression to the plaintext you might leak information about it via the length of the ciphertext as a side channel.
If your encoding method is buggy like an ASN.1 parser your application might barf its memory contents out like a bleeding-heart OpenSSL.


In a specific Paillier implementation, why is r prime?

Is there any risk in changing the implementation to make $r$ random but not necessarily prime?

None [1].  Consider the case where you encrypt two values, forming the ciphertexts $g^m r^n$ and $g^{m'} {r'}^n$, and then you homomophically add them (by multiplying the two ciphertexts).

That results in the ciphertext $g^{m + m'} (r \cdot r')^n$.

As a result, $r \cdot r'$ may not be prime [2]; if this were a security risk, that means that you really couldn't use homomorphic addition (or, actually, Paillier at all, as an attacker could take your ciphertext, add an encrypted 0, and generate another ciphertext that encrypts the same plaintext, but with a likely composite $r$).

Hence, there is no drawback for choosing a composite $r$

[1]: Other than the risk inherent with modifying any cryptosoftware and accidentally breaking something you didn't intend...

[2]: Actually, it might happen to be, as it's actually $r \cdot r' \bmod n$, and that value just might happen to be a prime within $\mathbb{Z}$


Randomness test question from FIPS 140-1 and comparison with 140-2

Q1: Why are these tests stroked out?

These tests are stroked out on pages 57-58 of the current FIPS 140-2 because they are no longer part of the current FIPS 140-2 standard, since Change Notice 2 of 2002 December third, where these pages belong.

My guess for the rationale of removing these tests is that

It was realized that the very principle of using theses RNG tests and bounds was unsound:

When testing a Cryptographically Secure Pseudo-RNG, a " cryptographic algorithm test using a known answer " (of 4.9.1) is good enough, and a statistical test on the output of a PRNG only a nuisance: the only errors it can report are false positives (else the very definition of the CSPRNG would be broken, when the intend is to test the implementation)!
When testing a True RNG, fact is that it is very hard to make a physical TRNG source that pass these tests (especially those in FIPS 104-2) with decent reliability, without some amount of conditioning between the actual TRNG source and the test point, especially if you account for process and temperature variation (on the field you will often get failures at a rate MUCH higher than predicted for a perfect RNG). This can be fixed e.g. with a LFSR inserted after the TRNG, but then a breakdown of the TRNG source will typically NOT be caught by the prescribed tests!

It was realized that mandating these test " when the module is powered up " (as required at least for level 4) is impractical in some unattended applications, culminating with Smart Cards (which admittedly do not aim level 4), where:

There can't be an operator to reset a "RNG test failed" condition.
There can be hundreds of devices (millions for Smart Cards), implying an unacceptable number of field failures in combination with 1 and false-positives in the mandated tests.
In addition, a Smart Card can be accidentally powered up several times per second in the normal (or at least practically unavoidable) operation of the device; I've witnessed applications powering off/on any unrecognized contact Smart Card like there's no tomorrow, and that will also occur when a contactless Smart Card is left in front of some perfectly reasonable ISO/IEC 14443 or NFC readers. So it would have been needed some creative redefinition of " powered up " implying intend to use rather than mere establishment of operating power.
We want to be ready fast after power-up.

Thus if you made something per the letter of FIPS 140-1 or FIPS 140-2 before Change Notice 2, it was bound to sometime report failure (and stop functioning save for a sometime impractical human action) even if it worked fine; and this sorry state of things was not a good insurance that it would stop working if the most probable and dangerous cause of field failure occurred (TRNG source stuck, almost stuck, or otherwise non-operative, like synchronized to power-supply ripple). And attempts to reduce the rate of false positives to the bare possible minimum would tend to seriously worsen the risk of letting a dangerously defective device run.

Q2: Are the changes an improvement?

The removal of the prescribed test is a great improvement. Now, competent implementors are at least able to make something that reliably operates when not defective, and reliably stops operating when it becomes defective. And the incentive to add conditioning (like a LFSR) that allows to pass certification at the expense of actual field security is gone. Previously, with some perfectly sound TRNG sources (like with a bias of a few percents, which is fine when followed by a CSPRNG), what was prescribed could not be the main defense against likely defects of the TRNG source. All modern methodology for RNG certification, like AIS31, recognize the need for some access to the TRNG source before conditioning, or/and a model of the source, and adapting the tests to that (including making more comprehensive tests when a first one failed).

Changes in test limits made from FIPS 140-1 to FIPS 140-2 with Change Notice 1 make each of the tests significantly dramatically more stringent (and thus much more impractical when used to test an unconditioned TRNG, and generating more false positives even for a conditioned one or a CSPRNG). I think I remember reading or hearing (sorry for the imprecision of that uncertain non-reference) that at least some of these changes are also related to the fact that the tests are not independent (thus it matters to the false positive rate if the 20000 bits in the 4 tests are from the same or different runs, the later significantly increasing the false-positive rate). The changes in the acceptance level in the runs test made in FIPS 140-2 Change Notice 1 (from FIPS 140-2 before that) is documented (page 54) to be a " correction ", that seems credible. Notice that the question gives, for the runs test of FIPS 140-2, a table of the erroneous bounds of FIPS 140-2 without Change Notice 1.

Update: As pointed by poncho in a comment, the increase in false positive rate from FIPS 140-1 to FIPS 140-2 (CN1) is dramatic, more than a hundredfold in the monobit test assuming a perfect source:$$1-\sum_{i=9,655}^{10,345}{20,000\choose i}/2^{20,000}\approx1/974,603\text{ for FIPS 140-1}$$ $$1-\sum_{i=9,726}^{10,274}{20,000\choose i}/2^{20,000}\approx1/9,662\text{ for FIPS 140-2}$$
What's worse, if one defines a good source as one that is less biased than some threshold (a reasonable requirement for a physical TRNG), the false positive rate can go from rare for FIPS 140-1 bounds to totally disrupting for FIPS 140-2 bounds; that probably eased making the right decision and removing the tests altogether.

Q3: Are bounds for the run test inclusive?

Perhaps that could be determined by computing the odds of failure with and without the limits of the intervals given for a true random source, and seeing if some some round number emerges.

But why care? Statistical tests of the output a conditioned RNG, including any CSPRNG, is pointless; and has not been indispensable to get rubber-stamped since late 2002. And while the statistical test of an unconditioned TRNG source are necessary (and the tests in FIPS 140-1&2 rather sound), the acceptance levels of FIPS 140-1, and much more FIPS 140-2, are typically too harsh unless there is some backup strategy (like redoing a more complete test; notice that redoing the same test drastically alter the meaning of its original acceptance level).


Formal definition of collision resistance for hash function

To define collision-resistance for a fixed hash function $H$, it probably looks like this:

CR: There is no efficient attacker (i.e., with polynomial computational resources) that can find two messages $m_0\neq m_1$ such that $H(m_0)=H(m_1)$ with non-negligible probability.

However, this is problematic because such an attacker may indeed exist but we just cannot find it easily. From the pigeonhole principle, we know for sure that there are two colliding messages for $H$. So, there exists a very efficient attacker who can simply output these two messages and break the above security.

To deal with this issue, one may attempt to rephrase CR as "It's hard to construct an attacker...". But then you got stuck on defining "hard to construct" formally, while in practice this is OK.

So, an easy fix is to introduce a large key space $K$ such that it's hard for any efficient attacker to output colliding messages for a randomly-chosen hash function $H_k$ (where $k\gets K$). Note that even if the attacker is given all colliding messages for all keys, it cannot "digest" them easily compared to the case with a fixed hash function because storing all colliding messages requires exponentially-large space (linear to the size of the key space) while the attacker has only polynomial computational resources.


What you call Block Sub-Keys, is called key schedule.

The first thing you need to know, is that this sub-key generation needs to be deterministic (else how would you be able to decrypt the cipher text).

Thus you are considering two cases:

a simple key schedule to generate the sub-keys.
a Pseudo Random Generator (or more usually a Hash function) to generate the sub-keys.

In the first case you have:
$$F(K) = K_1,\\
F(K_1) = K_2,\\
F(K_2) = K_3,\\
...$$

In the second case you have:
$$H(K) = K1 || K_2 || K_3 || ... $$
where $H$ is a eXtendable-Output Functions (XOF) such as SHAKE and $||$ is the string concatenation.

In the first case you have a sort of key dependence (from $K_1$ you can deduce $K_2$, but luckily not the other way around) while on the second case each sub keys are independent (you can't deduce $K_2$ from $K_1$).

From this point of view, surely the second approach looks the safest however, one must also consider speed and memory consumption.
Generating a long stream of bits in order to have the sub-keys takes time. If you were to compare the time spend on encrypting the data provided a set of sub-key and the time to generate the set of sub-keys, with this solution the slowest one would probably be the sub-key generation. And this is not something desirable if you want to have a usable cipher. Also the second methods requires to generate all the sub-keys at the initialization of the algorithm. This requires some memory...

To sum up, I'll point you to this two answers:

What are the requirements of a key schedule?
Does the key schedule function need to be a one-way function?


Is there a human readable easier version to represent PGP Private keys?

Apparently this answer will be updated as OP develop an understanding of his application. I've never used PGP, but general public-key cryptography concepts are always applicable.

  entering a private key on a website whenever you need to do something is troublesome

You can let clients derive their keys through memorable string - the user agent first derive a seed using a secure key derivation function (KDF) from 1) the user-supplied string, and 2) a random salt, then the seed is fed to a cryptographic deterministic random bits generator (DRBG), then the key-pair generation is run using the just-seeded DRBG.

Normally a hard-to guess 16-character string with upper and lower case letters and digits is a minimum. The salt should be a string of at least 16 fully-random bytes.

  But we also cannot maintain a central database for username/password

If you don't have a database of users, how do you authenticate them (recognize actual users from outsiders)? There is a solution: Use primitives that binds the authenticator to the public key, such as ECQV implicit certificate scheme, or identity-based encryption (IBE). These are not commonly-used public-key cryptography functionalities, and their post-quantum equivalents are far from mature.


Is deterministic encryption appropriate for low entropy plaintext when CPA is not a concern?

Yes, deterministic encryption would be a good solution to the problem you outlined.

Do however note, that an analytics service for credit card transactions will probably get information about payments like the time, location and amount. This can easily be used to create a profile for a specific ID. Given some extra information, for example from marketing companies, a deterministic ID can often be related to people. Whether this is an interesting consideration or not probably depends on the rest of the system.


Decrypting a vigenere cipher with a reused one-time pad

The crib-drag attack applies with a different operator.

p1 = AtextencryptedByFirstPassword
p  = HelloHelloHelloHelloHelloHell
c1 = hxpihlrncmwxpopfjtcgatldgdsco

p2 = ASecondEncryptedTextBySecondPassword
p  = HelloHelloHelloHelloHelloHelloHelloH
c2 = hwpncuhpyqycaeskxpihicdpqvroaozwhzfk

When you $c_1 - c_2 \bmod 26$ you will have the same problem as many-time-pad. This subtraction will remove the key.

 c1[i] - c2[i] = p1[i] - p2[i]

But this time instead of $\oplus$ we will have plus modulo 26.

 c1 - c2 = azafvjqcwecflqdfowgbijsmkszmm


How does the receiver compute the private key when using RSA?

I understand public key and private key is generated same time.

Yes, Bob does that, and gives the public key to Alice.

  The encryption is done with public key. Sender Alice sends public key [n,e] and cipher text C to Bob. Now is Bob recomputing the private key "d"?

No, Bob created the private key, and so doesn't need to 'recompute' it; he just saves it in secure storage.

  If Bob is computing the private key d, a "Man in the Middle" who gets the public key and cipher text can also do compute the same?

No, the man in the middle didn't create the public/private key pair, and so (unlike Bob) he doesn't have the private key in storage.

The only nontrivial issue here is "when Bob initially gives the public key to Alice, how does Alice know she got Bob's public key (and not a "man in the middle" public key)?".  Solutions for this include such as a one-time out-of-band authentication (say, a phone call, which might be worth it if Alice is going to encrypt a lot of messages with Bob's public key), or a "certificate" (which is something signed by a trusted authority which says "Bob's public key is [XXX], sincerely Big Brother")


Defining format-preserving encryption for natural language

The below is assuming a natural language is the one that has sentences from a well defined dictionary for that language (ex: oxford dictionary for english ).

We can do this with the standard approach for FPE i.e $rank-encrypt-derank$.
Build a $key-value$ pair map of all the  words in the language of preference  Where $key$ is the number and $value$ is the word. {Say from $1$ to $n$ }. $n$ being maximum number of words in dictionary.

Rank : For each word find the key which is a number
Encrypt: Apply the FPE algorithm of your choice (FF-1,2,3 OR FNR) or even simple fiestel network.
Derank the ciphertext of FPE algorithm which is a number by finding the respective word in the map. So the deranked word would be actual ciphertext

Decryption is similar .


Do key-dependent S-boxes make efficient constant-time software implementations almost impossible?

The point in the question makes senses, especially if one restricts to portable software implementations. But:

Small or moderately large constant-time RAM tables are reasonable, efficient, and (thus) common hardware building blocks. They are often used in DPA-protected DES and AES hardware coprocessors. Thus we can't dismiss key-dependent S-tables in hardware.
When knowing and controlling one's CPU well enough, constant-time table lookups are often possible (e.g. if there is no cache for data RAM, as is the case on many embedded CPUs).
There are other conceivable methods to guard against purely timing attacks, including releasing results with a fixed delay counted from start of computation, e.g. with the help of a hardware timer (however there often are other side-channels than pure timing, and that complicates things, a lot).


RSA-based authentication and key-agreement protocol

What you are looking for is authenticated key agreement with perfect forward secrecy based on certificates.

First, to address @Paulo's comment, TLS/SSL does provide this functionality with any of the Diffie-Hellman based suites. However it is more complicated than you require, as it generates several different shared secrets used for different purposes. SSH and IPSec have similar protocols.

The landmark key exchange protocol with the required properties is called the station-to-station protocol. I recommend the discussion of it (and the whole chapter for context) in the Handbook of Applied Cryptography (ch 12, pg 519).

STS does require an encryption function which you specified you wanted to avoid. A modern key exchange that does not have an encryption function is MQV and its variants. Since you also wanted a rigorous security proof, likely more has been written about MQV and its variant's security than any other protocol (although the history is somewhat sordid). The drawback for you is that it requires the public keys (in the certificates) are discrete log-based not RSA (STS can work with RSA public keys since the long-term secret is only used for signatures). It may also be patent encumbered.

To conclude, I don't have a perfect protocol that both works with RSA and avoids using encryption or MACs but looking into these two protocols should give you a head start on finding something you can work with.


Key derivation after ECDH: why h(q ‖ pk1 ‖ pk2)?

I'm not sure whether it's the only reason, but adding pk1 and pk2 gives you more entropy, hence a higher security level. Like the docs say, the number of points on the curve is $\approx 2^{252}$, so for a 256-bit hash function $h$ you have $\#\{ h(q) \}_q = 2^{252}$ instead of $2^{256}$.


Is there a symmetric-key algorithm which we can use for creating a signature?

Symmetric analogue of signatures.
The symmetric analogue of a signature is variously called a message authentication code, MAC, or authenticator.  The same key is used to create and verify authentication tags on messages.

Consequently, unlike signatures, third parties can't meaningfully verify MACs: if Alice sends a message with a MAC to Bob, Bob can't use the MAC to persuade Charlie that Alice sent the message because Bob could have created the MAC too.

Typical examples include HMAC-SHA256, keyed BLAKE2, KMAC128, AES-GMAC (which requires a distinct nonce for each message), and Poly1305 (which alone can be used only for one message per key).  Authenticators are often combined with ciphers to make authenticated ciphers like crypto_secretbox_xsalsa20poly1305 or AES-GCM, which simultaneously prevent eavesdropping and forgery.

Signatures built out of hashes.
You can also make a public-key signature scheme out of a collision-resistant hash function $H$, like SHA-256.

In the traditional one-time signature scheme of Lamport, you randomly generate a collection of 512 bit strings $x_{0,0}, x_{0,1}, \dots, x_{0,255}; x_{1,0}, x_{1,1}, \dots, x_{1,255}$, and publish $y_{b,i} = H(x_{b,i})$ as your public key.  To sign the message $m$, let $b_i$ be the $i^{\mathit{th}}$ bit of $H(m)$; the signature is $x_{b_0,0}, x_{b_1,1}, \dots, x_{b_{255},255}$—that is, you reveal $x_{0,i}$ if the $i^{\mathit{th}}$ bit of $H(m)$ was zero, and $x_{1,i}$ if the $i^{\mathit{th}}$ bit was one.  Anyone can verify this using your public key by checking whether $y_{b_i,i} = H(x_{b_i,i})$, but only you knew the preimages $x_{b_i,i}$ in advance.

Modern variants like SPHINCS extend this idea to many messages, and eliminate the need for collision resistance of $H$ in order to go faster.

There's no symmetric keys here but sometimes hashes are considered to fall into symmetric-key cryptography, since, e.g., the function $k \mapsto \operatorname{AES}_k(0)$ is supposed to be an irreversible hash.


A (probably weak) reason not to use a standard is that some nothing-up-my-sleeve numbers may serve some sort of purpose.  As an example, you cannot change Salsa20's constants to anything, it must be sufficiently asymmetric.  It's feasible to presume that another cipher may have a different set of requirements
As per this answer:

Salsa20 has strong rotational symmetry. The main point of these constant is that they're not invariant under rotations, introducing an asymmetry. The precise value isn't very important, as long as it's sufficiently asymmetric.

The answer goes into further detail, quoting DJB himself on the matter.
This answer also details several cryptographic constants, and the padding constant for HMAC is similarly designed to be asymmetric:

The padding constants for HMAC, 0x36 for ipad and 0x5C for opad, are repeated (for the hash function's block size) and XORed with the key to generate the prefixes for the two hashing steps. 0x36 = 0b00110110 and 0x5C = 0b01011100 - these two values are about "as different as possible", to avoid any attacks which rely on a similar hash state after the key block for inner and outer hash. This is mainly a heuristic, as far as I understand.


Is there a public key encryption scheme with optimal key size?

I am skeptical that there will ever be a public key system that has the property you are seeking. Of course it would be possible to wrap a public key system up inside a symmetrical system to get that effect. For example, I could use 4096 bit RSA key which I protect with a 56 bit DES key, thus giving the system the strength of that, weaker, 56 bit symmetrical key. But leaving such things aside, I think that public keys will always be "special" in that their size in bits is not a direct representation of their strength in bits.

Short statement of why I'm skeptical

Not just any number can be a secret key. So even if the worst case for the attacker who has to just randomly guess at candidate secret keys, they can rule out a large number of things before they have to start guessing.

Symmetrical strength.

To understand why I'm skeptical, it is important to understand why strength == keysize works for symmetrical systems. Only then can we look at what is different about public key systems.

Alice picks, completely at random, a 128-bit key, k for AES. If AES isn't broken, Oscar's best hope is to simply guess k. (Actually, Oscar's best hope is to not attack Alice's key at all and instead try to get the message before it's encrypted or after it is decrypted or something else altogether.) If Alice used a cryptographically appropriate random number generator to pick k then k will be any one of 2^128 numbers, each with equal probability.

Brute forcing symmetric keys

We are assuming through all of this (and this is a very fair assumption) that Oscar has a way of testing a key that will tell him whether or not he has the right one. In order to be sure of finding Alice's key, k, Oscar would need to make at most 2^128 guesses. On average, he only needs to check about half of those, so it is 2^127 guesses.

This works out that way because any candidate guess is as like (well, actually unlikely) to be the right one as any other. There is nothing to prefer certain guesses to others.

There is also no way (if everything else is designed properly) to get any information about k from looking at the encrypted traffic. There also should be no way to get any information about the key even if you know what some encrypted messages decrypt to. And finally (and this has been a really hot topic in practical cryptographic implementations), there should be no way to get any information about the key even if Oscar can get Alice to decrypt messages that he creates.  In sort, a properly designed symmetrical system reveals absolutely no information about the key other than the fact that it is, say a 128 bits long.

So that has all been a long winded way of driving home the point that Oscar's best attack is to just guess at keys and any 128-bit number is as likely as another other.

Public keys

Public keys are nothing like symmetrical keys. We've got the public key, p and the secret key, s.  Alice picks a secret key, s, and calculates p based on s. She then publishes p.  It is crucial that p is calculated from s. For these systems to work, there has to be a special mathematical relationship between p and s.  For RSA s can be a pair of really big prime numbers and p can be something like the product of those two primes. (For the rest of this discussion I'm going to pretend that p is the product of the two primes, that this isn't quite how RSA really works.)

As you probably know, Alice can solve problems using s that cannot be done with knowledge of p alone, but p can be used to create such problems and p can be used to verify that the problems have been successfully solved.

The strength of the system depends on (among other things) that it be hard to compute s from p.

Brute forcing private key

The analogy, I suppose, of a brute force attack on an RSA public modulus (to discover the primes) would be to take primes at random that are about the appropriate size (so half as many bits as p) and see if they divide p evenly.  So here you see that a brute force attack involves far far fewer guesses than the size of p.  If p is 2048 bit number, then the factors of p will each be around 1024 bit numbers.

Furthermore, not every 1024 bit number is prime; only about 1 in 300 of them are prime. (I'll say 1 out of every 256 so make rounding easier in my next step.) So for a brute force attack on a 2048 bit public key, Oscar "only" has to make 2^1016 guesses.

Now that is an awful lot of guesses, and would be more than sufficient. If this were the best way to discover s, then you would only need RSA keys about about 280 bits to get 128 bit security. But of course, this is an incredibly stupid way of attacking RSA.

However, there are two points from that simple example.

The secret key is (often) much smaller than the public key.
Not any number can be the secret key.

Either one of these mean that in terms of just blind guessing (brute force) the number of guesses necessary will be substantially shorter than the actual size of the public key.

Don't brute force

There are ways to try to go from p to s that are better than just doing that kind of random guessing. In the case of RSA, there are much better ways. In terms of the discrete logarithm problem in integer fields (for Diffie-Hellmen public key stuff), there are much better ways than brute force guessing to discover the private keys as well. Indeed, if the private key isn't chosen with considerable care there are enormous shortcuts that Oscar can take.

The best we can hope for

The best we can hope for is where guessing is the best strategy, but it will still be guessing in a limited domain. It won't be every possible number the size of the public key.  Even though ECC and DH are based on the discrete logarithm problem (DLP), they are the DLP in different fields, and ECC is holding up remarkably well.

I don't know if we have theorems that prove that ECC will continue to hold up. It isn't perfectly at this "best case", but so far it seems to be close to that.

Resources

I really recommend the book Understanding Cryptography by Christof Paar and Jan Pelzl. Chapters 8 and 9 do an outstanding job of explaining ECC and the kinds of attacks that might exist against it. The book is written well enough that it can genuinely be used for self study.


Does the time to evaluate a hash function depend on the function input size?

It all depends on how you define the machine that implements the random oracle. Consider this pseudo code random oracle that uses a hash table:

def rand_oracle(input, hash_table):
    input_hash_key = get_hash(input)
    if input_hash_key in hash_table:
        return hash_table[input_hash_key]
    else:
        return something truly random

You need to compute the input_hash_key by using the get_hash function. This function is usually implemented so that it's dependent on the length of the input.

Also, the line "if input_hash_key in hash_table" implies there is a test for hash collisions if any. This usually happens by comparing the input bits against the found entry. If they match (bit/byte by bit/byte), it's not a collision, else it's a collision.

So it all depends on how you view your machine that is implementing the random oracle. At some point, there are analysis that need to be performed for a length that is always dependent on the input length.

I think your confusion is from the fact that hash tables can perform lookups that are in the asymptotic worst run time complexity set O(1) if there is no hashing collisions -- yes this is the lookup/search time for the right entry, which different the time needed to generate the hash.


How does RFC 5652 authenticated data confirm origin and data integrity?

How would receiver know that it was not from originator?

The recipient doesn't know the sender with this scheme. It can be anybody.
Why? There's no secret involved in the sending process that is unique to the sender and thus anybody can create such a message, as you already noted.

  Why can't an attacker do this?

He can. However this looks more like a building-block for other schemes and as such these may implement advanced sender-authentication mechanisms which would prevent such an attack.

  How would receiver know that message has been changed?

The recipient always knows that the message is unaltered with respect to the sender, because the MAC is valid. The fact that the sender may change is not covered with this scheme (and in fact, an attacker does change the sender to himself with the obvious attack).


What is gpg2 algo 1 and 8 concerning its signature-procedure?

I assume that algo 1 means RSA

Correct. From RFC 4880:

9.1.  Public-Key Algorithms

      ID           Algorithm
      --           ---------
      1          - RSA (Encrypt or Sign) [HAC]
      2          - RSA Encrypt-Only [HAC]
      3          - RSA Sign-Only [HAC]
      16         - Elgamal (Encrypt-Only) [ELGAMAL] [HAC]
      17         - DSA (Digital Signature Algorithm) [FIPS186] [HAC]
      18         - Reserved for Elliptic Curve
      19         - Reserved for ECDSA
      20         - Reserved (formerly Elgamal Encrypt or Sign)
      21         - Reserved for Diffie-Hellman (X9.42,
                   as defined for IETF-S/MIME)
      100 to 110 - Private/Experimental algorithm

  What is algo 8?

It indicates that SHA-256 was used for computing the hash. Again, from the RFC:

9.4.  Hash Algorithms

      ID           Algorithm                             Text Name
      --           ---------                             ---------
      1          - MD5 [HAC]                             "MD5"
      2          - SHA-1 [FIPS180]                       "SHA1"
      3          - RIPE-MD/160 [HAC]                     "RIPEMD160"
      4          - Reserved
      5          - Reserved
      6          - Reserved
      7          - Reserved
      8          - SHA256 [FIPS180]                      "SHA256"
      9          - SHA384 [FIPS180]                      "SHA384"
      10         - SHA512 [FIPS180]                      "SHA512"
      11         - SHA224 [FIPS180]                      "SHA224"
      100 to 110 - Private/Experimental algorithm

You might want to try to get some practice in reading RFCs. It can be a bit overwhelming at first, but the information is all there - especially for the OpenPGP standard which is extensively documented.


RSA Optimal Asymmetric Encryption Padding Beginner

Yes, (Optimal) "Asymmetric Encryption Padding" means padding for asymmetric encryption which in practice means RSA encryption. The padded block is then RSA-encrypted, and on decryption the RSA-decrypted block is unpadded.

The drawing and description in Wikipedia is based on the original Bellare and Rogaway paper (link '1' from Wikipedia). The scheme actually used is specified in PKCS#1 and differs in a few details that don't affect security, but do matter for interoperation if that's your goal, or just exact understanding, and also uses somewhat different (but equivalent) notation.

The exact process is laid out in detail in PKCS#1 v2.0, republished conveniently as RFC2437 (linked from wikipedia), or the updated v2.1 republished as RFC3447 (linked on the IETF website), or the even newer v2.2 (only on the former RSA-labs site which is now EMC and every time I look they've reorganized it so just google). See 7.1.1 for pad-encrypt and 7.1.2 for decrypt-unpad.


Elliptic curve in Binary Field implementation

Yes it can. The only variation from the wikipedia article is in step 5 where it states to calculate $r\equiv x_1\pmod{n}$. This does not make sense when $x_1$ isbn element of a binary field. Instead binary field elements are converted to integers by a standards prescribed process (see ANSI X9.62-1984 section 4)


How many perfect secrecy systems are there?

How many non-trivial*, interesting perfect secrecy systems are there other than the one-time-pad?

Infinitely many.

Let $\mathbb G$ be a group (written multiplicatively). Then

$\operatorname{KeyGen}(1^n)=k\stackrel{\$}{\gets}\mathbb G^n$, that is the key is a vector of $n$ independently random group elements.
$\operatorname{Enc}(k,m):\mathbb G^n\times \mathbb G^n\to\mathbb G^n:(k,m)\mapsto m\cdot k$, that is the plaintext is a vector of group elements and the ciphertext is simply the element-wise multiplication of each message element with the corresponding key element.
$\operatorname{Dec}(k,m):\mathbb G^n\times \mathbb G^n\to\mathbb G^n:(k,c)\mapsto c\cdot k^{-1}$, that is we simply combine each ciphertext element with the inverse of the corresponding key element.

Note that the above defines an encryption scheme for each group there is and that's at least countably infinitely many ones (as $(\mathbb Z_n,+)$ works for all $n\in\mathbb N$). In particular it also works for non-abelian (i.e. non-commutative) groups.

The above scheme can be proven secure under a similar argument to the traditional one-time-pad and in fact the traditional one is simply this with the group $(\mathbb Z_2,+)$.


what method of transposition does AES 256 encryption use

What method of transposition does AES use?

Transposition is a simple movement of data to an alternative location. There are two relevant steps in AES when it comes to transposition: addRoundKey and shiftRows.

addRoundKey

The addRoundKey step incorporates a bitwise rotate left. This is a transposition of bits within a single word.

shiftRows

The shiftRows step is a transposition of bytes in the state. Each of the four rows of the state are shifted by an amount from $0$ to $3$ places. This step is designed to work in tandem with the mixColumns operation to ensure that changes in the state diffuse evenly and completely through the rest of the state.

Conclusion

The addRoundKey function incorporates a bitwise transposition, and the shiftRows step of the main function is a byte-wise transposition.

Note

  I'm interested in learning how to use AES-256 encryption in C/C++

All that being said, if you want to learn how the algorithm works, then implementing it is a good strategy and you should do so. But there is a lot more than functional correctness to consider in a secure crypto library - your code can produce correct input/outputs while still being vulnerable to all kinds of subtle and impressive attacks. After you are done implementing you might see if you can find/use any of these attacks to break your program.

If you intend to use AES to protect users data in the real world, you should strongly consider using a pre-existing library such as libsodium*.

* Note: I am not discouraging you from writing your own code, but using it is a different story. You wouldn't self-study karate for 2 weeks and then start up a mercenary protection service, for reasons that are obvious in the real world but not necessarily so obvious in the information world. Empowering yourself is great, but protecting people is against powerful adversaries who mean business needs to be taken seriously


Now, on to your question.
But, since reusing the IV with the same key is something that you should never, ever, ever do, I'm going to assume that instead, you are generating a new random IV for each encryption, but using the same global encryption key.

The answer really depends on what your colleague means when he says break. There are academic breaks and there are practical breaks.

Your colleague is correct if we are referring to academic breaks. Assuming you are generating good, random IVs for each encryption, after capturing $2^{64}$ ciphertexts, we can expect to have had one duplicate IV (this comes from the birthday problem). Given the two ciphertexts that have duplicate IVs, the attacker can distinguish whether or not the two ciphertexts encrypt the same plaintext. Or even more accurately, the attacker can determine the number of blocks starting from the beginning that are the same. Once one block is different, however, the attacker cannot distinguish any further. That is an academic break. Capturing $2^{64}$ ciphertexts would be a very noisy attack and would require lots of disk space to store. But is not outside the realm of possibility.

That said, I don't see any way an attacker could feasibly break the key or a plaintext only given access to a huge (but practical) number of ciphertexts.

A better design
What would probably be a better design would be to generate a new, random key and IV for every encryption. Encrypt the plaintext with those (and use HMAC or an authenticated encryption mode). On the server you should have an asymmetric key pair (for example, an RSA key pair). Encrypt that random symmetric key using the public (RSA) key. Send the ciphertext and the encrypted symmetric key to the client.

When the client sends this back, you would decrypt the symmetric key using your private (RSA) key. Then decrypt the ciphertext with that key and check the HMAC or authentication tag.

My final suggestion is to hire somebody very knowledgable in this area to review your design and implementation (or even to help out with the design process) so you are not putting your customers at risk. I doubt it would cost very much.


Combining CTR and ECB modes to prevent attacks

There are a few problems that spring to mind:

this is a double-pass scheme, which is computationally expensive;
the leakage of blocks that are identical is unnecessary, there are schemes that only leak fully identical plaintext;
ECB mode requires padding, so you would create some overhead.

Now you could argue that 1. is not a problem on current computers. However, that would only be a good argument if there weren't any schemes out there that would present the same properties without requiring a double pass.
As for 2, there are schemes such as Format Preserving Encryption that don't leak any information other than fully identical plaintext. FPE is generally rather expensive when it comes to implementation (on the other hand, not having to store an IV is generally not a problem for large binaries as they would generally have a VARiable size). Another option is to perform a block encrypt on the index and use that as unpredictable IV for CBC mode (possibly with ciphertext stealing if you don't like the padding overhead). Existing disk encryption routines such as XTS and ESSIV have already been mentioned.
As for 3, ciphertext stealing (CTS) for ECB mode can of course be implemented, but it definitely doesn't help with ease of implementation, which would be the major benefit over other schemes (ECB is generally available in e.g. SQL, and CTR is relatively simple to implement using ECB, although I definitely would not like doing so in SQL).
Finally, if you have room for an authentication tag, then a SIV mode (such as AES-GCM-SIV) could be used to remove the need for an explicit IV. If you've got room for both then just a generic AES-GCM would make sense of course.
All in all, I think that - while the scheme has merits - there are better options out there - preferably ones that are build into the DB engine.


What is the complexity for attacking 3DES in linear or differential cryptanalysis?

"Not vulnerable" is not how I would describe it, but my understanding is that the existing attacks on DES cannot directly not work with 3DES.

At the moment, the best attack against single DES is a linear attack which requires $2^{43}$ plaintext-ciphertext pairs, and has a time complexity of at between $2^{39}$ and $2^{43}$ operations.

Linear cryptanalysis works by trying to approximate the functionality of the cipher with some linear function, e.g. "if I plug all of the input and output bits into this polynomial I discovered, I can determine the value of the 26th bit of the key with a confidence of 72%". Given such approximations, an attacker with access to enough plaintexts and corresponding ciphertexts for a single key may be able to recover the entire key, or enough of it to make a bruteforce on the remainder feasible.

Many block ciphers, including DES, introduce non-linearity with an S-box. While it may be possible (or even trivial) to produce linear approximations of a single round of a block cipher, doing so for larger numbers of rounds becomes significantly more difficult. Assuming a good design, as you add more rounds, the number of possible internal states of the function increases, and the statistical significance of linear approximations decreases. This increases the number of plaintext-ciphertext pairs and operations you need, often to the point of making it less feasible than a brute-force attack.

Differential cryptanalysis works in a similar way. By observing how changes in input propagate through each round to the output, it may be possible to identify behaviours that leak information about the round keys. For example, one might select a pair of similar message values $m_1$ and $m_2$, and then compare $m_1 \oplus m_2$ and $f_r(m_1, k_r) \oplus f_r(m_2, k_r)$, where $f_r$ and $k_r$ are the round functions and round keys respectively. Statistical analyses of each separate round, in relation to their reactions to small changes in input, can be combined together to demonstrate properties that can be used to determine information about the values of the round keys in the full-round version of the cipher, or in a reduced-round variant (though this would not constitute a break).

The thing to keep in mind here is that attacks such as these rely upon the attacker having access to a large number of plaintexts and their associated ciphertexts for a key that they wish to recover. Removing this ability, or inhibiting it sufficiently, makes it incredibly hard to find practical attacks against even mediocre ciphers.

Now, the important question to answer here is as follows: can the existing attacks on single DES be reconstructed in a way that allows them to function against 3DES, where the attacker only has access to an oracle against the entire encryption process? (i.e. the values of the intermediate steps in 3DES are unknown to the attacker). The answer is essentially no. Since the attacks require the attacker to know a large number of plaintext-ciphertext pairs for each DES operation, but the intermediate values of the 3DES operation are unknown to the attacker in this scenario, the original attacks are no longer directly relevant - it isn't possible to just "run the attack three times".

Instead, new attacks had to be formulated against 3DES, using the same observations in previous attacks as building blocks, but applying them to a full 3DES operation. 3DES can be thought of as a 48-round variant of DES, as each round of DES is identical (aside from the key schedule, but that is irrelevant for LC and DC attacks). This now means that a full-round attack against 3DES requires linear approximations across all 48 rounds, or differential properties that can be correlated across the full 48 rounds. This is remarkably difficult to do - much moreso than against single DES itself.

The "typical" attack against triple encryption is what's known as a meet-in-the-middle attack. In such an attack against 3DES, we treat each DES operation separately, and attack a single plaintex-ciphertext pair. First, we perform decryption operations against the ciphertext for every possible $2^{56}$ keys, and store the resulting decrypted blocks in a list. This requires $2^{56} \times 64$ bits of space, or 512 petabytes. Next, we perform the first two DES encryption operations against the plaintext for every possible key (i.e. brute-force the entire 112-bit keyspace) until we reach an output that matches an entry in the previously computed list. Once we find a match, we know we've found the correct key. The time complexity of this attack is $2^{112} + 2^{56}$, which can be approximated down to $2^{112}$ due to the massive difference in exponent.

This basic idea has been improved upon somewhat for DES specifically - the best known attack requires $2^{32}$ known plaintexts, $2^{113}$ operations (consisting of $2^{90}$ DES encryptions and the remainder much faster operations), and $2^{88}$ memory. While, numerically speaking, this has more operations than the direct meet-in-the-middle, the vast proportion of those operations are much faster in practice. As such, the number of operations itself doesn't tell the full story in terms of actual computational cost, and the attack is faster than a naive meet-in-the-middle.


Collision in Merkle–Damgård without a collision in compression function

No, it is not possible.

If two inputs with different length produce identical hash outputs, then there would be a collision in the last invocation of the compression function. This is because the last input to the compression function always encodes the length of the original message.

If two inputs with identical length produce identical hash outputs, then there would be a collision in the compression function somewhere along the way. This is because considering the entire Merkle-Damgård hash as a hash tree build up of invocations of the compression function, then you will get two trees with identical structure, but those two trees have different inputs and identical output. By induction it can be shown that at least one of the invocations of the compression function in that tree structure must have a collision.


ElGamal message signatures retrieving the secret value x

$\newcommand\gcd{\operatorname{gcd}}$Let's have a look at the signature equation:

$$ s = (H(m) - x·r)·k^{-1} \mod (p-1), $$
$$ s·k = H(m) - x·r  \mod (p-1), $$
and thus
$$ H(m) - s·k = x · r \mod (p-1).$$

$d = \gcd(r, p-1)$ means we find (efficiently, given $r$ and $p-1$, using the extended euclidean algorithm) a $z$ such that $z·r = d \mod (p-1)$ ... this can be regarded as an "almost-inverse" for $r$ if $d$ is small.

If we multiply the equation above by $z$, we get
$$ z·(H(m) - s·k) = x·d \mod (p-1)$$

$s$ and $r$ are the signature, $m$ and $y = g^x$ are also known to the attacker, $d$ is a known small divisor of the modulus, and $k$ is also "small", which means that we can brute-force over all possible values of $k$ and for each one see if there is a solution for $x$.

The moral of the story: Use a random $k$, which will most likely not be small.


What is "blinding" with cryptographic hash functions?

There are at least three possible senses of blinding in crypto in a context involving a hash such as SHA-256. In all cases, the purpose is to hide something (the value, or the true meaning) of some data element manipulated.

Blinding with the hash as a tool used as a black box. The exact meaning depends on the purpose. That can further subdivides into

we only to need to compare data elements for equality, so we can hash them, then compare the hashes
we use the hash output combined (e.g. by XOR) with a data element to mask.

Blinding within the implementation of SHA-256, to thwart attacks trying to find the input of the hash from some side channel, like electromagnetic emission.

Blinding the input of the hash. This is the sense in the linked text

Consider blinding before calling an external function.You're passing your password into the MD5() and SHA256() functions plain-text-style.  If either is backdoor'd, then they get your password.  Consider blinding.

Here the goal seems to be hiding the password from an attacker having hooked the MD5() or SHA256() APIs (that could also be: able to invert these functions with a rainbow table). I think the author is suggesting transforming the password before hashing. That could be XOR-ing it with a secret constant, or applying some rudimentary cipher with a fixed key. This is not crypto, but an attempt to make code harder to reverse-engineer, or attacks more specific, using security by obscurity.


How does a chosen plaintext attack on RSA work?

Slight revision based on Paulo's remark in the comments - in a public key system a chosen plaintext attack is pretty much part of the design - arbitrary plaintexts can be encrypted to produce ciphertexts at will - by design, however, these shouldn't give any information that will allow you to deduce the private key.

A chosen ciphertext attack can be used with careful selection of the plaintext, however, to perform an attack - it's actually fairly straightforward on textbook RSA. Firstly, we have a piece of ciphertext we'll denote by:

$$C = t^e \mod n$$
Which is RSA as we know and love. Now, Eve has $C$ - this is perfectly ordinary, since Eve is supposed to be able to see $C$. Now eve has the ability to chose a plaintext - so, she choses $2$ as her plaintext and computes $C_a = 2^e \mod n$. However, to our unsuspecting victim she sends $C_b = C_a * C$, so:

$$C_b = C\cdot 2^e = t^e 2^e\mod n$$

All good so far. Now since this is a chosen plaintext attack we're reliant on having access to the decryption of our substituted value - so now the unsuspecting victim computes:

$$(C_b)^d = [t^e 2^e]^d = (t^e)^d \cdot (2^e)^d \mod n$$

However for any plaintext $x$, we know $C \equiv x^e$ and $x \equiv C^d$; so: $$(x^e)^d \equiv x \mod n$$

Therefore from the preceding result: $$(C_b)^d = t \cdot 2 \mod n$$

Hence when we get that value back, we can quite easily compute $t$. We simply need to halve it.

This can actually apply for any plaintext we wish to chose - I simply chose $2$ because I like it as a number. This paper covers the general technique and a lot more.

This only applies to textbook RSA. The proper application of RSA in the wild involves the use of padding schemes which defeat this attack by ensuring the ciphertext is not malleable in this way.


Is there any code available online for CHA-1?

This is an obscure and not peer-reviewed article of dubious quality (I'm being polite). It has far too many flaws to list here. It should be best left ignored. The author did not publish a reference implementation, and the software they used is most likely just a proof-of-concept, not usable in practice.


Just above the algorithm, the document says:

  If $f$ is irreducible, then $\gcd(X^{q^k}−X, f) = 1$ for all positive
  integers $k$ up to $\ell /2$

What the loop does is just testing all the $\gcd(X^{q^k}-X,f)$ up to $\ell/2$.

To avoid computing $X^{q^k}$ at each $k$, you just compute $X^{q^k}=(X^{q^{k-1}})^q=h^q$.

At the $k$-th round you will have $h=X^{q^k}$.


Can two traitors safely reveal themselves to each other?

But is there a way without a trusted third party?

Sure, one of the simpler solutions is probably to use Yao's Garbled Circuit Protocol to compute the AND gate. Note that actually using the original protocol will do here because the modern speed-ups are only important for large numbers of ANDs and malicious security would also be somewhat useless as a dishonest party can just lie and claim 1 to learn the other party's input bit.
So here's the basic protocol:
Setup Phase (executed only by Bob):

Pick $6$ random 128-bit keys and call them $k_A^0,k_A^1,k_B^0,k_B^1,k_\land^0,k_\land^1$.
Define the encryption scheme $E_{k,k'}(m)=(r,F_k(r\|0)\oplus F_{k'}(r\|0)\oplus m,F_k(r\|1)\oplus F_{k'}(r\|1)\oplus 0^{128})$ where $F_k(m)$ is a single AES-128 block cipher encryption call and $r$ is a freshly randomly chosen 127-bit value. The corresponding decryption function returns an error whenever the XOR of the third entry with the re-computed AES evaluations doesn't yield 128 zeroes.
Compute the "garbled table", that is compute $T_{11}=E_{k_A^1,k_B^1}(k_\land^1)$ and $T_{xy} = E_{k_A^x,k_B^y}(k_\land^0)$ for $x,y\in\{0,1\}$ with $x\land y=0$.
Randomly permute the four table entries, call the result $T_0,\ldots, T_3$, eg using a Fisher-Yates shuffle fed by a cryptographic RNG.
Compute $H_0=H(r\|k^0_\land)$ and $H_1=H(r\|k^1_\land)$ using your favourite cryptographic hash function, e.g. SHA-256 and some 128-bit random string $r$.
Send $T_0,\ldots, T_3,H_0,H_1$ to Alice.

Input Phase (executed between both):

Bob sends $k^x_B$ to Alice where $x$ is his input bit.
Bob also picks a random Diffie-Hellman key (e.g. for P-256), call it $t$ and sends the public element $T=[t]G$ to Alice.
Alice picks her own Diffie-Hellman key, call it $k$, and computes $K_c=[k]G, K_{1-c}=T-K_c$ for her secret protocol input bit $c$ and sends over $K_0$ to Bob.
Bob computes $K_1=T-K_0$ and chooses two new DH keys $r_0,r_1$ with $R_0=[r_0]G, R_1=[r_1]G$ and sends over to Alice $E_0=(R_0,H([r_0]K_0)\oplus k_A^0), E_1=(R_1,H([r_1]K_1)\oplus k_A^1)$ using your favourite hash function, e.g. SHA-256
Alice selects $E_c=(L,R)$ from the two received ciphertexts corresponding to her input bit $c$ and computes $k_A^c=R\oplus H([k]L)$

Note: The last 4 steps are my adaption of the oblivious transfer protocol of Naor and Pinkas from "Efficient Oblivious Transfer Protocols" (2001).
Computation (executed by Alice)
Alice now tries to decrypt all 4 entries of the garbled table $T_0,T_3$ using $k_A^c$ and $k_B^x$. Only one decryption should succeed recovering $k_\land$.
Output Exchange (executed between Alice and Bob)

Alice sends $k_\land$ to Bob, Bob now knows the result of the AND gate computation by virtue of comparing the value with $k_\land^0$ and $k_\land^1$
Bob sends $r$ to Alice who can then also recover the evaluation bit by re-computing $H_0,H_1$ and checking which hash matches.


PBKDF2 with longer than native output length - Will hashing the result help?

Restating and expanding on what the linked example says: when using PBKDF2-HMAC-H for storing a password hash (salted/peppered) for later comparison, it makes no sense to make PBKDF2's output size parameter $\mathsf{dkLen}$ more than the output size $h$ octets of H (if $h\ge16$ octets or similar threshold), nor more than perhaps $20$ octets, because:

The adversary doing brute force password search will seldom find a match of the first $h$ octets: when having found the right password, or with probability $2^{-8h}$ for random other inputs. The search can thus skip the (independent) computing of the other octets for the overwhelming majority of passwords tested. The extra data past $h$ has a cost for the legitimate user, but almost none (in proportion of total effort) for the attacker. Thus the legitimate user is better lowering $\mathsf{dkLen}$ to $h$ (as long as it remains enough to repel accidental match with the wrong password, which $\mathsf{dkLen}\ge16$ insures well-enough in practice), and should increase the PBKDF2 iteration count instead, which will cost the attacker.
In practice, odds of finding a password other than the genuine one that matches the hash over more than about $20$ octets are impossibly low, and adding more octets adds no useful security from that standpoint.

So there's not really a problem to solve; when using PBKDF2-HMAC-H for storing a password hash (with a common cryptographic hash thus $h\ge16$), we can just use $\min(h,20)$ for $\mathsf{dkLen}$, and pump PBKDF2's iteration count to whatever we can afford for comparable performance in legitimate use. If $\mathsf{dkLen}$ was $l$ octets with $l>h$, we can  multiply the iteration count (thus attack time) by a factor of $\lceil l/h\rceil$ at comparable cost for the legitimate user.

However, yes, it is correct that in an application keeping a password hash for later comparison, re-hashing the result of PBKDF2-HMAC-H with H (or another hash) with $h\ge16$ octets, and truncating to $20$ octets, will similarly shorten the result, and won't harm compared to storing the whole result. Indeed, computing the whole PBKDF2 output is necessary to find the overall hash, forcing an attacker to perform for each password tested all the work a legitimate user does. Security is thus comparable to reducing $\mathsf{dkLen}$.

The only benefit that I can think of in asking for longer output, and hashing it to get the final result, is that the increased complexity will require a slightly more complex code for a brute force password cracker. But that does not even require memory proportional to $\mathsf{dkLen}$ (the final hash can be computed on the fly), thus it will not markedly increase build and operating cost of a password cracker well designed with that oddity in mind.

Note: large $\mathsf{dkLen}$ can still make sense in applications of PBKDF2 other than testing if the password is correct.

Note: contrary to what the quoted remark suggest, it is not mathematically certain that if the first $h$ octets match, the others will; that's just very likely.


How does $g$ being a generator imply Diffie-Hellman's correctness?

It does not; the equation holds for any element $g$. The fact that $g$ is a generator means only that every element of the group can be obtained a key. This is not at all necessary for the protocol.


But when I try to decode the private key in the same manner, I get only 48 bytes for the actual key. What exactly do these bytes represent? Is this the curve point in it's compressed form? But in this case, shouldn't there be a flag at the beginning telling me that this is compressed form?

When we generate an EC public/private key pair, we pick a number $x$ and compute the elliptic curve point $xG$, which is $G$ (the well-known "generator point") added to itself $x$ times.

The public key is the point $xG$; because it is a point, we need to state whether we're expressing that point in compressed or uncompressed format.

In contrast, the private key is just the value $x$; this is just an integer, and so doesn't need to be 'compressed'.

As for why your $x$ is 48 bytes (or about 384 bits), we try to select the integer randomly between 1 and the size of the group (which is, in your case, circa $2^{384}$); selecting from a smaller range would reduce the security we get, and selecting from a larger range wouldn't help.


Why are cryptographically secure hashes required for digital signing (RSA or DSA)?

Well, if the hash function is weak, then the attacker might be able to take a valid signature for a signed message, and find a second message for which the signature for this first would also validate for the second.  For example, if Alice signs the message "I like chocolate", what Bob might do is find a second message "Alice owes Bob $13,106,107.57", and reuse the chocolate signature for the second message.

Here's how it works; when someone verifies the signature, they take the message, hash it, and then uses the underlying signature verification on the computed hash, the signature and the public key.  Note that once we have computed the hash, the signature verification logic doesn't pay any more attention to the message. Hence, if Bob can find a second message that hashes to the same value, then the rest of the signature verification logic will proceed as with the valid message.  Note that the attacker didn't need the private key to do this; all he needed was to find a second message that hashed to the same value.

The formal term for the property that a hash function doesn't allow someone to do this is "second preimage resistance"; that is, given an image, one cannot find a second image that hashes to the same value.

Now, it is possible that Bob can get Alice to sign an innocuous message that Bob had picked out (and then reuse that signature with a message that isn't quite so innocuous); because of this, we generally also insist that hash functions has a stronger property called "collision resistance"; that is the property that one cannot find two different images that hash to the same value.


How to determine the RSA Private key size from the Public.key file?

Assumption: you've saved the RSA public key using the default encoding in Java (for the SUNRSA provider), as in:

KeyPairGenerator kgen = KeyPairGenerator.getInstance("RSA");
kgen.initialize(1024);
KeyPair kp = kgen.generateKeyPair();
Files.write(new File("Public.key").toPath(), kp.getPublic().getEncoded());

This generates an X.509 ASN.1 SubjectPublicKeyInfo structure encoded using DER.

In that case you can retrieve the information from the public key using the following OpenSSL command:

openssl rsa -pubin -inform DER -in Public.key -text -noout

This will show the following output:

Public-Key: (1024 bit)
Modulus:
    00:c3:7e:ea:ba:9d:55:81:ec:80:8b:68:fb:7b:80:
    14:d4:66:45:0e:ba:6e:45:98:23:dc:24:26:a4:30:
    0e:20:48:12:23:b3:8b:5e:ed:c2:a5:cf:5e:32:43:
    00:9b:61:6e:e7:a6:f4:01:55:e9:cc:a8:c7:29:24:
    fd:29:7b:a1:b9:4b:1c:4c:de:cc:f6:d0:7e:75:a6:
    5f:28:09:65:67:76:1c:e8:f5:ae:85:ad:4a:dc:48:
    ca:82:46:25:e1:17:f8:3b:0c:53:30:c4:bb:08:5a:
    75:43:8a:d3:26:97:35:a7:2f:61:c6:68:06:24:b3:
    c8:42:e1:53:40:39:95:46:c9
Exponent: 65537 (0x10001)

As you can see, the key size is in the first line of the output.


How to use "mod" related words in technical paper？

A modular operation is an operation done modulo some modulus.

"modular" is an adjective: modular inverse, modular operation, modular reduction, ...
"modulo" is indeed the Latin ablative of modulus, and that makes it an adverb: I walk modulo $n$, just like I walk fast.
"modulus" is a noun: the number $n$ is the modulus that you would use in some system.


How can I map arbitrary group elements to unique integers without using Hash functions?

The order of every element $g$ of a group $G$ divides the order of the group ($p$).

Since $p$ is prime, every $g\in G$ has order $1$ or $p$. Only the identity element $e$ satisfies the first case, so every $g\in G\setminus\{e\}$ is a generator of $G$, i.e., $$G = \{g^0,g^1,g^2,\cdots,g^{p-1}\}.$$

This allows defining a bijection $$\begin{array}{cccc}\varphi:&\mathbb Z_p&\rightarrow& G\\&n&\mapsto&g^n\end{array}.$$

If you can find $\varphi^{-1}$, you're done.


AES-CBC then SHA vs AES-GCM for encrypting and authenticating a web token

just appended some bytes to the ciphertext, and found that it decrypts
  successfully

Normally this shouldn't happen, as the appended bytes surely aren't a valid authentication tag for the previous "ciphertext". I suppose (but don't know!) the implementation you are using encoded the length of the ciphertext, the associated data and the tag and retrieved these values upon decryption, ignoring the added values, yielding a correct decryption.

  AES GCM is authenticate then encrypt algorithm? because I feel that
  encrypt then authenticate feels more secure to me

AES-GCM is an authenticated encryption algorithm. Encrypt-then-Authenticate is one specific construction that achieves this general definition and is indeed preferable to Authenticate-then-Encrypt, which is why GCM internally does encrypt-then-authenticate and so AES-GCM achieves the same security definition as CBC-then-HMAC.

  is AES-128-CBC then SHA-256 more secure than AES-128-GCM?

When you say "AES-128-CBC then SHA-256" I suppose you actually mean AES-128-CBC with HMAC-SHA256 authentication on the ciphertext.

Then yes, technically that is more secure, because HMAC-SHA256 requires $2^{128}$ operations to come up with a forgery, whereas AES-128-GCM allows you to perform a multi-target search for a key that works dropping security slightly below $2^{128}$. So it also has a serious security level unlike CRC. Also from this we can infer that both are secure, as neither $2^{128}$ nor $2^{100}$ operations are feasible making them both "secure" (a.k.a. "meh, can't break"), so you might as well use the easier-to-use and faster AES-GCM, assuming you have hardware support available, which is the case on modern x86 processors.

See Squeamish's comments below for a more detailed discussion of the actual values. Also see their answer here.


Secrete message sharing using N private keys

I am not sure if I understand your requirement correctly, but from the first part of your
description I think you want the following (I skipped the second part since I do not understand the meaning of "$+$") :

Set up a public key $pk$ which can be
used to encrypt a message $m$ and you want to split the corresponding
private key $sk$ into two shares $sk_1$ and $sk_2$ such that given a
ciphertext $c$ encrypting a message $m$ under $pk$ can first be
decrypted using $sk_1$ to some intermediate ciphertext $c'$ and then
using $sk_2$ be decrypted to $m$. The goal is that decrypting with $sk_1$ reveals nothing about the message but if decrypted with $sk_1$ first and then with $sk_2$ will reveal the message to the entity holding $sk_2$.

Here is an example using ElGamal encryption.

Setup:

Let $p$ be a safe prime and $g$ be a generator of an order $q$ subgroup of $Z_p^*$. Let
the public key $y=g^x$ for some random $x\in Z_q^*$ and $x$ be the private key.

Now the partial private keys are $x_1$ and $x_2$ such that $x\equiv x_1+x_2 \pmod q$ and give
$x_1$ to $A$ and $x_2$ to $B$.

Standard Encryption:

To encrypt a message $m\in Z_p^*$ just do it as with standard ElGamal, i.e.,
compute the ciphertext $c$ as $c=(c_1,c_2)=(g^k,m\cdot y^k)$ for $k$ random in $Z_q^*$.

Standard Decryption

You can decrypt as you do it with ElGamal when you want to directly decrypt using $x$, i.e.,
compute $m$ as $c_2\cdot (c_1^x)^{-1}=m\cdot c_1^x\cdot (c_1^x)^{-1}=m$. Note that in the equation I write $y^k$ as $c_1^x$ as $c_1^x=(g^k)^x=(g^x)^k=y^k$.

Sequential Decryption

Now in order to sequentially decrypt a ciphertext $c=(g^k,m\cdot y^k)$ encrypted under public key $y$ by first
$A$ and then $B$ (one can also switch to first $B$ and then $A$) one proceeds as follows:

$A$ is given a ciphertext $c=(c_1,c_2)=(g^k,m\cdot y^k)$ and partially decrypts it to $c'$ by computing $c'=(c_1,c_2')$ where $c_2'= c_2\cdot (c_1^{x_1})^{-1}$.

Then $A$ gives the "partially decrypted" ciphertext $c'=(c_1,c_2')$ to $B$. $B$ then
decrypts $c'$ to $m$ by computing $m=c_2'\cdot (c_1^{x_2})^{-1}$.

To see that this is correct observe that

$$c_2'\cdot (c_1^{x_2})^{-1} = c_2\cdot (c_1^{x_1})^{-1}\cdot (c_1^{x_2})^{-1} = m\cdot c_1^{x_1}\cdot c_1^{x_2}\cdot (c_1^{x_1})^{-1}\cdot (c_1^{x_2})^{-1}=m.$$

Clearly you can generalise this to arbitrary $n>2$ additive shares of the private key $x$ such that only the $n$'th user in the chain of partial decryption learns the message $m$.


How did "Secure Voice" work on the old Air Force One's?

They used a scrambler[wikipedia] (not “encryption“ and definitely not a “One-Time-Pad” as some think [comment] [comment]) to transmit messages via a SatCom (read: military satellite) system. The scrambler they used back then was (let's just call it) “non-optimal” and has been replaced with an enhanced system. That's also what the sign is hinting at, among other things.

Scramblers and jam resisting implementations are only distantly related to cryptography, but somewhat comparable to how synchronizable, bit-wise stream ciphers and/or lightweight hash algorithms work. Yet, the goal of scramblers is different from a security perspective.

Scramblers use a secret spreading sequence or secret hop sequence, or some other information that must be kept secret from a potential jammer and/or listener. This mostly (and certainly back then) assumed sender and receiver to have a shared secret… somewhat like a seed for an (CS)PRNG. Back in the days, those shared secrets were stored analogue, while meanwhile things have (in most cases) been digitalized.

As a matter a fact: at the time of writing this, there is only one scrambling system for achieving jam resistance without any shared secret: BBC coding. BBC coding is able to provide unkeyed jam resistance. For a quick read on the subject, you can check (for example) the MilCom2012 paper The Glowworm hash: Increased Speed and Security for BBC Unkeyed Jam Resistance (PDF).

I'll skip the “Bonus” about “the radiophone that rarely worked“ as that would push this Q&A too much into the off-topic area and will quickly become too broad. Instead, I'll add an aside…

Aside: In case you'ld like to dive into the current state of scrambling and jam resistance, you could take a look at a related meta question I once asked, which happens to contain a whole list of related papers. Using your favorite search engine, you'll be able to find the related papers as PDFs.


Size of $E$ over $\mathbb{F}_p$ contains $p+1$ points

For every $y \in \mathbf F_p$, there is a unique $x \in \mathbf F_p$ such that $(x,y)$ is on the curve, namely $x = \phi^{-1}(y^2)$, where $\phi : x \mapsto x^3+1$. Adding the point at infinity, that gives $p+1$ points.


How do ciphers change plaintext into numeric digits for computing?

Say you want to encrypt "Hello World" with RSA.

The first important thing here is the encoding of that text. "Hello World" as such cannot be encrypted since characters are a non-numerical concept.
So an encoding is used convert the characters of that text to numeric values (e.g. the ASCII / Unicode table, but there are many others, especially for non-latin characters). Using Unicode-8, "Hello World" turns into this sequence of bytes (hex-notation):

48 65 6C 6C 6F 20 57 6F 72 6C 64

Such a sequence of bytes can then be interpreted as a number by assigning a most-significant and least-significant byte (e.g. the more left-sided, the more significant). That sequence would then equal the number

0x48656C6C6F20576F726C64 or 87521618088882538408046480

But since such a small number would not produce a secure ciphertext (as @SEJPM already said), a padding is applied. The sequence of bytes then might look something like this:

01 48 65 6C 6C 6F 20 57 6F 72 6C 64 98 9C 38 83 E1 64 E7 0B BC F2 43 C0 6B
26 D4 5E AC 9B C9 DC 2F 1B 87 46 3D 2E 6F 86 66 5E 1B CB 44 DA 5A 50 79 2F
40 79 88 83 84 3E 16 9D 7F 1F 05 2C DF F2 9B 9B 07 11 F6 7A CB 1C 35 9B 76
BD 8D 46 1C E0 09 2A 9F C5 B8 A9 FB 61 41 ... up to the bitsize of N

That sequence is then interpreted as a number and shoved through the algorithm.


If the ring is multiplicatively commutative, the obvious way to do this is:

Have each pair $a, b$ create a secure connection, and jointly select two random invertible elements $r_{ab}$ and $r_{ba}$ with $r_{ab}r_{ba} = 1$ (that is, they're inverses of each other).
Then, $$r_a = \prod_{b \ne a} r_{ab}$$

This is secure (in that any group of parties know nothing about the shares that everyone else has, except the product of their shares), however it does require $O(N^2)$ communication.

If we reduce the requirement to "no single party can deduce anything about any other party, then we can reduce the communication to $O(N)$ (by having $a$ exchange with $a+1$ and $N$ exchange with $1$).


Adapting RSA Timing Attack for Square And Multiply from right-to-left vs left-to-right

I was finally able to adapt the attack. The solution is to use the reduction of the squaring of the following bit as a discriminator between the two groups. That is we split into two paths, i.e. (R^2 mod m)^2 mod m and (R^2*b mod m)^2 mod m. For each path we create two groups by whether the final mod has an additional reduction. Finally we check which two groups has a higher difference of means, just like the right-to-left variant. This works very nicely, except for the last bit, which we can simply solve by checking for a difference in variance as before.