Evaluating a TRNG device positively requires knowing its structure, both to evaluate the actual amount of entropy it produces, and the possibility to detect a field failure.

Some devices sold as TRNG are in fact a TRNG subsystem followed by a PRNG, which produces the output of the device. In that case, if the PRNG is any good, the output of the device may appear random even though the TRNG subsystem produces no or little entropy, opening the possibility of an attack (perhaps just by enumerating the possible outputs of the TRNG subsystem), especially for an attacker knowing enough about the PRNG.

To illustrate: consider an hypothetical Smart Card with an RNG amounting to a TRNG subsystem followed by an LFSR-based PRNG, which task is to hide any small imperfection of the TRNG subsystem. In case of total failure of the TRNG subsystem, perhaps induced by very cold temperature (as obtained non-destructively by evaporation of a liquefied gas poured on the card), it is easy to guess future output from past one (if the PRNG has few state bits, the output has a short period; even with many state bits, the full state is known after that many bits have been output, with knowledge of the LFSR feedback; even when that's unknown, Berlekamf-Massey allows an efficient attack). There might be less obvious failure modes at different temperatures. If the PRNG is fair (e.g. based on the ASG and enough state bits) but secret, only those in the know of the PRNG design are in a good position to detect the failure, or exploit it.

To avoid this, a modern Smart Card RNG may keep the same basic structure, but with hardware to detect total failure of the TRNG subsystem (e.g. when it outputs constant 0 or constant 1), with some access by the software to the output of the TRNG, to enable testing and certification. Any cryptographic TRNG should have some monitoring system able to detect its failures. In the case of a USB RNG, mere accidental under-voltage could cause the source to fail; and USB ports fuses, hubs and their power supply do fail! Monitoring is a must in contexts where an adversary is in a position induce failure. The monitoring system can be hardware or software, internal or external.

This is a requirement in the AIS31 scheme for common-criteria security evaluation of TRNG (index in German, linking to documents in English; see also how French authorities have been using AIS31 method, including some reservation in section 5). This the best such methodology I've used, although I find it much more complex than necessary to the point of being confusing, and not free from error especially in the examples. My advice if you want to assess by yourself the soundness of a TRNG (rather than delegate that to security certification) is to follow the principles behind AIS31, which I can loosely outline as:

the structure of the RNG must be known and it must guide the evaluation;
the TRNG hardware source must be modeled in some way;
there should be some access to the output of that TRNG hardware source, allowing to check experimentally that the model is sound;
some system must monitor and detect possible failures of the TRNG hardware source, and in that event prevent operation (such monitoring system typically uses the output of the TRNG hardware source);
the model of the TRNG hardware source must support the effectiveness of that monitoring system;
before actual use as key material, the output of the TRNG hardware source must be post-processed by a PRNG, preferably a cryptographically strong PRNG;
the model of the TRNG hardware source must support that comfortably more entropy is fed in the (CS)PRNG than is necessary for security of the output of the (CS)PRNG in any situation where the monitoring system allows operation;
the false alarm rate of the monitoring system should be functionally tolerable (that one tends to be hard to demonstrate).

With access to a raw bit stream produced by a TNRG hardware source, at a point amounting to the output of an analog comparator followed by sampling with a clock, one could do worse than experimentally evaluating the entropy in sub-samples of say 4 to 16 bits (depending on RAM resources and time allowance) by frequency counting, computing experimental entropy from that; doing this as monitoring, with some threshold comfortably below the experimental value; assuming the real entropy is a small fraction of what the threshold supports; and post-processing the whole output with a CSPRNG.

A note on thermal noise vs "radio noise" TRNG sources: I've never met the later, and suspect that it is hard to prove that an attacker can't beam some RF signal towards the TRNG source, strong enough to turn its output into a square wave under the attacker's control.

Thermal noise TRNGs are more classic. They are known to be susceptible to temperature variations; in theory, the colder the less entropy; but high temperatures can introduce undesirable effects in the detector following the source. This might need to be considered (it is very relevant in a Smart Card, not much to something hooked to a PC operated in a trusted environment).

My limited understanding of physics make me see thermal noise as having its origin in quantum noise. I'm equally confident in either as a source of unguessable bits for cryptographic purposes. In my opinion, what matters more than the quantum vs thermal origin of the noise is how it is extracted and converted to bits, and the robustness of that with respect to failure modes and external influence.

This is one area where CSPRNG post-processing helps: in a cryptographic context, it insures that an attacker must have near perfect control of the TRNG source to gain an advantage. As soon as about 160 bits (give or take a factor of two) of actual entropy has been fed into the CSPRNG (without the output being observable by the adversary meanwhile, as rightly pointed by @CodesInChaos), and baring any attack on its design or implementation, the output is indistinguishable from random for any practical purpose (that's even though any CSPRNG using finite memory and no more seeding has a finite period; we are considering computationally bounded adversaries).

The output of any TRNG can't be better than that! On the contrary, in my experience, the unconditioned output of a TRNG source is never free from some detectable bias. If a stream of bits of arbitrary length has odds of 0 vs 1 passing a basic chi-squared test (and especially when that stands taking the effect of temperature and device variation into consideration), this is strong indication that it is not the output of an unconditioned TRNG. And again, any post-processing of the TRNG source must be known and taken into account (in addition to the nature of the source) when assessing the TRNG, and especially the effectiveness of its monitoring.


Now, the AES Key Schedule may be weak (it certainly does appear to be the weakest part of AES); however, I don't believe invertibility is really the problem.
If someone has a way to get some information on the last-round subkey for an N round cipher, well, he has some information on the original key if the key schedule is invertible; if he determined $k$ bits of that subkey, that is equivalent to knowing $k$ bits of key. Using that to complete the attack is the easiest way to attack the key, and so that's what attacks on AES (and AES variants) do.
On the other hand, if the key scheduling were noninvertible, there is another avenue of attack; gaining information on the last-round subkeys also gives us information about what the cipher state was after N-1 rounds. Using this information, we can presumably use the same style of attack to get information about the N-1 round subkeys. And, since we're asking the distinguisher to go through one less round, it'd presumably be stronger, and hence can be expected to take less effort than recovering the round N subkeys. Then, after recovering the round N-1 subkeys, we can start attacking the round N-2 subkeys, etc.
With this hand-waved approach, the attacker can get the entire set of subkeys with an effort that is only a constant factor greater than obtaining the single round subkey. And, even if knowledge of all the subkeys cannot give us information of the real key, it is enough information to encrypt/decrypt with the keys (which is usually why we're interested in the key in the first place).
Again, published attacks against AES and AES-variants don't take this approach, because it is more work (and harder to specify) than inverting the key schedule; however, it does show that making the key schedule noninvertible won't, by itself, make things that much more secure. If it does make things more secure, it's because that change would prevent someone from finding the last round subkeys, instead of preventing him from parlaying that knowledge into knowledge of the original key.
In addition, making the key schedule invertible does have these benefits in practice:

It's easy to prove that each subkey is unbiased (that is, each of the possible $2^{128}$ values is equiprobable), given that the original key is unbiased. If the keyschedule were noninvertible, well, this might not hold (and, in fact, with a 128-bit key, there would likely be values that a particular round key cannot hold). It's not at all obvious if having nonuniform subkeys would lead to a weakness, however with an invertible key schedule, we don't have to worry about it.

One implementation approach that I've seen that some AES hardware take is that if the AES key was to be used for decryption, we give the hardware the last round subkey (and possibly next-to-last for 192 and 256 bit AES). Then, as the data was being decrypted, the hardware would run the key schedule in reverse, deriving the previous round key as required. This allows the hardware not to run the full AES key schedule before starting decryption, and also without having the full AES subround keys preprogrammed. This approach may be trickier with a noninvertible key schedule (depending, of course, on the details of how it works).


Zero-Knowledge proof for data being decryptable to a given hash preimage

There has been some recent progress [1] on efficient zero-knowledge for such statements. Essentially they present a $\Sigma$-protocol to prove statements over general circuits. To prove the AND relation you state, you could essentially just build one large circuit which takes (the bits of) $r$ as input and outputs $h_r$ and $h_m$ so that $h_r = \operatorname{SHA256}(r)$ and $h_m = \operatorname{SHA256}(\operatorname{Dec}(\hat m, r))$, where $\hat m$ is hardcoded in the circuit.

The proofs above are of linear size in the number of AND gates in the circuit. If you want something more compact you might want to have a look at SNARKs.

References

[1] https://eprint.iacr.org/2016/163.pdf


Does there exist a deterministic, invertible function $\{0,1\}^n \rightarrow \{0,1\}^n$ that is not a bijection?

Does this have to be explicitly said?

You stripped the preceding context from that quote:

  Let $F$ be a mapping $\{0,1\}^n × \{0,1\}^s → \{0,1\}^n$. $F$ is a PRP if

  For any $K ∈ \{0,1\}^s$, $F$ is a bijection from $\{0,1\}^n$ to $\{0,1\}^n$.
  [...]

Not all mappings $F : \{0,1\}^n × \{0,1\}^s → \{0,1\}^n$ are bijections for all choices of $K$, so yes, the definition certainly has to state the bijectivity requirement.

  Is it even possible for this not to be true for a deterministic, invertible function where the input and output domains are the same?

You're reading the definition with an implicit assumption in mind that the function must be invertible, but the clause you're pondering is the one that actually states the requirement.


Usually. $\:$ A variable-length input keyed-PRF is a [PRF's output length]-bit MAC.

In particular, a variable-length input keyed-PRF with long output is automatically a MAC.


Why multiple homomorphic operations on a ciphertext leaks no information about the plaintext?

If the parties do exactly what you have described, then yes, the malicious server can learn some information. In particular, if $h_1 == h_2$, then $c_D == c_E$. So, given the $c$ values, the malicious server can learn whether or not $h_1 == h_2$. Furthermore, the malicious server can learn if either $h$ value is $1$, as $c$ would not change. Finally, if the $h$ values are drawn from a small set of numbers, where the set is known to the malicious server, the malicious server can actually brute-force the $h$ values given the $c$ values.

This is all due to the fact that homomorphically multiplying by a constant (which is done via exponentiation in the ciphertext domain) with Paillier is deterministic. Given the same ciphertext value and the same constant, you will get the same result.

To fix this issue, you should homomorphically add a fresh encryption of $0$ to the ciphertext after any operations. This rerandomization step* is very important when using Paillier or other additively homomorphic ciphers.

* Sorry to link to my own project on this, but it illustrates the point, I think.


Why does RSA OAEP add this many zero bytes?

The choice of $n_\text{Len}–K_\text{Len}–2\,H_\text{Len}–2$ zero bytes seems arbitrary

No. It's actually tight given what RSAES-OAEP does:

allow any modulus $n$ of $n_\text{Len}$ bytes,
$H_\text{Len}$ bytes for the hash of the tag,
$H_\text{Len}$ bytes for an unconstrained random seed,
length of the message (that is, the value of $K_\text{Len}$) encoded in the padding.

$n_\text{Len}$ is the number of bytes to represent the modulus $n$, that is $\left\lceil b/8\right\rceil$ where $b$ is the modulus size in bits. An all-ones bitstring encoding a value less than $n$ needs to be $b-1$ bits, thus we can't use more than $n_\text{Len}-1$ bytes for the padded message. From that we need to remove $H_\text{Len}$ for the hash of tag, and $H_\text{Len}$ for the seed. By a counting argument we need at least one bit to encode the length of the message, which is variable and must be encoded into the padding. That one bit has been rounded up to one byte, and that's all the leeway there is to fit the message of $K_\text{Len}$ bytes.

The scheme to encode the length of the message is that the message is left-padded with a bit at 1, then bits at 0 for what remains. Decoding the bit length of the message (equivalently, removing the padding) remains simple. This scheme is maximally compact for long messages: if RSAES-OAEP allowed bit-sized messages, it would allow messages up to $8\,K_\text{Len}+7$ bits. With such allowance, the entire padding (bits at 0 and the bit at 1) would provide nearly no redundancy: over the $n_\text{Len}–2\,H_\text{Len}–1$ bytes used for message an padding, only the all-zero bitstring would be invalid.


Good pre-image resistance value for hash visualization

I disregard the perfect hash requirement.

In the application asking for preimage-resistance with a narrow hash, one should use a purposely-slow memory-hard hash (as used for passwords, also known as key-streching or password-based hash). This greatly reduces the number of bits needed for preimage resistance.

More precisely, we want to build a hash that starts with a fast hash of the payload (e.g. with SHA-512), then performs a slow hash of the result and (if the application allows) salt¹ and/or pepper² (e.g. per Argon2id), with the largest parametrization (iterations, threads, memory size) that the application allows.

If in the application one spends 1 second slow-hashing, and the adversary can spend $2^{25}$ more time (over a year) with $2^{20}$ (over a million) more×better computing resources, and we want residual probability $2^{-10}$ (less that one in a thousand) that the adversary succeeds, we need $25+20+10=55$ bits of hash.

This hash size is date-independent, but does not account for how much time the system must remain secure without adjustment of parametrization of the slow hash. Add like 1 or 2 bits per year to account for progress in technologies.

Caution: the need for collision-resistance is easily overlooked³, and much more bits of hash are needed for that. With the same hypothesis, we'd need $2\times(25+20)+10-1=99$ bits of hash (see this), and twice more extra bit per year for progress in technologies.

¹ Salt could be an email or/and a random number. The idea is to make it impossible for an adversary to amortize the cost of the slow hash across multiple targets with different salt, and make it impossible to start a meaningful attack before knowing the salt.

² Pepper could be a server-unique string, tentatively kept secret, but considered public in a conservative security analysis.

³ For example, collision resistance is required for integrity if an adversary can influence the hashed content after the last unpredictable step in its generation. With preimage-resistance only, a maintainer of a Unix distribution that uses an automated nightly build is vulnerable to a contributor maliciously changing a text in release note and becoming capable of producing something unrelated to the original but with the same hash.


Advanced Composition (Differential Privacy)

Turning arcynia's comment into an answer so this question can be marked as fixed: « The very next paragraph of the book explains this: "Note that the above corollary gives a rough guide for how to set $\varepsilon$ to get desired privacy parameters under composition. When one cares about optimizing constants (which one does when dealing with actual implementations), $\varepsilon$ can be set more tightly by appealing directly to the composition theorem." That is to say, this value for epsilon does not represent anywhere near a calculated optimal value, but just a fairly good rough guide. »


Motivation of Adversarial Indistinguishability Experiment

My question is that in this game, it seems as if the adversary is choosing the two messages. Isn't this not simply an eavesdropping adversary, but rather one that can choose the messages being encrypted?

Yes, the adversary gets to choose the two plaintexts. There are a few ways to think about why this is appropriate.

It is very realistic to assume that the adversary has a-priori partial information (imagine an encrypted protocol session where we know that all protocols start with a "hello" message, like SMTP) or even partial control (imagine a website where you type a username and the website responds with a message "Hello, <username>") over what plaintext is getting encrypted.
In order to cover these realistic cases, it is necessary for the definition to allow the adversary to influence the choice of plaintexts. Once you include that into your definition, you end up converging on the standard chosen-plaintext-attack-style definition, since it is the most pessimistic and conceptually simplest way.

If the security definition didn't allow the adversary to influence the choice of plaintext, then every time you used an encryption scheme, you would have to think to yourself: am I absolutely sure that no external entity had any influence over what I'm encrypting? The standard definition gives you a guarantee that you can more-or-less encrypt whatever you want (there are weird edge cases like encrypting the key itself, etc).

Note that quantifying over all possible $m_0, m_1$ is equivalent to giving the adversary choice of $m_0, m_1$. This is because for every $m_0, m_1$, you can consider the adversary whose only strategy is to choose those $m_0, m_1$.

Having the game itself choose the two message $m_0,m_1$ is not equivalent. Such a definition would not rule out the existence of "bad" plaintexts. Consider a scheme that says: "to encrypt $m$, if $m$ is all zeroes then reveal the secret key, otherwise do a reasonable thing." This scheme would be secure under this weaker definition (since all-zeroes $m$ is rare, assuming the message space is large enough), but not the standard definition.

One reason to favor the "adversary chooses" style of definition is that we are already quantifying over all adversaries. We don't need another quantifier.

Actually in other settings (e.g., public-key encryption, poly-time adversaries), the "forall $m_0, m_1$" style is actually stronger! I think this is contrary to your suggestion. Imagine the public key contains $f(x)$ where $f$ is a one-way function. The encryption scheme says "if $m=x$ then give out the secret key, otherwise behave as normal." Quantifying over all $m_0, m_1$ would include quantifying over $m_0 = x$, and the scheme would be deemed insecure. But no poly-time adversary could actually choose $m_0 = x$ (that implies inverting the one-way function), so the modified scheme is equivalent to the original scheme under the "adversary chooses" style, so it would be considered secure.


Hashing high entropy key into AES format

I seem to recall that shared secret keys should be hashed before using as encryption keys (some brief discussion here).

If your key is already high-entropy, then hashing with SHA256 is fine. If you plan to generate several keys (ie, encryption and HMAC) from the original shared secret, then HKDF is a good option. This is a key-based KDF.

Scrypt and Argon2 are password-based KDFs and are not appropriate - they're designed for low-entropy input (such as passwords).


Why all multivariate schemes restrict themselves to polynomials of degree 2

In multivariate schemes, the secret key is a ``simple'' multivariate polynomial with some structure. The public key is obtained by wrapping the secret key in random linear maps. The resulting multivariate polynomial representation is very dense and unstructured to anyone without the secret key, meaning that any possible monomial would occur with high probability (depending on the field size). That means, storing $n$ such polynomials would require $O(n\binom{n}{d})\approx n^{d+1}$ coefficients, where $n$ is the number of variables / outputs and $d$ is the degree. The same value determines time complexity of encryption, as one has to go through all the coefficients in the public key to compute the ciphertext.
As you can see, degree 2 schemes already have cubic complexity in the number of variables.


What is the purpose of an Authentication Tag in AEAD encryption schemes?

What does this tag consist of ... is the tag itself human-readable data

It will most likely be a string of random looking bits. It is not intended or required for humans to participate in the verification process.

  what is its purpose

The algorithm uses it to verify whether or not the ciphertext and/or associated data have been modified.

If either the ciphertext or associated data has been modified, then the procedure that re-computes the validation tag on the receiving end will end up generating a different tag. The algorithm will check the re-computed tag against the tag that was bundled with the ciphertext and associated data (which collectively can be referred to as a "cryptogram").

If the tags don't match, that means some part of the ciphertext and/or associated data have been modified.

If the tags do match, that means that no part of the ciphertext and/or associated data have been modified*

* at least, there is a a high probability assuming that the keys have not been compromised and the authentication scheme is secure


How to use Libsodium encryption (in PHP) in the most secure possible way?

No need to implement padding, as it's already available. See the second example of the libsodium-PHP module.
Partially-known plaintext has no implication on security, especially in counter mode where the encryption of a block is independent from the previous blocks.
Creating a valid signature requires the secret key. Ed25519 has a 2^128 security target. The best attacks known actually cost more than 2^140 bit operations on average, and degrade quadratically in success probability as the number of bit operations drops.
Nonces can be public. Keeping them private doesn't significantly change the security level. However, nonces should never be used with different messages and the same key. See this page for a discussion on libsodium and nonces.
Yes. This doesn't make the cipher stronger, but mitigates the implications of a leaked secret key. If you are encrypting very large data streams, the secretstream API will automatically rotate the keys for you.
Salsa20 already has a huge key space. A salsa20-in-salsa20 cascade would have no benefits, and would be twice a slow.
Libsodium does its best to avoid side channels. Leaks are more likely to happen in the PHP code.


For the one time pad, your key must be

The same length as the message. Whatever your unit of measurement (bits, bytes, etc), they must be the same length.
The key must be perfectly random.
The key is only ever used once.


The question makes a formal confusion between the keyspace, which is a set; and the size of the keyspace, which is an integer. AES-256 has keyspace equal to the set of 256-bit bitrings, noted $\{0,1\}^{256}$, which has size $2^{256}$.

Often, equivalent keys are counted only once. That's why DES is considered to have a keyspace of size $2^{56}$ even though its key is 8 octets (the low order bit of each octet is either ignored, or checked to be the complement of the XOR of the other 7). Similarly, TEA can be considered to have a keyspace of size $2^{126}$.

For symmetric algorithms, the size of the keyspace is of direct interest, since it determines the resistance to brute force key search, which ideally is the best attack.

For asymmetric algorithms like RSA, size of the keyspace is no longer directly related to security, because the public key is assumed avaialble to attackers. For this reason, size of the keyspace is not much studied, and for RSA there is not even consensus about exactly what that is. Rules vary for what a valid $N$ is, much more for a valid $e$. And it is unclear if we count (non-equivalent) pairs $(N,e)$, or just the possible $N$. We'll do the later, which alleviates the need to define a valid $e$, and makes a lot of sense since knowing a private key for $(N,e)$ allows to find a private key for any given $(N,e')$.

One possible definition of a valid 4096-bit RSA modulus is $N=p\,q$ with $p$ and $q$ prime, and $2^{(4096-1)/2}<p<q<2^{4096/2}$ (that's about what's FIPS 186-4 asks). By the prime number theorem, about one out of $\log(2^{2047.75})$ integers in the interval $[2^{2047.5},2^{2048}]$ are prime, giving about $u=(2^{2048}-2^{2047.5})/\log(2^{2047.75})$ choices for $p$. That gives roughly $u^2/2\approx2^{4070.5}$ choices for $N$. That's one possible estimate of the size of the keyspace for 4096-bit RSA. Which, again, has just nothing to do with its security.


22 is the hex encoding of a binary polynomial $f = x^5 + x$ that is used to represent the element of the AES finite field (the field is defined as $F_{2^8} = GF(2)[x] / p(x)$) where $p(x) = x^8+x^4+x^3+x+1$ is the reduction polynomial.

Now, we need to find the multiplicative inverse of $f(x)$, i.e. another polynomial $g(x)$ such that
$$
f(x)\cdot g(x) \equiv 1 \pmod{p(x)}
$$
We can do this either by using extended Euclid algorithm for polynomials or using the fact that $f^{-1}(x) = f^{254}(x)$ because of the Little Fermat's Theorem.

Using a computational algebra package like e.g. GP/PARI we can compute

p = Mod(1,2)*x^8 + Mod(1,2)*x^4 + Mod(1,2)*x^3 + Mod(1,2)*x + Mod(1,2)
f = Mod(1,2)*x^5 + Mod(1,2)*x
g = Mod(f,p)^-1

and we get the result

Mod(Mod(1, 2)*x^6 + Mod(1, 2)*x^4 + Mod(1, 2)*x^3 + Mod(1, 2)*x, Mod(1, 2)*x^8 + Mod(1, 2)*x^4 + Mod(1, 2)*x^3 + Mod(1, 2)*x + Mod(1, 2))

so we get the reduced polynomial $x^6 + x^4 + x^3 + x$ and this encodes as 5A, the table entry that corresponds to 22.

The only element that does not have its multiplicative inverse is 00, so by convention we define that 00 is mapped to 00 again.


Are there any security issues when replacing the SHA-256 initialisation values?

Random IVs are fairly clearly ok. NIST secure hash standard defines SHA-512/t with arbitrary t and different IV values that are themselves outputs of SHA2, and Merkle-Damgård hashes basically do the same internally when you have a multi block massage. There should be no reason you could not do the same with SHA-256 or with another PRNG generating the IV values.

Nonrandom IVs are theoretically a different matter. Current (partial) attacks on SHA2 work on the compression function and find collisions for any predetermined IV/chaining value. However, at least in principle some values could be easier to attack. That would not break the whole hash as long as the number of weak IVs is negligible.
(As in the case of the Malicious SHA1 linked in the comment by CodesInChaos, but with round constants instead of IV.)


What are the possible applications of fully homomorphic RSA algorithm?

The question's observation is perfectly right: RSA as practiced uses padding or/and is used to encipher a symmetric key, which makes it not homomorphic at all.

Further, textbook RSA (without padding) is homomorphic, but is deterministic (the same plaintext always produces the same cypertext). This is most often a devastating weakness, because it lets anyone (with the public key) test an hypothesis on the plaintext.

For this reason, use of RSA as an homomorphic asymmetric encryption algorithm is questionable, and accordingly is now almost entirely absent in cryptographic publications with a peer-review system that I trust.

Update: A related question asks if it is possible to devise safe RSA padding while preserving homomorphy; I tentatively answered in the affirmative, but that does not seem practical at all.

I do not know any way to make RSA fully homomorphic, in the usual sense that it allows both addition and multiplication of plaintext from ciphertext.

The Pailler cryptosystem is a randomized asymmetric encryption algorithm (safe from plaintext guessing); is homomorphic (for addition of plaintext, rather than multiplication for RSA); is based on the same mathematical problem as RSA; and is not much more difficult to grasp. It might be a proper substitute for RSA when a homomorphic asymmetric encryption algorithm is thought. Also, there seems to be more applications of additive homomorphic encryption than of the multiplicative breed.

Among applications of the Pailler cryptosystem (and homomorphic encryption in general) are some electronic voting protocols (an interesting theoretical subject; still, count me among the strong opponents of their actual use for political elections).


How to design a practical and secure MAC scheme?

There are many ways to authenticate the contents of the disk.  The way you have described is reasonable, if you have a way to store the global sequence number in an authentic way (so it cannot be tampered with).

Another general approach is to look at the data structure that is maintained by the UBI to map from logical block numbers LEV($v,l$) to physical block numbers PEB($p$).  Then, add a MAC on all entries of that data structure, and when you read the data structure, verify the MAC.

Also it might help to use tweakable encryption to encrypt each block, with the tweak set based upon the block numbers.

Broader comment: I think you should start by reading about full disk encryption (FDE) in general.  I don't see anything here that is terribly different from the issues facing FDE on magnetic hard disks.  Here are some good starting references:

Disk encryption theory, particularly its discussion of tweakable encryption.
IEEE P1619/D16 - Standard for Cryptographic Protection of Data on
Block-Oriented Storage Devices
And, these three research papers on disk encryption
Do Flash memory (SSD) architecture impacts encryption techniques?

Do note that many full disk encryption schemes provide only confidentiality, not authenticity, so you'll need to go beyond what those schemes offer.

P.S. One last comment: you are forming the input to your MAC by concatenation.  This is fine if all of the fields are fixed-length values, but if they are variable-length, you may be at risk of a concatenation attack.


Usage and limitations of sponge functions for PRNG

I'd say the comparison table is not a fair one, as it compares the Infinite Noise generator's throughput when feeding bits into a CSPRNG (Keccak) running on the host workstation and then running that CSPRNG as fast as the workstation allows. Other devices in the table achieve ~10 Mbit/sec speeds, but all of those devices in the table which had enough design documentation published on the web seem to advertise their throughput based on whitened output, but not on output expanded via a seeded CSPRNG on the host.

All of this is “much ado about nothing” however. A single 256-bit seed and a fast-key-erasure CSPRNG is all one should ever want in the real world. Don't create a persistent channel for attacker-controlled input. Or just use /dev/urandom.


Diffie Hellman Key Exchange (Finding # of bits/digits of secret key)

Assuming that $g^A \bmod p$  and $g^B \bmod p$ are 100 digits long, would Charlie be able to determine a bound (in terms of digits or bits) for the respective secret key $A$ and $B$ ?

100 digits is approximately 332 bits; if $p$ is 332 bits long, then it is known to be feasible to apply the Number Field Sieve algorithm to recover the values $A$ and/or $B$; that certainly would give him the bound.

For reference, Antoine Joux and Reynald Lercier computed the discrete log of a 431 bit (130 digit) base in three weeks.


What is the difference between substitution cipher and block cipher?

I feel this description is talking about the problem of ECB mode in block cipher.
So my understanding so far is that substitution cipher can be considered as a block cipher. But I'm wondering if a block cipher is always substitution cipher.

(1) let us compare a block cipher with ECB mode to a substitution cipher.
With ECB Mode and a given key, a block cipher can be seen as a substitution cipher which maps one block to another block. For example, AES, twofish, or serpent has a block size of 128 bits; you may say, "one 128-bit block is substituted to another 128-bit block".
(Note: this is just a simple comparison. If a block cipher has a "state", the same input blocks might get different output blocks. In this case, the block cipher might be compared to Vigenère cipher.)
While a Caesar Cipher maps one letter to another letter. That is from a 5-bit to a 5-bit, or at most a byte to a byte. (From this point, you could be right to say "substitution cipher can be considered as a block cipher"; but the block size is quite small.)
So, I might say a Caesar Cipher is a special block cipher which has a small block size; or, on the other hand, a 128-bit block cipher (with ECB mode) is a "monster Caesar Cipher with 2128 letters".
(2) a block cipher with certain mode (except ECB)
This is a fun part. From my point of view, if you want, you can actually create a Caesar Cipher with CBC, PCBC, OFB, CFB, CTR modes by replacing the IV or counter with a letter.

What is the difference between them in general.

(3) difference
They are quite different in practice.
But the main one is size: block size, key size, IV size, and counter size. (The last two is really the block size for different uses).
If a monster Caesar Cipher has 2128 letters and has CBC, PCBC, OFB, CFB, CTR modes, it might be as strong as a 128-bit block cipher.


How might one create a system of election by lot (sortition) that is both secure and verifiable?

I'm going to try to answer a more modest version of your question.

Imagine that the Dishonest Society, a small club of 100 members, needs to take care of an Arduous Task that will require 5 people to complete.  The members are lazy and so there are no volunteers.  The members also don't trust each other very much, so they want to use a _sortition_ protocol to elect a random committee to do the Arduous Task.

Let's assume for the following that the members have all come to agreement on the membership list of their club:

$$
M = \{ M_1, M_2, \dots, M_{99}, M_{100} \}
$$

A physical protocol

The intuition is that the members will collectively generate a random
number, and then each member will try to guess the number.  We'll rank
the members based on how close their guess was to the random number, and
select the 5 lowest-ranked members for the committee.

First we have to decide "how big" our numbers will be.  We are going to
have 100 guesses, so let's pick the range 0 through 8190, which should be enough. All of our calculations will be done modulo 8191.  Because 8191 is $2^{13}-1$, a Mersenne prime, we are actually working in the finite field $\mathbb{F}_{8191}$ -- it will come in handy later when we look at the cryptographic protocol.

Now obviously we need the members to commit to their guesses before we generate the random number, so each member $M_i$ secretly makes a guess $g_i \in \mathbb{F}_{8191}$.  We don't trust the members to be honest,
so we'll ask them to put their guess inside a sealed envelope and write
their name $<M_i>$ on the outside.  Once all the members have prepared
their guesses, we put all of the envelopes in a box and lock it.  If a
member tries to cheat by writing down a nonsense guess, we'll find out
later when opening the envelopes.  (And if a member tries to put someone
else's name on his envelope, we assume someone will catch him when he
attempts to put it in the box.)

Next the members need to generate a random number.  $\mathbb{F}_{8191}$
is fairly large, so dice would be impractical.  Instead we will ask each
member $M_i$ to pick a random number $r_i \in \mathbb{F}_{8191}$.  Then
we have them write $r_i$ on a slip of paper and toss it into a hat.  Once
all members have put their random numbers in the hat, we can sum them up
to get a truly random number that no member can influence:

$$
r = \sum_{i=1}^{100} r_i \pmod {8191}
$$

It is easy to see that as long as at least one member was honest and selected their $r_i$ at random then the result $r$ is also random.  It
is also easy to see that none of the members knew anything about what
$r$ would be at the time that they made their guesses $g_i$.  And they
can't go back and change their guess, because it's in a sealed envelope
inside a locked box.

Now we can open the box with the guesses and calculate each member's
ranking based on how close their guess $g_i$ was to the chosen number $r$:

$$
rank(M_i) = r - g_i \pmod {8191}
$$

The committee for the Arduous Task can now be formed by choosing the 5 lowest-ranked members.  Ties can be broken by a roll of the dice.

A cryptographic protocol

Assuming that all of the players can communicate with each other over a secure authenticated channels (standard in the multiparty computation literature) we can transform this physical voting protocol into a cryptographic protocol:

$M_i$ makes a random guess $g_i \in \mathbb{F}_{8191}$.
$M_i$ broadcasts a commitment $Com(g_i)$.
Wait until every $M_i$ has broadcast their commitment.
$M_i$ picks a random number $r_i \in \mathbb{F}_{8191}$.
$M_i$ sends each $M_j$ an additive share $[r_i]_j$ such that $\sum_{j=1}^{100} [r_i]_j = r_i$.
$M_i$ broadcasts $r'_i = \sum_{j=1}^{100} [r_j]_i$ and $g_i = Open(g_i)$.
Each player can now calculate the ranking of every other player as:

$$
rank(M_i) = g_i - \sum_{i=1}^{100} r'_i
$$

We use a commitment scheme to force each player to select their $g_i$ before they have received any information about $r$.  Because the
commitment hides $g_i$ until the openings are broadcast, the players
must select their $r_i$ before they have any information about the
other players' choices of $g_i$.

We use a secret sharing scheme so that no player (or coalition of players) has enough information to determine the $r_i$ of any other player, and so
this allows all of the players to send their $[r_i]_j$ shares to each
other simultaneously.

In the real world we'd want to also use a linear message authentication
code to verify each of the $[r_i]_j$ shares;  otherwise a dishonest
player could lie about $r'_i$ in step 6.  We'd also want to consider a
dishonest player who aborts in step 6 (without sending his $r'_i$ or
his $Open(g_i)$) after learning enough information to determine that he would be one of the "losers".

No fancy public key cryptography required!  :)


Major Block Ciphers between DES and AES competitions

IDEA and CAST-128 (aka CAST5) first come to my mind as widely deployed/used ciphers. Blowfish and TEA are next. The first two (and to some degree the third) got support in PGP early on.

Update per comment: RC2, RC5, and GOST 28147-89 (in the Eastern block) also have been widely used.

All 7 are 64-bit block ciphers; that's typical of the era, and made these block ciphers a painless substitute for DES and 3DES (the dominant ciphers). They stood the test of time quite well, with no practical attack better than brute force by more than very few bits (except for GHOST, but when used with its full 256-bit key it remains safe enough). While TEA is involved in a notorious incident where a game console misused it for hashing, that's hardly a problem attributable to TEA itself.

Note: I'd have included RC4 if is was a block cipher; that used to be widespread in quite a few commercial applications.


Any group operation $\odot$ on the set $\{0,1\}^{256}$ equally matches the objective of making the hash round function $F(m,x)=E(m,x)\odot x$ one-way under the assumption that $x\mapsto E(m,x)$ is a random permutation keyed by $m$. Thus under this model, XOR or 32-bit addition does not matter.

  would xor'ing instead of adding be more secure, or not?

For the reason above: That's moot. But if we need to choose, rather not. Argument: addition makes the natural expression of a hash round function as a number of elementary logic gates (or satisfiability equations) slightly more complex than XOR due to the  8×31 carry terms. And absent any other good criteria, it's reasonable to bet that more complex is more secure, because that's demonstrably true for a random arrangement of gates (or satisfiability equations)


How do I construct and use the Okamoto protocol simulator?

There is "zero knowledge simulator" and "honest verifier zero knowledge simulator". General idea is reversing the order of variables picked at random or cauluated. Namely, pick the simulated challenge and response first, and calculate the first message $a$. For HVZK, just pick a challenge and a response at random, calculate proper first message using verification equation. For ZK, one should get a challenge by querying the real Verifier. This means running a session with Verifier and sending some random first message. Please note I did omit minor details doable as a homework.


How many field operations are needed when you compute kG in elliptic curves with a multiple additions or the double-ans-add-algorithm?

Given two points $P_1 = (x_1,y_1)$ and $P_2 = (x_2, y_2)$ on an elliptic curve $y^2 = x^3 + ax +b$, the sum $P_3$ of $P_1$ and $P_2$ is $P_3 = P_1 + P_2 = (x_3,y_3)$ where $x_3 = \lambda^2 - x_1 - x_2$ and $y_3 = y_1 + \lambda(x_3 - x_1)$ where $\lambda = (y_1 - y_2)/(x_1 - x_2)$ if $P_1 \neq  P_2$ and $\lambda = (3x_1^2 + a)/(2y_1)$ if $P_1 = P_2$.  The case $P_1 \neq P_2$ is called point addition and the case $P_1 = P_2$ is called point doubling.

Let $M, A, S, D$ denote the operation of multiplication, addition, subtraction, and division in the underlying field.  Then we see that with the previous formulas,

the evaluation of $x_3$ requires $1M + 2S$;
the evaluation of $y_3$ requires $1M + 1A + 1S$;
the evaluation of $\lambda$ requires $2S + 1D$ if $P_1 \neq P_2$ and $1M + 4A + 1D$ if $P_1 = P_2$ [I assume here that $3x_1^2$ is evaluated as $x_1^2 + x_1^2 + x_1^2$ ($2A$) and $2y_1$ as $2y_1 = y_1+y_1$ ($2A$)].

Hence, we obtain that

a point addition requires $2M + 1A + 5S + 1D$;
a point doubling requires $3M + 5A + 3S + 1D$.

Back to your question now,

the evaluation of $kG$ requires $k-1$ point additions using the first method, that is, $2(k-1)M + (k-1)A + 5(k-1)S + (k-1)D$;
letting $\ell$ the binary length of $k$ (i.e., $\ell = \lfloor\log_2 k\rfloor + 1$) and $h$ the Hamming weight of $k$ (i.e., the number of bits equal to $1$ in the binary representation of $k$), the evaluation of $kG$ requires $\ell$ point doublings and $h$ point additions using the double-and-add method, that is, $(3\ell+2h)M + (5\ell+h)A + (3\ell+5h)S + (\ell+h)D$.  On average, for a random $\ell$-bit integer $k$, we have $h = \ell/2$; in which case, we get $4\ell M + 5.5\ell A + 5.5\ell S + 1.5\ell D$.

It is worth noting that the first method is completely impractical for cryptographic applications since $\ell$ is typically $256$ and thus $k \approx 2^{256}$.


Is this a typo/error in the Galois/Counter mode specification or have I misunderstood?

Examining the document, it seems that you are correct on both equations. Thus

$$
C_i ~~\textrm{should be}~~C_{i-m},
$$

and

$$
C_m^* ~~\textrm{should be }C_n^*.
$$


Will hashing over and over eventually give the same hash?

In general, collisions in a hash function are a bad thing: if you have different $M_1$ and $M_2$ for which $hash(M_1)=hash(M_2)$, the situation will require special handling.

In cryptography, hash functions can be seen as "summary" functions, that reduce a message of arbitrary length to messages of fixed length. Since the message space (all the possible messages) is usually way larger than the hash space (all the possible hashes), you are bound to have collisions.

There are several ways for an attacker to violate a hash function, but for this scenario, let us take a random value $H_1$ in the hash space. It could be a hashed password you retrieved from a server, for instance. What matters is that it is fixed.

In most cases, like the hashed password, the attacker does not need to know the original password. He only needs to know a random password $P$ such that $hash(P)=H_1$. That is definitely undesirable, and that is why cryptographic hashing functions are designed to be collision resistant. That means that, for an attacker with the most efficient polynomial algorithm to attack the hash function, it would take ages (a longer time than the time of existence of humanity) to find a collision.

All that said, what you want to find is some $M$ for which $H(H(H(...H(m)...)))$ some amount of times, gives again $H(M)$. That is mathematically possible (and certain to obtain), but your lineage will probably not live to see it.

As a final note: the password example is clearly flawed, since there are more specific attacks against it (like dictionary attacks and rainbow tables), but it is enough for the sake of your scenario.


Can you give me an example of any PKC encrytion algorithm with coins?

All textbook PKC systems are never applied as they are described. Take e.g: RSA.
There is a random padding technique that plays the role of the coins. The coins make the scheme probabilistic. For the same reason a block cipher which is instatiated as a pseudorandom permutations takes as input an instatiation vector IV. OAEP is a commonly used random encoding scheme before applying RSA on your data.


Can Microsoft's SIDH (Supersingular Isogeny) keypairs be reused for encryption? If not, why?

Is SIDH actually insecure when keys are reused?
  If so, why? How can SIDH actually be broken? Can you demonstrate an attack?

Yes it is. There is a well known adaptative attack, described here https://eprint.iacr.org/2016/859

  Is SIKE actually secure even when keys are reused?

Yes it is. There is a security proof, assuming the number-theoretic hardness assumptions SIDH is based upon are true.

  What prevents an attacker from encrypting many messages with a SIDH public key and breaking it that way?

That's the definition of CPA security. SIDH is proven CPA secure.

The CCA attack works by generating faulty ciphertexts (not plaintexts) and sending them to a decryption oracle. The attacker learns something on the key by observing whether decryption succeeds or not.

  What's the difference between the two that makes it so one can securely use reused keypairs and one can't?

SIKE uses a generic transformation meant to turn a CPA secure protocol into a  CCA secure one. Essentially, it amounts to recomputing Bob's public data to check that he did not cheat in computing the ciphertext. This thwarts the attack, and indeed also any other potential CCA attack.


The GCD strikes back to RSA in 2019 - Good randomness is the only solution?

The solution is simply to make sure that you have good randomness. At the size of the numbers we are considering, the probability of a repeat when using good randomness is extremely small. To make this clear, there are well over $2^{1000}$ prime numbers of length 1024. The probability of a repeat at any reasonable number of primes chosen, when using true randomness, is so small that it's not worth considering. To be more exact, if we generate $t = 2^{50}$ random primes of length 1024 (this is 1,000 trillion), then the probability of a repetition is smaller than $\frac{t^2}{2^{1000}} = 2^{-900}$.

True randomness isn't that helpful, so the NIST recommendation is to take a random seed for your PRG at double the length of the bit security you are looking for. So, assume RSA-2048 is 128-bit security (it's actually a bit lower by estimates, but let's ignore that detail for here). Then, you should be using a 256-bit truly random seed, and using that in a PRG based on something like AES-256. In this case, the chance of getting a repetition is still essentially 0, even if thousands of trillions of keys are generated. Again, to be more exact, the probability would be upper bound by $\frac{t^2}{2^{256}} = \frac{2^{100}}{2^{256}} = 2^{-156}$.

The main challenge is how to make sure that good randomness is used. It's much cheaper and easier to generate identical devices on a factory line that have nothing unique. In this case, each device needs to generate its keys by itself later, and the easiest thing again is for it to use its own internal state. This doesn't work. The best option is to write a fresh random 256-bit seed in every device during production (in a factory, it's not a problem at all to have a machine with a true random generator that can generate the seeds that are written to the devices). If this isn't done, then there needs to be some way of securely delivering a good seed to the device. It's possible to "add in" any entropy that can be generated locally as well, but this cannot be the primary source.


Is it possible to determine the number of characters used for a password used to encrypt a file with AES 128?

No. Password cannot be used to encrypt anything directly unless it is exactly of a certain size, and then it will be likely weak. Encryption passwords are hashed, with a slow hash hopefully, and the output is used as key.


Best practice to create certificate by CA

Practice 1 is superior without a doubt.

First and foremost the obvious problem:
With practice 2 you need a channel to transport a piece of data confidential and authenticated which is strictly harder than just transport information (the CSR) authenticated for practice 1.

Now there are a couple of other reasons why in practice the first practice is used:

In actual CAs, the private keys are stored inside of HSMs. If you were to transport a key from the root CA HSM to the Intermediate CA HSM these two would have to be linked in some form / initialized the same way which is unneccessary procedure and unneccessary risk, after all if someone manages to convince the root-HSM to give you a wrapped key of the root key, now the attacker can use this key on the fortified root-HSM or he could use it on the less-fortified intermediate-HSM. Note though that actual CAs most likely do operate multiple HSMs that can unwrap the root keys, but they are all off-line, in-vaults and highly fortified as opposed to the intermediate HSMs which sometimes even operate fully automatically with an internet-facing API / service.
At other times the intermediate CA may not be operated by the same company as the root CA. In these situations I highly doubt that the client (the intermediate CA) would want to trust the root CA's security measures on key generation and wrapping and secure transport methods given that they might as well just generate a key on their own and use a CSR.
It introduces unneccesary protocols. Consider how end-users get their certificates: They generate a key themselves, send a CSR and get a certificate. No sane CA would ever propose to generate the keypair for the client and have them download it. The same applies to this CA-CA communication: The protocol to issue certificates works just fine, so why make it harder?


how to compute the correlation between two binary vectors?

The math

The correlation coefficient between an array of boolean vectors is a value between 0 and 1 defined by the following equations, covariance and standard deviation:

$\operatorname{cov} (X,Y)=\frac{1}{n}\sum_{i=1}^n (x_i-\overline{X})(y_i-\overline{Y})$

$\sigma_X=\sqrt{\frac{1}{n}\sum_{i=1}^n (x_i-\overline{X})^2}$

$\sigma_Y=\sqrt{\frac{1}{n}\sum_{i=1}^n (y_i-\overline{Y})^2}$

Where $\overline{X}$ is the average value of a set, and $X$ is the set of $x$ values, which would be the first array in your variables [0,1,0,1] , and $Y$ is the set of $y$ values, the second array [0,0,1,1]. Note the array indexing is 1-4 for the equations, but will not be so in computer code.

The correlation coefficient is the final equation:

$\rho_{X,Y}= \left|\frac{\operatorname{cov}(X,Y)}{\sigma_X \sigma_Y}\right|$

$\rho_{X,Y}= \left|\frac{\sum_{i=1}^n (x_i-\overline{X})(y_i-\overline{Y})}{\sqrt{\sum_{i=1}^n (x_i-\overline{X})^2} \ \cdot \ \sqrt{\sum_{i=1}^n (y_i-\overline{Y})^2}}\right|$

In the scenario where $\sigma_X$ and $\sigma_Y$ are both 0, the vectors are most likely completely correlated, and a different comparison must be made. If one of them is 0, the results are probably not correlated. You will probably not run into these situations if you are analyzing an s-box for bit independence.

Your example

Because your dataset is small, it is easy to use as an example, but is still a bad example, because the correlation coefficient is 0:

The standard dev of your X and Y sets is both 0.5, but the covariance is 0:

$0 = \left|\frac{0}{0.5 * 0.5}\right|$

Now, if you change your X,Y to [0,1,0,1],[1,0,1,0], you can see that they are completely correlated [y = not(x)], and the math agrees, as the covariance calculation is -0.25:

$1 = \left|\frac{-0.25}{0.5 * 0.5}\right|$

Optimization and code

You may notice that standard deviation looks like the square root of covariance between the same set, and for this calculation it is. You may also notice you cancel out the 1/N in the final equation. The intermediate calculations of average values and subtractions are also the same, so you can combine them all into a single calculation. Careful optimization will also help compensate for any floating point rounding errors.

Optimized pseudocode for the final equation on arrays of X and Y would look something like this:

mean_X = ArithMean(X)
mean_Y = ArithMean(Y)

For i = 1 to N
    val_x = X(i) - mean_X
    val_y = Y(i) - mean_Y
    deltasum_c = deltasum_c + (val_x * val_y)
    deltasum_x = deltasum_x + (val_x * val_x)
    deltasum_y = deltasum_y + (val_y * val_y)
Next i

CoVariance = deltasum_c
StdDeviation_xy = Sqrt(deltasum_x * deltasum_y)

If StdDeviation_xy <> 0 Then COR = Abs(CoVariance / StdDeviation_xy)
Elseif deltasum_x = deltasum_y Then COR = 1
Else COR = 0


Can ECDSA key pairs be added up or multiplied?

Is it possible to add up these key pairs?

Yes. If $y_1=x_1\times G$ and $y_2=x_2\times G$, then
$$y_1+y_2=y_1+(x_2\times G)=(x_1+x_2)\times G$$
and that's a public key matching private key $x=x_1+x_2$.

  Let's say (before i have $ x_1 $) I encrypt a text with $y$. And let's say I get $x_1$ at a later date. Can I decrypt my text using $x$ (means by adding up the private keys)?

Yes, that follows from the above.

Note: there's no multiplication of key pairs as in the title, in the sense of an operation on keys yielding a new key (unless we note the group operation on the Elliptic Curve multiplicatively, which the question does not). With a group operation noted additively (as the question does), the only well-defined operation between public keys / group elements is addition, and we can only multiply these by a scalar (integer).


How safe is a prime with $P=2 \cdot Q \cdot R \cdot S \cdot t+1$ for discrete logarithm? How to enhance/compare?

It does work with Silver-Pohlig-Hellman algorithm

As theREALyumdub pointed out in comments that Silver-Pohlig-Hellman might be an option I did some test and it did work. Thanks for that hint.

In case $t=1$ we get the results $a,b,c$ right out of the algorithm. For other $t$ the results $a,b,c$ aren't correct. Some extra work need to be done there. It does work if you multiply value $v$ with the inverse of used $T$ first. However this $T$ is unknown in use case. Chances are high there is a better way but the naive way is good enough for my case. As I wrote in post $t<1000$ so we could just multiply with a random number and get the correct result with chance $\frac{1}{t}$.

So it is not harder than:
finding d for a given $v'$

$v'\equiv g^d \bmod P$, with $g$ generator of a subgroup with size $G=\max(Q,R,S)$

Remaining questions:

Does it make a difference if you solving only for a subgroup? Or is equation above, as hard as
$v'\equiv g^d \bmod G$

Is there any way to speed up finding the correct $T$ factor? While a
constant factor of 1000 is asymptotically equal but in real world it can make a huge difference.

However this transition used in Silver-Pohlig-Hellman algorithm destroys the idea of hiding the dimensions in one number. Three separate equations with big prime factors would do the same job.

Although the question is not fully answered it's enough for me. The remaining questions above are not specific to this case. I might create some new threads about those. If so, I will link them here.

$v = T\cdot g^a\mod P$
proof if same factor $T$ was used -->  $v_{T_1}^{QRS} \equiv v_{T_2}^{QRS} \mod P$  iff same group

links show easy to do -> this kind of prime and usage has not benefits :(


Use of cryptographic hash for computing previous block hashes in blockchains

Collision resistance and pre-image resistance, both first and second, are important for Bitcoin. This answer may not apply to all blockchain instances.

Collision resistance is important for the property of distibuted consensus.

  In bitcoin mining, the inputs for the function are all of the most recent, not-yet-confirmed transactions (along with some additional inputs relating to the timestamp and a reference to the previous block).

Think about what would happen if there were more than one input that could hash to the same value.

Preimage resistance is important to the mining process, and by extension to the strength of the consensus which is mined into the blockchain.

Each bitcoin block contains a nonce. The job of miners is to find a nonce value such that the resulting hash of the block contains a certain number of leading zeros. The number of zeroes corresponds to the difficulty of mining the blockchain. Without pre-image resistance, and depending upon the difficulty of finding a pre-image, it could be possible for miners to find a nonce value with less difficulty than by exhaustively enumerating the nonce field. If it were very easy to mine the blockchain, in particular if one group had a significant advantage in doing so, then they could launch an attack in which they control the majority of the hashing power of the bitcoin network. .

Finally, second pre-image resistance is necessary for the same reason as collision resistance. If a second input could be found which matched one of the block hash values then there would be uncertainty about the canonical state of the blockchain.


Why are singular "elliptic" curves bad for crypto?

When a Weierstraß equation $y^2 = x^3 + Ax + B$ over $\mathbf F_p$ has a null discriminant, then it does not define an elliptic curve: it is a singular curve. In that case, it means the polynomial $x^3 + Ax + B$ has a double or triple root $x_0$ and the point $(x_0, 0)$ is a singular point. All the non-singular points still define a group law with the regular construction as in an elliptic curve.

With a change of variable, you can always come back to these two cases:

$y^2 = x^3$, then there are exactly $p$ non-singular points and there is an efficient map to the additive group of $\mathbf F_p$ where the discrete logarithm is trivial.
$y^2 = x^2(x-1)$, then there are $p+1$ or $p-1$ points and there is an efficient map to the multiplicative group of $\mathbf F_{p^2}^*$ (which has $p^2 - 1 = (p-1)(p+1)$ elements) where the discrete logarithm is way easier to compute (but not as easy as the previous case).

In both cases it is very bad for crypto.


Software implementation of a commutative cipher?

To clarify a little, you need "encryption" that is commutative, deterministic (otherwise the commutative ciphertexts won't necessarily match even if the plaintexts do), and has a private encryption function (otherwise given that it is deterministic and the plaintext space is small, an exhaustive search would be possible). For example, Elgamal is commutative but it is also randomized and public key. Encryption is in quotes because, since you never decrypt, you actually just need a trapdoor function with those properties.

Pohlig-Hellman and SRA are suitable.

As far as implementations go, I do not know of any. However Pohlig-Hellman would be easy to implement with just a number theory library (it is just a single modular exponentiation -- you don't need to decrypt in your application). If you have a DSA library that has a function to generate a public key from a secret key, you can use that as the encryption function.

Similarly, SRA is just RSA with two key pairs. If you could call the key generate function of an RSA implementation is such a way as to get $e,d$ if you supply $p,q$, then that would work.

Both of these ciphers are old and were developed before certain attacks were known. For Pohlig-Hellman, you should work in a multiplicative subgroup and this requires encoding the plaintext. SRA could leak the Jacobi symbol of the plaintext like RSA (I think even if $e$ is not known?).

Finally, the application you are implementing is called "private set intersection." There are lots and lots of papers on how to do it, and potentially some implementations of the whole protocol. There are some issues with the way you are implementing it assuming that one of the parties is malicious.

If both parties are honest (only submit true values) and fair (one party learns the result before the other), it seems ok. But there are all sorts of attacks otherwise that could be resolved by using a private set intersection protocol designed for exactly this purpose.


Well, to explain that, I have to touch lightly on what a group is, and how both operations involve a group.

A group [1] is a set of values, along with an operation (which I'll denote as $\odot$); with this operation, we take two values, smash them together, and generate a third one [2].  One example of a group are the numbers, along with the operation of addition $+$; we can take the values 1 and 3, and smash them together $1+3$ to get the value 4.

Now, one thing we can ask is 'if we start with a value $a$, how many $a$s do we need to smash together before we get the value we're looking for $b$'.  That is, if we compute:

$$\underbrace{a \odot a \odot a \odot … \odot a}_{\text{x times}}$$

how large does $x$ need to be before we get the value $b$?

This is called the discrete log problem.

With some groups, this is an easy problem.  For example, in the numbers and addition group I mentioned earlier, if we start with $7$, and ask "how many 7's do we need to add together before we get to 63, it's easy to see that the answer is 9.

Now, it turns out that both problems you mentioned are like this.

For the problem $a^x = b$, the $\odot$ operation is the act of taking two values, multiplying them together, and then taking the result modulo p (typically a large prime).  Because $a^x = \underbrace{a \times a \times a \times … \times a}_{\text{x times}}$, this is precisely the same form as the generic problem (and in fact is why we call the generic problem the 'discrete log' problem)

For Elliptic Curves and the problem $xP = Q$, the $\odot$ operation is taking two values where are 'elliptic curve points' [3], and performing an 'elliptic curve addition' to generate a third point.  That is, the problem is finding $x$ where $xP = \underbrace{P + P + P + … + P}_{\text{x times}}$ is the elliptic curve point $Q$; hence it is also in that same form.

Now, if the two problems are the same at the abstract level, why do we write them differently?  Well, it just comes down to notation.  For modular multiplication, we always write the operation as if it were multiplication, and so the obvious way to write a large number of multiplications is to write it as an exponentiation:

$$\underbrace{a \times a \times a \times … \times a}_{\text{x times}} = a^x$$

For Elliptic curves, we typically write the operation as if it were addition, and the obvious way to write a large number of additions is to write it as if we were doing a multiplication:

$$\underbrace{P + P + P + … + P}_{\text{x times}} = xP$$

This difference is just in the way we generally talk about these two grous - it has no impact on what we do with them.

[1]: That's a term that mathematicians use; don't worry, I would use that much more arcane terminology

[2]: Actually, there are a bunch of other things we require of a group - I will not mention them here.

[3]: I won't go into detail here about what an elliptic curve point is.


Can the input to a one way function be pseudorandom?

The definition of a one=way function, according to Wikipedia, is:

A function $f : \{0,1\}^* \to \{0,1\}^*$ is one-way if $f$ can be computed by a polynomial time algorithm, but any polynomial time randomized algorithm $F$ that attempts to compute a pseudo-inverse for $f$ succeeds with negligible probability. That is, for all randomized algorithms $F$ , all positive integers $c$ and all sufficiently large $n = \mathrm{length}(x)$ ,
$${\displaystyle \Pr[f(F(f(x)))=f(x)]<n^{-c},}$$
where the probability is over the choice of $x$ from the discrete uniform distribution on $\{0,1\}^n$, and the randomness of $F$.

The definition doesn't say anything about pseudorandom choices of $x$, and this means that we do not have to contemplate such choices when assessing whether $f$ is one-way.  So your question if $f$ would "still be a one-way function" if $x$ is drawn pseudorandomly has a trivial "yes" answer.

The question I think you're actually interested in is this: if $f$ is a one-way function but $x$ in the definition above is drawn from some pseudorandom distribution $D$ over $\{0,1\}^n$, could there exist a polynomial time randomized algorithm $F$ that finds a pseudo-inverse of $f(x)$ with non-negligible probability?  Well, if there is such an $F$, then we could use it to construct a distinguisher for $D$:

Accept an input $x$;
Output $1$ if $f(F(f(x))) = f(x)$, $0$ otherwise.

Now:

Since we assumed that $F$ succeeds with non-negligible probability for $x$ drawn from $D$, in that case the distinguisher will output $1$ with non-negligible probability;
Since we assumed that $f$ is one way, this means when $x$ is random $F$ outputs $1$ with negligible probability;
The difference between a negligible probability and a non-negligible one is non-negligible.

But that contradicts our assumption that $D$ is pseudorandom, so there cannot be such an $F$. In plainer English: feeding pseudorandom inputs to a one-way function is not significantly likelier in practice to pick "bad" (easy to invert) inputs than choosing inputs at random.


Can the access policies defined using different access structures (Monotone Span Program and Access Trees) be used together in CP-ABE scheme?

Yes. As Attribute-based signcryption with hybrid access policy (Yu and Cao, 2015) shows, it is possible to combine an Attribute-based Encryption scheme with an Attribute-based Signature scheme of different access structures and different flavors. This is commonly referred to as Attribute-based Signcryption.

  What changes are necessary for the two access policy structures to work together?

That would be a longer answer along with the necessary security game.

  For example, can I translate an MSP access policy to an access tree?

Yes, because a monotone access tree has the same expressiveness as a Monotone Span Program. I don't know whether there is an algorithm for this. It is usually done the other way around. For example, access tree to LSSS is described in Efficient Generation of Linear Secret Sharing Scheme Matrices from Threshold Access Trees (Liu, Cao, Wong, 2010).

Note that a Monotone Span Program (MSP) is equivalent to a Linear Secret Sharing Scheme (LSSS). Again, I'm not sure if there is an algorithm of doing the translation out there.


Was RSA inspired by Diffe-Hellman, published the year before in 1976

Update

I met Ron Rivest at MIT's LCS35 time capsule unveiling and asked him this question for you.

The answer is yes.

Original Answer

In "The first ten years of public-key cryptography", the following social relationships are mentioned:

  Ron Rivest had been a graduate student in computer science at Stanford while I was working on proving the correctness of programs at the Stanford Artificial Intelligence Laboratory. One of my colleagues in that work was Zohar Manna, who shortly returned to Isreal and supervised the doctoral research of Adi Shamir, at the Weitzman Institute.

So Rivest went to the same school where Whitfield Diffie was working, and Zohar Manna apparently brought the knowledge to the attention of Adi Shamir.

So they certainly must have been aware of Diffie and Hellman's work.

In fact, the original paper on RSA cites the paper "New Directions in cryptography" by Diffie and Hellman, so that's pretty much a smoking gun that proves that they were building off the work of Diffie and Hellman.


Brute force attack expected running time

Well, ECC takes about $2^{n/2}$ time to break because there are smarter ways to attack it than literally trying each possible key separately.

With AES, the best known-attack is to try a key, and see if it works.  If it doesn't, all you've learned is that that specific key wasn't it, only $2^{n}-1$ more to go...

However, with ECC, there are other methods.  For ECC, in general, a public key gives us two elliptic curve points $G$ and $P$; to break it, we need to find an integer $k$ such that $kG = P$ (where $kG$ is point multiplication).

Now, there are $q$ possible values of $k$ (where $q \approx 2^{n}$ is a large prime that depends on the curve); however here is a smarter way to attack it:

Compute a value $r \approx \sqrt{q}$
Generate the $r$ values $P-0G, P-1G, P-2G, P-3G, ..., P-(r-1)G$.  This takes $O(r) = O(\sqrt{q}) = O(2^{n/2})$ time.
Generate the $r$ values $0rG, 1rG, 2rG, 3rG, ..., (r-1)rG$.  This also takes $O(r) = O(\sqrt{q}) = O(2^{n/2})$ time.
Scan through the two lists for a value in common; if we see that $P-iG = jrG$, (for two integers $i$, $j$) then we have $P = (jr+i)G$, and that solves it.  This always succeeds if $r \ge \sqrt{q}$, and this takes $O(2^{n/2})$ time if we use an appropriate hash table.

Total time taken: $O(2^{n/2})$.

This isn't the only way to solve the problem this quickly (there's also Pollard's Rho, which doesn't involve huge tables), however this is the easiest to explain.


How much more secure is $c = mg_1^r + g_2(g_1(g_1^r-1)/(g_1-1)) \mod p$ compared to just $c = mg_1^r \mod p$ (dis. log), all known but $r$?

If the attacker knows everything (including $m$) except for $r$, he can rewrite it to:

$$g_1^r = (c + g_1 g_2 (g_1 - 1)^{-1}) ( m + g_1 g_2( g_1 - 1)^{-1})^{-1} \pmod{p}$$

He knows everything on the RHS, and so it's a simple discrete log problem.

BTW: for the $\mathbb{Z}_p^*$ group, there are much faster attacks than Baby-step-Giant-step


If the POS system is online, then its simple. Just have a purchase ID in the QR.
The POS will call your API, and "create" an unpaid purchase.
This purchase ID is encoded into an QR.

Then the customer scans this QR, and approves payment. You don't even need to display a returning QR, because the POS could poll the API at regular intervals and check when the ID is "paid".

If you want to be able to have an offline POS, its also pretty easy. You need a shared key, that is unique per physical store location (store_id must also be unique per store location, store_id is then used by the payment server to look up the correct HMAC key).

If a store accidentially leaks their shared key, they must replace it immediately, else they risk customers creating fake QR codes to get products for free.

The store have a QR code with:
amount + "-" + description + "-" + purchase_id + "-" + store_id + hmac_sha256(amount + "-" + description + "-" + purchase_id + "-" + store_id + "-unpaid-", SHARED_KEY)

You send this to server. Server validates the hmac, and then, upon payment, creates the following QR:
hmac_sha256(amount + "-" + description + "-" + purchase_id + "-" + store_id + "-paid-", SHARED_KEY)

Assuming a shared hmac_sha256 key of: SHAREDKESHAREDKESHAREDKESHAREDKE

First you create the purchase:
100-USB memory-0001-1212-475d1fa90f24e134e76ffcc075ad3e7ce2c76e1ae78c7c8408c7508882ee9952
(89 characters)

Then app sends this for payment.
When payment is done, you create the following QR:
0899dd28bb8e5cfe6d54deb0000df01cec88f65b85a0b4148d7b49dddd2453d9
(64 characters)

NOTE: The original purchase data is NOT needed in the "reply QR" - the cash register already have this data from the pending transaction, that it can use to check the reply QR. So the "reply QR" becomes much smaller and more easier to scan.

NOTE2: Even if someone learns the structure, its still a impossibility to create a valid reply HMAC from the request HMAC. Changing "-unpaid-" into "-paid-" would require knowledge of the shared key.

NOTE3: purchase_id must be unique among a single physical store location (store_id). If a store is generating duplicate purchase_id's, a customer can reuse a paid order to get products for free. If a store location has multiple offline POS not even connected with each other, the store, which also chooses purchase_id, must prepent the POS location to purchase_id, eg have purchase_id 10000-19999 for POS 1, 20000-29999 for POS 2, and so on. In my solution, purchase_id can be of any length required for the purchase_id not to roll over.

You really don't need to mix in RSA at all.

Actually, you don't need an HMAC for the request at all (but its ALWAYS required for the Response). Its just a customer protection so any scan errors or any sheninigans doesn't cause a customer to do a payment for a non-existing purchase.
The reason is that the request isn't security-sensitive, is because if the customer edits the purchase request, the response QR for the paid purchase will not validate, and the hacking customer will not get anything out of it.

But you must atleast have some error protection so not a damaged QR display or strong light falling on QR-code or the phone camera causes it to generate a purchase request, which when paid for, will not release any products, and thus cause a legit, fair customer to lose money. Thats extremely unlikely however, as QR code contains their own checksums, but feel free to add any checksum you like to the request. It can be HMAC, a md5 hash, a CRC32, whatever. Even a truncated hash suffices, if you must keep the request size down to not cause too large (and unscannable) QR codes.

The customer editing a purchase request to for example try to get products cheaper, and then getting a invalid response QR back, would be equvalient of a customer taking a 20 dollar bill, and trying to make a 100 dollar bill out of it, failing the fraud attempt, and thus losing the 20 dollar bill. So basically, any protection on the request is only for customer protection against themselves, which you can skip if your situation does not require it.


what is a rigorous definition of "proof-of-possession"?

The closest notion used in the literature seems to be “proof / argument of knowledge” (PoK / AoK). See [GMR, BG] as well as Wikipedia for its definition. Indeed, giving out the key would be a proof of knowledge (but it's not of much interest to cryptography).
The part about “not sending the value to the other party” seems to be related to zero-knowledge (ZK). ZK requires the interaction yields no extra effect beyond the prover convincing the verifier. For example, if a ZKPoK is used to prove possession of a secret key with respect to a public key, then the verifier does not learn any extra practical information about the secret key after being convinced. See [GMR] and Wikipedia.


Shamir's ID based signatures - Notation issues

Ok, lets look at the operations.

Sign: $s = g * r^{f(t,m)} \pmod n$

This is an assignment. You compute $(g * r^{f(t,m)}) \mod n$ and assign the resulting value to $s$. If you have a multiplication $(a \cdot b) \mod n$, this is equal to $((a \mod n)\cdot (b \mod n)) \mod n$. See for instance here.

Verification: $s^e = i * t^{f(t, m)} \pmod n$

This is no check for equality, but a check for congruence.

You can implement this by computing $s^e \mod n$ as well as $(i * t^{f(t, m)}) \mod n$ and check if these values are equal.

fgrieu has recently written an answer to a recent question on congruences which clarifies this nicely.


How to formally prove that a given hash construction is collision resistant or not?

Proof by contradiction is easy in this case.

Assume the construction is not collision resistant. Then there's an adversary who can efficiently find a pair $H(x) = H(x')$. However, that also gives them $H_1(x) = H_1(x')$ and $H_2(x) = H_2(x')$, so neither hash function is collision resistant, which contradicts the assumption.


What is the current security level of an algorithm?

First of all: The security and the length of the key depends on the system you use. So e.g. RSA needs longer keys than AES-256 does, to ensure the same security.

Second: The level of security depends on the application and how secure it has to be. A important point here is: How long should it be secure. There are still security systems in use, that can be broken in days. That's however no problem when the information only has to be secure for some minutes/hours.

This question / answer about algorithms used for SSH keys on the Information Security site might also help you.


A couple of papers by Faugère and Perret (and, in one case, von zur Gathen) provide efficient (i.e., polynomial time) algorithms to solve the Functional Decomposition Problem:

Given: a list of $u$ multivariate polynomials $H = (h_1, \ldots, h_u) \in (\mathbb{K}[x_1, \ldots, x_n])^u$ in $n$ variables over some field $\mathbb{K}$.
Task: find a non-trivial decomposition $(F,G)$ where $F = (f_1, \ldots, f_u) \in (\mathbb{K}[x_1, \ldots, x_n])^u$ and $G = (g_1, \ldots, g_n) \in (\mathbb{K}[x_1, \ldots, x_n])^n$ such that $H = F \circ G$.

There are various definitions of "non-trivial" designed to explicitly exclude pathological cases such as where $F$ or $G$ are the identity or linear transforms. Suffice to say that any cryptosystem claiming security based on the hardness of multivariate polynomial decomposition, such as your proposals, should convincingly argue why the algorithms of Faugère et al. do not apply.

Specifically, these algorithms enable the attacker to obtain $f$ from $p$ in your proposals, even without using $g$. This breaks the schemes without inverting anything because $f$ represents the secret key.

There was a similar proposal called 2R$^-$. It was the original motivation for Faugère and Perret to study the FDP, which lead to that scheme's demise.


Reconstruction vector in Linear secret sharing schemes

Notation in this answer is as in the answer to a question on the same LSSS construction.

Is this the right way to calculate g?

You are correct that you solve for $g$ by setting attributes $B$ and $C$ to zero.  What you are actually doing is computing a solution vector, which I will denote by $\mathbf{g}_{\{A,D\}} \in \mathbb{F}^2$, to $\mathbf{g}_{\{A,D\}} \cdot M_{\{A,D\}} = (1,0,0)$ where

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

and then lifting to a solution by padding with $0$s to get a full vector $\mathbf{g}$.  So here you find that $\mathbf{g}_{\{A,D\}}=(1,1)$ (and happens to be unique in this case), and then we pad with $0$s in the corresponding components of the vector $V$ to get $(1,0,0,1)$.  This final solution (after padding) is called a recombination vector for this set.

The vector $V$ is just a way of saying which rows it is permissible to combine in order to try to obtain the target vector $(1,0,0)$.  If you like you can think of finding $\mathbf{g}$ as finding a solution to the equation

$
\mathbf{g} \cdot
\begin{pmatrix}
1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1
\end{pmatrix}
\cdot M = (1,0,0)
$

where the middle matrix is a square zero-matrix replacing the leading diagonal with the entries of $V$.  It is essentially irrelevant that $V=\mathbf{g}$ in this case: the point is that the support (here meaning the indexing set of non-zero components) of the vector $\mathbf{g}$, denoted by $supp(\mathbf{g})=\{1,4\}$, is contained in $supp(V)=\{1,4\}$.

How do we proceed to calculate g as we then have two cases?

If a vector $\mathbf{g}$ works for the smaller set $\{A,D\}$, then it will also work for the larger set $\{A,B,D\}$, since the target vector already lies in the linear span of rows indexed by attributes $\{A,D\}$.  In other words, the same solution works because $supp(\mathbf{g}) = \{1,4\} \subseteq supp((1,0,0,1)) = \{1,4\} \subseteq supp((1,1,0,1)) = \{1,2,4\}$.

Indeed, it is easy to check that your solution $\mathbf{g}=(1,0,0,1)$ also solves

$\mathbf{g} \cdot
\begin{pmatrix}
 1 & 0 & 0 & 0 \\
 0 & 1 & 0 & 0 \\
 0 & 0 & 0 & 0 \\
 0 & 0 & 0 & 1 \\
\end{pmatrix}
\cdot M = (1,0,0).$

Thus in general it suffices to compute recombination vectors $\mathbf{g}$ for only the minimally authorised sets: then for any authorised set $A$ we can take any $\mathbf{g}$ for any minimally authorised set which contains the set $A$ and it will also work for $A$.

Then why do {A,B,D} and {A,C,D} have the same coefficients i.e (1,0,1)?

In this example there is only one vector, namely $\mathbf{g}=(1,0,0,1)$ for all three sets $\{A,D\}$ $\{A,B,D\}$ and $\{A,C,D\}$, which means you get $\mathbf{g}_{\{A,B,D\}} = \mathbf{g}_{\{A,C,D\}} = (1,0,1)$.  This is because to combine the vectors $\{ (1,1,0), (0,-1,1), (0,-1,0)\}$ owned by $\{A,B,D\}$, we must have zero contribution from $(0,-1,1)$; similarly, to combine the vectors $\{ (1,1,0), (0,0,-1), (0,-1,0)\}$ owned by $\{A,B,D\}$, we must have zero contribution from $(0,0,-1)$, otherwise the third component will not be $0$ as it must be for constructing the target vector $(1,0,0)$.


differential cryptanalysis cipher for the final round


What is the technical name for a public key container in DER format?

As can be seen by RFC 5280 (X.509), this structure is the SubjectPublicKeyInfo. This field is formatted as follows:

SubjectPublicKeyInfo  ::=  SEQUENCE  {
     algorithm            AlgorithmIdentifier,
     subjectPublicKey     BIT STRING  }

The AlgorithmIdentifier is defined as follows:

AlgorithmIdentifier  ::=  SEQUENCE  {
     algorithm               OBJECT IDENTIFIER,
     parameters              ANY DEFINED BY algorithm OPTIONAL  }

The above two types define the format of the outer container in the ASN.1 in question (with the NULL value corresponding to the parameters field). The BIT STRING is an inner object defined by Appendix A.1.1 of PKCS #1 v2.1 as follows:

RSAPublicKey ::= SEQUENCE {
    modulus           INTEGER,  -- n
    publicExponent    INTEGER   -- e
}


Disclaimer: The use cases for proxy re-encryption are very specific. From your description it is not clear to me why you don't just encrypt the message with a different key for your someone.

Looking at the scheme it seems to me that someone only gets $x_2$ and cannot use that to learn anything about $x_1$. Even given multiple pairs $x = x_1^{(i)} + x_2^{(i)}$; if only the $x_2^{(i)}$ are known any $x'$ could be the correct key for $x_1^{(i)} = x' - x_2^{(i)}$.


For textbook RSA, we have

Key-Gen

The modulus $n$ must be a product of two distinct random large primes due to the security, $n = p \cdot q$

in your case $n=143 = 11\cdot 13$

For finding the primes, the probabilistic Miller–Rabin primality test, it should be enough. Note that the Miller–Rabin primality test is probabilistic; composite output is always true, prime output has probability defined by the number iterations, $k$; $$\Pr( p\text{ is not prime} ) \ll \frac{1}{4^k}$$ and can be stated as $$\log_2(\Pr( p\text{ is not prime} ))\ll-2k$$ This is a rough calculation, and as noted by fgrieu, the probability is approaching 0 as the size of the number to be tested increases. The FIPS 186-4 table C.3 provides specific numbers for $k$;

for 512 bits gives $k=7$ rounds with $\log_2(\Pr( p\text{ is not prime} ))<-100$,
for 1024 bits gives $k=4$ rounds with $\log_2(\Pr( p\text{ is not prime} ))<-100$, and
for 1536 bits gives $k=3$ rounds with $\log_2(\Pr( p\text{ is not prime} ))<-100$.

The factors of modulus are $p=11$ and $q =13$
$\varphi(n) = (p-1)(q-1)$, in your case  $\varphi(143) = 10\cdot 12 = 120$,

Actually, we prefer $\lambda(n) = \operatorname{lcm}(p,q)$ and this will give us the smallest private exponent. That can be helpful for signature calculation speed, and actually, one should use the CRT method ( see the last bullet of Key-Gen)

The relation is;
$$\varphi(n)=\lambda(n)\cdot\gcd(p-1,q-1)$$ and this implies that $\lambda(n)| \varphi(n)$
The public exponent $e$ is chosen relatively prime to $\varphi(n)$, so $e=7$ is fine. Normally the $e$ is chosen advance in $\{3, 5, 17, 257, 65537\}$. If the $\gcd(e,\varphi(n)) \neq 1$ then a new modulus is generated.

$(n,e)$ makes the public key to distribute.
The private exponent $d$ is the inverse of $e$ modulo $\varphi(n)$, i.e. $d\cdot  e \equiv 1 \bmod \varphi(n)$, in your case $d=103$. This can be used with the Ext-GCD which result in a Bézout's identity $ e \cdot x + n \cdot k =1$. Take modulus $n$ then $x$ is the inverse of $e$.

$(n,e,d,p,q, d_p, d_q, q_{inv})$ is your private key. One can use CRT to speed up the decryption up to 4 times.

Encrypt

$c = m^e \bmod n$

The $m \in [0,n)$, otherwise after the decryption one will get an equivalence class representative of $m$ less then $n$.

Decrypt

$m = c^d \bmod n = (m^{e})^{d} \bmod n = m^{ed} \bmod n = m$

Example

$m = 7$ then  $c = 7^7 \pmod{143} = 6$
$m = 6^{103} \pmod {143}= 7$

Notes:

There is also multi-prime RSA where the large prime factors of $n$ are mode than 2.
Textbook RSA is not secure one should never use it without a proper padding scheme. One is the PKCS#v1.5 padding scheme and the other is RSA-OAEP. RSA OAEP has a security proof and PKCS#v1.5 has not. PKCS#v1.5 has many attacks over the years and should not be used.
RSA ( actually any public-key encryption) is not preferable due to the speed. We prefer the hybrid encryption schemes like RSA-KEM for Key Encapsulation Mechanism then encrypt the data with AES-GCM or ChaCha20-Poly-1305 to achieve Data Encapsulation Mechanism, use 256 bit key with AES, preferably.

With this composition of a KEM and a DEM, one can achieve IND-CCA2/NM-CCA2—ciphertext indistinguishability and nonmalleability under adaptive chosen-ciphertext attack.


What is the advantage of digital signatures over message authentication codes?

If this requires a single answer among 1/2/3/4 (rather than none), I would select 3, by the following reasoning:

  Digital Signature provides confidentiality while message authentication code can not

We can summarily exclude this, since a Digital Signature simply does not provide confidentiality.

  Digital Signatures works faster than message authentication codes

We can exclude this (slightly fixed) statement: Digital Signature is often annoyingly slower than MAC (an exception is long messages with the signature's hash supported by hardware and the MAC in software; but then we can hash then make a MAC of the hash to regain most of the speed). Digital Signatures also has larger minimum size overhead for equivalent resistance to brute force.

  Digital Signatures provide authenticity while message authentication code cannot

Authenticity is commonly defined as only a user authorized to author or modify a message can do so. In some use cases, a MAC can provide authenticity (e.g. if the MAC key is kept secret, including unknown to users that verify integrity, by using Smart Cards to verify signed messages); but if we understand "while" as including in some setups where, the statement makes sense: the (only) advantage of Digital Signature over MAC is that verification is possible with only public keys; and that provides authenticity in many setups where a MAC does not (e.g. verification using a computer that adversaries can fully analyze).

  Digital Signature provides integrity verification while message authentication code can not

Integrity is commonly defined as resisting accidental alterations, or the stronger resisting deliberate modifications by outsiders. Digital Signature and MAC both insure this. Other definitions similar to that of authenticity are sometime used, but if we have to choose between 1 and 3, we must pick 3.


Comparing plaintext to contents of ciphertext

2 is considered better, because the probability of the comparison in 1 returning $\:\text{true}\:$ is always at most $$\frac1{2^{\operatorname{len}(\text{IV})}}$$


Is there a way to double the size of ciphertexts of a public-key scheme which is IND-CCA2

This is actually a very interesting theoretical question that was open for many years. For CPA-secure encryption, it is possible to simply concatenate ciphertexts in order to increase the plaintext space. However, for CCA2, it is not sufficient to concatenate since it's possible to move around the bits and maul the ciphertext. Note that if you assume that the original plaintext space is large  (super-polynomial), then it's easy to solve by just using hybrid encryption. This is because you can encrypt a symmetric key and work from there. However, if the plaintext space is small -- especially hard if a single bit -- then it's very unclear. Fortunately, Myers and shelat solved this in FOCS 2009 in a paper entitled Bit encryption is complete.


Actually, because of DESX works, the meet-in-the-middle attack can be optimized to take $2^{119}$ $DES$ (and no $DES^{-1}$ operations), and no additional storage.

Here is how it works: let us assume that we have three known plaintext/ciphertext pairs $(P_1, C_1)$, $(P_2, C_2)$ and $(P_3, C_3)$.  We know that:

$$C_1 = K_2 \oplus DES( K, K_1 \oplus P_1 )$$

$$C_2 = K_2 \oplus DES( K, K_1 \oplus P_2 )$$

In a standard meet-in-the-middle attack, we would rewrite the first equation as:

$$C_1 \oplus K_2 = DES( K, K_1 \oplus P_1 )$$

and create lists of the two sides (using possible values of $K, K_1, K_2$), and search for common values; the lists (actually, we'd create a list only for the left side, as it's smaller) would account for the additional storage.

However, in the case of DESX, we can simplify this by combining the two equations as:

$$C_1 \oplus C_2 = DES( K, K_1 \oplus P_1 ) \oplus DES( K, K_1 \oplus P_2 )$$

We know the value on the left side; with $2^{119}$ DES operations, we can go through all possible combinations of $K, K_1$ that make this equation work (note: why $2^{119}$ and not $2^{121}$?  Because there are two separate artifacts that allow us to reduce the search space by a factor of two each: the first is the observation if a value $K_1$ makes it work, so does the value $K'_1 = K_1 \oplus P_1 \oplus P_2$; hence if we test one $K_1$ value and it doesn't work, we can skip the corresponding $K'_1$ value; the second is the key complementation property of DES; that is, if $K, K_1$ satisfies the above equation, so will $\bar{K}, \bar{K_1}$; hence if we test one $K$ and it doesn't work, we know that $\bar{K}$ wouldn't either.  So we test the above with $2^{55}$ $K$ values and $2^{63}$ $K_1$ values, and each test involves 2 DES operations, for a total of $2 \times 2^{55} \times 2^{63} = 2^{119}$ DES evaluations).  And, because we're not explicitly making any lists, we don't use any extra memory.

When we find a $K, K_1$ pair that makes this work, we can compute the correspond $K_2$ values, and test it out with our third known plaintext/ciphertext pair; this additional checking is rare (once out of $2^{64}$ pairs tested), and so can be ignored when doing complexity computations.

And, this observation can be extended to show that the attack against DESX can be performed even faster if we have more plaintext/ciphertext pairs.


Complete Attack on RLWE Key Exchange with reused keys, without signal leakage

There is a condition that is not considered, that is, the value after modulo 257 should be in $\mathbb Z_q$.
When $q = 257,    \mathbb Z_q = \{ -128, ... , 128 \}$, so,  $(4+128)\mod 257$ should be $-125$ rather than $132$ .
And $-125 \mod 2 = 1$.
Thus, $sk_a \neq sk_b$  and the output of  oracle $\mathcal B$ is $0$.


What is more secure, a ciphertext encrypted with AES-256 or encrypted with 3 different AES-128 keys?

You have more than one question in your... question. user13741 already did answer the "is 2x AES-128 as secure as 1x AES-256?" part, so only a small summary: Plaintext is the message before it was encryptet, and ciphertext after it was encryptet. You can encrypt a known plaintext with all possible keys and save the result. Now you decrypt the ciphertext with all possible keys and look if the result is in the database of the first encryption task. If yes, you have found the two keys. The first task takes $2^{128}$ encryptions (for AES-128) and the second task takes $2^{128}$ decryptions. If you add them you get not $2^{256}$, but $2^{129}$.  That attack is called Meet-in-the-middle attack. (But you need the space to store $2^{128} \times 128$ bit. That's more than you will ever be able to store, but still you have to consider this. Maybe a future attack will somehow reduces the security of AES in a way which will make this kind of attack feasible without storing over $10^{27}$ terabytes.)

In the title you ask about 3 different AES keys. Yes, this construct is more secure than AES-256. An attack on this (if AES is not broken) would take something like $2^{257}$ encryptions or decryptions, even more than on AES-256. Without the mentioned meet-in-the-middle attack you would even need $2^{384}$ to fully search the possible key space. This is the reason why Triple DES was used and not Double DES. DES with two keys would be enough in terms of the number of possible keys, but this attack makes it possible to reduce the amount of work to a nearly managable number. Not secure enough for most of the experts.

Why nobody (or at least not a high number of people) encrypt their message more than one time? There's no need for that. Even $2^{128}$ attemps are totally unfeasable. Even if the future of the world would depent on it and every government would need to break it. There are just too many possible keys. An attack on the person which knows the key or attacking the underlying protocol is much more promising.

Yes, you are right, there's exactly one key which results in the given plaintext for a given ciphertext (and the other way round). Also there's exactly one plaintext for every given plaintext and given key (and vice versa). This is true for AES-128, while AES-192 and AES-256 are slightly more complicated, but not much.

Now comes the big "but": All this only works if AES is fully secure. It is not. There exist some attacks which reduce the amount of security AES has. AES-256 is more "broken" than AES-128 and AES-192 (because the key setup is slightly different for AES-256 and it uses a bigger key size). Still, all three are (as we know it) still not really broken. The security margin is still quite high and the kind of attack is a pretty hard one. We don't have to panic, but for the future we should either change AES to make it more secure (Bruce Schneier suggests more rounds as fast and easy change) or take a look at some other ciphers like one of the other finalists of the AES process. If you really need to secure some highly risky data for 30 years against the NSA and other major organisations, than you should consider not using AES. For every normal person, AES is more than enough.)