Why is Bcrypt called a Key Derivation Function?

It's called a key derivation function because that's what you'd typically use its output for — as a key for some other cryptographic algorithm.  (Of course, you can also use the output of Bcrypt for other purposes, e.g. storing it in a database as a password hash, but that's really a secondary use case.)

In general, key derivation functions (KDFs) serve a number of purposes:

Key separation: This is the most basic use case for KDFs. Basically, you have one key, but need several.  This might be e.g. because you're a server that needs to communicate with multiple clients using distinct keys for each, or simply because the algorithms you're using together (e.g. a cipher and a MAC) have only been proven secure under the assumption that they each have separate and independent keys.  You can solve this problem by using a KDF (with different salts) to derive multiple (quasi-)independent subkeys from your original key.
Key expansion: Related to the above, some algorithms may require rather long keys for practical reasons, even though the desired security level against brute force guessing could be met with a shorter key.  In such cases, you can use a KDF to effectively extend the length of your key.
Key whitening: Many encryption algorithms, such as block ciphers, require a key that consist of a fixed number of (effectively) random bytes.  If you have a key that is not in the required format (such as an arbitrary-length passphrase, or a Diffie-Hellman shared secret), you can use a KDF that accepts arbitrary input key material to hash it into a byte string of suitable size.
Key stretching: This is the specific use case for which Bcrypt (and other "password-based" KDFs like PBKDF2 or scrypt) are designed for.  Basically, say you have a user-entered passphrase that may have a relatively small amount of entropy (say, from 20 to 40 bits), in addition to all the other issues mentioned above (too short / too long, wrong format), and you want to use it to encrypt/decrypt some data (or to authenticate the user) while making it hard to break the encryption by guessing the passphrase by brute force.

The solution is to use a deliberately slow (and possibly memory-hungry) KDF, like Bcrypt, to derive an encryption key from the passphrase.  By making the derivation process deliberately take a very long time (say, a whole second, which might be a million times more than a simple non-stretching key derivation would take), you can slow down any brute force attacks by the same factor.  The reason it's called "key stretching" is, presumably, because you're taking a "short" (low-entropy) key and effectively making it as resistant to brute force attacks as a "longer" (higher-entropy) one.

Now, that's a whole bunch of jobs, and indeed one might argue against lumping all functions designed for some or all of these tasks under the single label "KDF", but that's how the established terminology works.  There is some justification for it, since systems that require the latter properties often also require the former.

Still, different KDFs do have different strengths; for example, Bcrypt is pretty good for key stretching, but somewhat awkwardly limited in other respects.  If I wanted a Bcrypt-based system that handled all of the points above, I might consider e.g. combining Bcrypt with HKDF (from RFC 5869), like this:

Use HKDF-Extract to whiten the input key material / passphrase, avoiding the input length limits of Bcrypt.
Feed the pseudorandom key generated by HKDF-Extract through Bcrypt to stretch it against brute force attacks.
Use the output of Bcrypt as the PRK for HKDF-Expand, to provide efficient key separation and expansion.


If the maximum Hamming distance $d$ between the keys is small enough (and to a lesser degree if the key size $n$ is bits is small enough), one obvious technique is that Alice computes $H(k_1)=h$ for $H$ some cryptographic hash, e.g. SHA-256; and sends $h$ to Bob. He explores $x$ of small Hamming weight until $H(k_2\oplus x)=h$, and when he finds such $x$, he knows $k_1=k_2\oplus x$. There are $\displaystyle\sum_{i=0}^d{{n}\choose i}$ values to try. That's $2^{\approx40.5}$ hashes for a $n=128$-bit key with up to $d=8$ garbled bits, which is already inconveniently slow/costly for Bob, thus that does not work at all for sizably larger $d\log_2(n)$.

If the key has enough entropy and thus can't be enumerated (e.g. it has $n\ge128$ uniformly random and independent bits) and is used to key some fast cryptographic algorithm unrelated to $H$ (e.g. AES when $H$ is SHA-256), this reveals nothing useful about the key. However, beware of interactions! As an extreme example, if the key is used as an HMAC-SHA-256 key, and $H$ is SHA-256, and $n>512$, then $k_1$ is entirely compromised, because by definition of HMAC for long keys, $\forall M,\,\text{HMAC-SHA-256}(k_1,M)=\text{HMAC-SHA-256}(H,M)$.

Note: this is essentially the question's brute force method, except that by processing the key thru a hash independent of the normal use of the key, we avoid using the key in one of its possible intended later way. A more formal approach could always use $k_1$ as the key of a Key Derivation Function, with one derivation parameter reserved for repairing $k_1$.

If the key is large with aplenty entropy (e.g. 256-bit or more), and the above can't be applied because $d\log_2(n)$ is too large, or we want no guesswork for Bob, another option is to use Forward Error Correction: Alice computes and reveals $C=\text{FEC}(k_1)$ of $c$ bits, with $c$ large enough to correct the expected error knowing $k_2$, but still a small fraction of $n$.

It must be used a FEC system where the message normally sent for payload $M$ is $M\mathbin\|C$ with $C=\text{FEC}(M)$, which is common, and includes some Turbocode (as used in 3G/4G mobile communications). The FEC should have little or no extra error-detection capability after correction.

Alice computes and sends $C\gets\text{FEC}(k_1)$, and $h\gets H(k_1)$ as before.

Bob receives $C$ and $h$, applies the FEC recovery to $C$ and $k_2$ to get a tentative $\widetilde{k_1}$, and if $H(\widetilde{k_1})=h$ concludes that $k_1=\widetilde{k_1}$.

Compared to the previous scheme, at most $c$ bits of entropy have leaked about $k_1$, and for a full-entropy $k_1$, we are safe as long as $n-c$ remains large enough to make $k_1$ unguessable; and the FEC, $H$, and the algorithm used for $k_1$ do not interfere.

If we again allows some guesswork for Bob, we can reveal less about the key, as follows.

Alice

computes $C\gets\text{FEC}(k_1)$ as above
optionally applies some public pseudorandom permutation $P$ to $C$, yielding $C'$ (or just $C'=C$)
splits $C'$ into $C_1\|C_2=C'$, with $C_2$ of $r$-bit, e.g. $r=32$ (or smaller, down to possibly $1$);
computes $h\gets H(C_2\mathbin\|k_1)$
sends $C_1$ and $h$

Bob

recovers $C_1$ and $h$
for up to $2^r$ values of $\widetilde{C_2}$

deduces the corresponding $\widetilde{C}=P^{-1}(C_1\mathbin\|\widetilde{C_2})$ (or just $\widetilde{C}=C_1\mathbin\|\widetilde{C_2}$ for no optional pseudorandom permutation)
applies the FEC recovery to $\widetilde{C}$ and $k_2$ to get a tentative $\widetilde{k_1}$
if $H(\widetilde{C_2}\mathbin\|\widetilde{k_1})$ matches $h$

concludes that $k_1=\widetilde{k_1}$, and proceedq to use that with Alice.

if no match is found, stops with failure.

$C_1$ was $c-r$-bit, thus at most that much entropy has directly leaked. The pseudo-random permutation allows a simple security argument that the attacker's best strategy has cost $O(2^{n-c+r})$ operations for full-entropy $k_1$ even for pathological FEC, but is probably not necessary in practice.

If $k_1$ is not full-entropy, then $O(2^{\text{Entropy}(K_1)-c+r})$ work must remain infeasible to the adversary, and if we want a simple security argument (including if $k_1$ is used only in part), we can pass $k_1$ thru another public PRP before applying the whole scheme, and pass it thru the inverse permutation in the end.

If wanted, the PRPs can be built from a MGF as in OAEP.


Crypto++ benchmarks cycles/byte vs. megacycles/operation

The reason for this is that RSA and other asymmetric operations are not used for bulk encryption (or bulk signature generation, if such a term exists).

If a lot of data needs to be signed/verified or encrypted/decrypted then a hybrid cryptosystem will be used instead.

In the case of signature generation / verification most if not all of the plaintext will be hashed by a secure hash algorithm. This hash value will be used as input for signature generation or verification using the asymmetric keys.

For encryption a symmetric cipher will be used. The symmetric key will be wrapped / unwrapped or derived using the asymmetric keys.

So you'd use just a single operation when it comes to asymmetric primitives such as RSA for most operations.

If hybrid encryption is used you'd use a single operation for the asymmetric primitive and then add the amount of time required to hash or encrypt the amount of data.


Here you have an overkill of information, really. We know that $e_A$ and $d_A$ are related by the fact that $e_A d_A \equiv 1 \pmod{\phi(N)}$, normally, and then this answer gives an algorithm.

But here we have more info, as both $e_A d_A - 1$ and $e_B d_B - 1$ are multiples of $\phi(N) = (p-1)(q-1)$. We need some multiple of their gcd, that is close to $N$ to get $\phi(N)$.
Their gcd is 7656, and half of that is 3828, which is probably $\phi(N) = (p-1)(q-1)$.

Now from this you can solve the quadratic equation $(x-p)(x-q) = 0$, because the left hand side is now known: $x^2 - (p+q)x + pq = x^2 + (N - \phi(N) + 1 )x + N = 0$, and $p$ and $q$ follow from the standard formula.


How can mega store my login details and still be secure?

Here are some hints on how it's done on Mega:

The password provided is passed through a KDF to derive a key, that is used to en-/decrypt the master key (later provided by the server through an API call).

To bring it down to the crucial bits: The KDF applies $2^{16}$ rounds of AES-128 with it. The details can be found in the function prepare_key() of the web client in file crypto.js.

The user supplied password itself is never sent over the wire. And the master key is only decrypted client side using this password-derived 128 bit AES key.

To log in against the Mega servers, which gives one a valid session that allows one to access the (encrypted) master key, a token is computed. This token is computed using the derived key (see above) by running it through an additional series of $2^{14}$ rounds of AES-128 (see the stringhash function in crypto.js) after "joining" the user's email address with the above mentioned derived key.

D.W. is right, that the procedures in place are unfortunately not properly documented, yet. This is a severe shortcoming that needs to be rectified over time. Having said that, newer cryptographic work by Mega is paired with documentation in the form of a white paper as it is implemented to allow for peer review. These white papers are currently not openly published, yet, but interested parties have received these easily as needed or as requested, as they're still somewhat in flux.

If anybody is interested in further information, please feel free to email crypto@mega.co.nz for this to get first hand answers. However, that should still hold nobody back from discussing here or elsewhere, though it seems not easy to get explicit answers from the Mega developers here without letting them know of a question raised here.

Update:

There's an independent study that has been conducted by a researcher team in Spain: English PDF. They have dug into the available JavaScript code and reasoned on it. Except for minor flaws, the information is pretty much correct.


Is there any existing obfuscation scheme that makes cipher text indistinguishable from plain text?

As was mentioned, what you're asking for is a form of steganography,which may or may not use encrypted content.

The classic approach derives from talking around the subject (Crimes and Spies) as in:

"The Apple crates are Golden Delicious. There are 15 crates."

A more technical approach I've seen is  Spam Mimmic

Spam Mimmic encode:  Bob, meet me at the secret lair at 1900.

Spam Mimmic decode:

  Dear Friend , We know you are interested in receiving  red-hot news !
  This is a one time mailing there is  no need to request removal if you
  won't want any more  . This mail is being sent in compliance with
  Senate  bill 1626 ; Title 1 , Section 307 ! THIS IS NOT MULTI-LEVEL
  MARKETING ! Why work for somebody else when you can  become rich
  inside 31 DAYS ! Have you ever noticed  the baby boomers are more
  demanding than their parents  plus how many people you know are on the
  Internet !  Well, now is your chance to capitalize on this . WE  will
  help YOU use credit cards on your website plus  increase customer
  response by 120% ! You can begin  at absolutely no cost to you ! But
  don't believe us  . Mr Anderson who resides in Montana tried us and
  says  "My only problem now is where to park all my cars"  ! We are
  licensed to operate in all states . For the  sake of your family order
  now ! Sign up a friend and  you'll get a discount of 10% . Thanks .
  Dear Internet  user , This letter was specially selected to be sent
  to you ! If you are not interested in our publications  and wish to be
  removed from our lists, simply do NOT  respond and ignore this mail .
  This mail is being sent  in compliance with Senate bill 1620 ; Title 9
  , Section  303 . This is not a get rich scheme . Why work for
  somebody else when you can become rich within 92 WEEKS  . Have you
  ever noticed most everyone has a cellphone  plus nearly every
  commercial on television has a .com  on in it ! Well, now is your
  chance to capitalize on  this ! We will help you decrease perceived
  waiting  time by 120% and process your orders within seconds  . You
  can begin at absolutely no cost to you . But  don't believe us . Ms
  Ames of Mississippi tried us  and says "Now I'm rich, Rich, RICH" . We
  are licensed  to operate in all states . We urge you to contact us
  today for your own future financial well-being . Sign  up a friend and
  your friend will be rich too . God  Bless ! Dear Web surfer ; This
  letter was specially  selected to be sent to you ! If you are not
  interested  in our publications and wish to be removed from our
  lists, simply do NOT respond and ignore this mail .  This mail is
  being sent in compliance with Senate bill  1619 ; Title 3 ; Section
  301 ! THIS IS NOT MULTI-LEVEL  MARKETING . Why work for somebody else
  when you can  become rich in 41 DAYS ! Have you ever noticed people
  love convenience plus most everyone has a cellphone  . Well, now is
  your chance to capitalize on this !  We will help you deliver goods
  right to the customer's  doorstep and deliver goods right to the
  customer's  doorstep . You can begin at absolutely no cost to you  .
  But don't believe us . Mrs Simpson of Montana tried  us and says "My
  only problem now is where to park all  my cars" ! This offer is 100%
  legal ! DO NOT DELAY
  - order today . Sign up a friend and you'll get a discount  of 50% ! Warmest regards !

It's rather wordy and not practical for heavy use, but it gives you an idea. In general auto generating believable text is very difficult, hence the use of SPAM as it tends to blend in with other unbelievable text.


Argon2.

Argon2 is the current standard for password-hashing schemes, which are designed to be slow and more importantly expensive to parallel adversaries, even if they have hardware support. You can tune its speed via the memory and the time parameter, either of which should affect run-time linearly. Anyways, the paper in the repository should contain a guide on how to experimentally configure the parameters for your application.


Is there any SRP-like key exchange only using "standard" cryptographic primitives?

The first protocol for password authenticated key exchange that appeared in the crypto community was the Bellovin-Merritt scheme (see also this survey page 4). This protocol is very simple, and might actually suit your need: is is exactly a Diffie-Hellman key exchange, in which the flows are encrypted with a block cipher (using the common password as the key of the cipher), and where the secret key the players agree on is derived by hashing the Diffie-Hellman tuple. The security of this protocol was analyzed several times, in various models (ideal cipher model or random oracle model, in indistinguishability-based framework or simulation-based framework...). Although it does not enjoy a proof of security in the plain model, you might be satisfied with a protocol proven secure in the random oracle model.

In this case, this scheme seems to exactly fit your requirements: you need "any Diffie-Hellman key exchanged", together with "any (good) hash function" and "any block cipher" that allows you to encrypt the flow with the password. Variations of the Bellovin-Merritt scheme that might make it even simpler are presented in this article (they essentially replace the block cipher by a simple one-time pad, and have two variants, one non-concurrently secure and one concurrently secure).

EDIT: so, after discussing with Ricky Demer, this does not quite work yet. A necessary condition for this to work is that the messages generated by the DHKE - which are group elements - should be indistinguishable from random bit-strings. For DHKE over $\mathbb{Z}^*_p$ for some large prime $p,$ group elements can be naturally mapped to a distribution statistically indistinguishable from bit-strings, and existing implementations might already encode these messages as random-looking bit strings (but this would have to be checked). For more sparse groups such as elliptic curves, I believe such a mapping can be done, but it would be more cumbersome from an implementation point of view. I thank Ricky Demer for pointing this out.

The variants presented in this article do not use a block cipher, which gives rise to dictionary attacks when the encoded element does not look random, but using a kind of multiplicative one-time pad: Alice masks her flow $g^x$ by multiplying it with $M^{\mathsf{pw}}$, where $M$ is a group element and $\mathsf{pw}$ is the password (and Bob plays similarly). Here, you do not have to care about how group elements are represented; however, you must perform an exponentiation (with a small exponent) and a multiplication, hence it does not makes a black-box use of the DHKE key exchange.

EDIT:

So, I discussed today with my PhD advisor, who happens to be the author of quite a number of papers in the PAKE area (in particular this paper which I had mentioned). It confirmed what I had started to think: it does not seem feasible to build a PAKE with a black box access to a DH key exchange and symmetric primitives. Somehow, you have to be at least able to multiply two group elements (hence you must know their structure). I cannot prove that it is infeasible, of course, but that is currently unknown in the scientific community, and not believed to be feasible.


How does the UE communicate its ephemeral public key to the HN in 5G networks?

Ok, so after a lot of reading I realised that the UE's public key is actually concatenated to the ciphertext to create the SUCI. So it's by sending the SUCI that the UE actually sends it's Ephemeral public key


Real world use cases of Multi-Party Computation

As I mentioned in a comment, a relatively new application of multi-party computation is its use as a countermeasure against (mainly hardware) side-channel attacks. In particular, there is a method called "threshold implementations" which is based on a form of secret sharing.

A relevant reference would be the paper Secure Hardware Implementations of Nonlinear Functions in the Presence of Glitches by S. Nikova, V. Rijmen and M. Schläffer.
Extensions to higher-order DPA attacks have also been proposed.

Let's say you wish to securely implement a Boolean function $f$ with $n$ input bits. The (secret) input $x = (x_1, \ldots, x_n)$ is then "shared" by (randomly) choosing additive shares $x_{i, j}$ such that

$$x_i = \bigoplus_{j = 1}^{s_{in}}x_{i, j}.$$

I'll write $\mathbf{x} = (x_{1, 1}, x_{1, 2}, \ldots, x_{1, s_{in}}, x_{2, 1}, \ldots, x_{n, s_{in}})$ for convenience below.

The idea is then to share $f$ too, in such a way that for all inputs $x$ and correct sharings $\mathbf{x}$

$$f(x) = \bigoplus_{i = 1}^{s_{out}} f_i (\mathbf{x}).$$

This is called the correctness property.
We now also require that $f_i$ is independent of every $i$th share of $x$. So each $f_i$ actually operates on $n(s_{in} - 1)$ rather than $ns_{in}$ inputs. This is called the non-completeness property.

Under the non-completeness assumption, the paper shows that if $x$ is shared with independent uniformly chosen shares, then $f_i$ (as well as any intermediate result) is independent of the input shares $x_{k, i}$ with $k = 1, \ldots, n$.
This then leads to pipelined implementations which are secure against first-order (i.e. using first-order statistical moments) side-channel attacks. For more details, take a look at the paper (or other papers on the same subject).


Achieving non-linearity in a block cipher using only, rotations, shifts, AND, OR, and XOR

The brief answer is: Yes, you can!

You may wish to study NORX, an AEAD scheme submitted to the CAESAR competition, whose essential thesis is that you can simultaneously attain high security, high software performance, and high hardware performance by the same design principles as ARX, but replacing $a + b$, which is slow in hardware, by the approximation $a \oplus b \oplus (a \wedge b) \ll 1$.


How rotate RSA keys and how work with old encrypted data

I've generated the keys pair with some limited expiration time and I will use this private and public keys for the purpose of encryption and decryption and in one time the certificate will be expired

first - do you have a particular reason why would use short lifetime for the keys? Often there is no reason for that.  still  there should be a way how to replace the pki keys when needed.

From the comments seems you are designing a new system, what gives you more flexibility. I will try to build an answer from the comments

RSA has some limitations.  You can encrypt only data shorter than the keysize and as someone already mentioned in another answer - RSA is good at hiding random-looking data.

How PKI (RSA) is used to encrypt data - usually a random symmetric key is generated to encrypt the data (with arbitrary length using a symmetric cipher) and RSA is used only to encrypt (wrap) the symmetric key. see the hybrid cryptosystyem

  what alg do you recommend for symetric encryption?

you have plenty to choose... try to type openssl list-cipher-algorithms  something standard would be good, just don't reinvent anything own. AES-128-CBC could be good start

  Is it possible decrypt the symmetric key with expired certificate (private key)?

now - a homework for you. find out what is difference between a certificate and a public key..

nothing prevents you to use the public key to en(de)crypt even the certificate is expired.


How useful is NIST's Randomness Beacon for cryptographic use?

I would characterize the service as similar to a trusted time-stamping service. Except they do not do the time-stamping, but just provide the "key". This allows a user to decide what do to with it, such as using it as a private key to sign something, or an HMAC key, proving the signature is "not older" than the timestamp. If the signature is published to a verifiable record, it can then be proven to be "not newer" than the date of the record. If the gap is short enough, the applications for a signature or hash with a provable time period of creation are numerous. It can also be used an an additional input to a two factor authentication system (I think this is the most useful).

Other sources of true randomness are available, but having one for free is better if you do not need to use it for a cryptographic purpose. Having a way to prove or audit your random source is beneficial from a business or political perspective, as in the examples for the Unpredictable Sampling application link.

Other non cryptographic uses of random values could be used to prevent bias for things like "random screenings" of airline passengers, jury selection, and collection of census data. I doubt this will be implemented, but one can hope.

Service Security

We can make three types of assumptions from a subterfuge perspective.

The numbers are truly random, but are provided to the NSA in
advance (or are simply delayed for public view).
The historical record can be modified by the NSA or NIST, since
they have access to the private key.
The numbers are not truly random.

Not being random is something that would need an audit or some kind of analysis to prove. I doubt they are not random, but that does not mean that a non random value could be used for say, a single output.

The 2nd is unlikely to occur, since acceptance of the service would only be likely if you could verify the record from other parties, which one does trust to have been unmodified. Also since the output is based on the prior outputs, the entire chain would need to be tampered with.

The 1st is much more likely, the outputs could be delayed for a substantial amount of time, even days, and you would not know unless the entropy source can be audited by a trusted party. Since the signature is generated using a known future time code plus the current and prior values, it is trivial do to this without detection. Seeds could potentially be chosen at random and tested to give an output with a specific bias, but a massive amount would probably need to be tested to give appropriate output, at significant cost to the attacker (each requires an RSA sign and a hash, and the guarantee that the one specific value will be used by the target).

Given this, one would probably use these numbers only for uses where that would be highly unlikely to occur. Most applications would fall into that category. Anyone who needs these type of numbers for a use that is likely to be manipulated by an intelligence agency would just build their own entropy generator, which is not too difficult. If nobody is using the service for something the NSA would want to tamper with, the NSA wont tamper with it, it is simply too expensive and there would be no gain.

The only concerns I have from a cryptographic perspective are how the numbers are actually generated. The page does say that the output is full entropy and the output is 512-bits. It may be safe to assume that the "Seed Value" is actually the hashed output of the entropy source/DRBG, as the XML schema file says the "Output Value" is the SHA-512 hash of the signature, which I have verified to be the case. This means the output value is computationally infeasible to predict without all the input values AND the private key.

The specifics of the seed number are not listed, one can only assume that the samples are passed through SHA-512 to give this, but the size of the sample is not listed. Since the Beacon page specifically lists compliance with SP800-90, the entropy sample should be at least 888 bits, but there is nothing to confirm that, and no detail on the actual method of output generation, such as the DRBG used (very very important), and the reseeding interval.

Other Security Concerns

At this point I will assume the service is still in beta prototype, as their XML schema file references values that are not given, such as randomValue and previousHashValue, which are most likely supposed to be the seed value and previous output.

The other unknown is how the signature is generated, since there must be someway to verify it, but no public key or any detail at all regarding the type of signature is listed. It is a 2048 bit value, so RSA is quite likely, possibly even generated by the same private key for their SSL traffic. I would hope that is not the case, when the key expires later this year, it may be difficult to verify previous outputs, as the old public key would need to be found.

Also, the page is encrypted using CBC mode using TLS 1.0, which means the connection is potentially vulnerable to tampering by a 3rd party while in transit. This type of service should be as invulnerable to tampering as possible with current technology and standards, and is not. This is not a problem with the service itself, just in how the service is accessed. The page accesses an XML formatted entry using AJAX on the same server, secured with the same protocol and key.

Acceptance is also dependent on public trust in the security of SHA-512, the methods used to measure the unpredictability of quantum behavior, and the methods described in SP800-90A for turning those measurements into random bits. SP800-90A is the publication that describes Dual EC DRBG....

Updates to the service as of March 2018

As mentioned above, the private key for their SSL traffic expired in 2014, at that point they got a new cert, and have since posted the specific certificate used to sign beacon data. That cert (2048-bit RSA, SHA256 hash) was valid for 3 years, and expired May 7th 2017. It is downloadable for verification of prior data, and they list the new public key used to sign current beacon data, but it is not a certificate and thus not signed with a root cert.

The new public key is 2048-bit RSA with 65537 as the exponent, same as in the previous certificate.

Their SSL traffic is now secured with TLS 1.2, the specific ciphersuite used is TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA. That cert has a 1 year validity, and is also 2048-bit RSA.

Their schema has been updated, and no longer references randomValue or previousHashValue. The XML records from the beacon match the schema correctly.

The service is still listed as a prototype, and they note that a new version of the beacon is in development, however there have been no updates since the last page edit on May 13th 2014.

Updates to the service as of October 2019

In June 2018, the service officially left prototype status and entered beta, using the "new version" I referenced earlier, which is now referred to as version 2.0. The new XML Schema file is fairly well documented. It appears the new beacon went online July 23rd 2018.

I was able to determine that the certificate used to sign the beacon output changed on pulse 502025, which occurred on August 16th 2019. The status of the pulse correctly specify a gap in the beacon output occurred (it was 3 minutes), with a code of 6 for certificate change, although this code is not listed in the XML Schema file. The prior certificate actually expired on January 11th 2019 and was used for an additional 7 months 5 days.

The current and prior certificates are easily obtainable from the service interface. Both were issued by DigiCert Global CA G2. The new public key is 4096-bit RSA with 65537 as the exponent.

Their SSL traffic is still secured with TLS 1.2 on my system, the specific ciphersuite used is now TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384. That cert has a 1 year validity (expiring November), and is still 2048-bit RSA. It is also issued by DigiCert, but is a common web server certificate for 14 separate NIST subdomains, including NVD and CSRC.

In May of 2019, they published a draft reference for randomness beacons, of which the version 2.0 service is an implementation of, as Internal Report 8213. This is an extremely detailed report of the design and implementation of the beacon system, and includes a security analysis with multiple threat assessments.

There are a few important changes with version 2.0 that are worth mentioning, the first is that they now have published block diagrams of how the system works, make note that although RNG3 is listed as quantum, the beacon project website specifies "We may soon integrate in the NIST Beacon a PML-developed quantum RNG (identified in the figure as #3) based on photon detection", implying that RNG3 is not currently active:

The next important change is how the hash chains are built, and the addition of the skip list. I have not verified the complete operation of the skip list, but it would appear to use the 1st hour/day/month/year as the anchor point for a hash chain, so it is much faster to audit the current beacon to the start of the chain, which could be years long.

Now instead of going back half a million hashes to go back a year, you simply go back to the start of the hour, then back by hours to the start of the day, and so on until the chain is verified back to the first minute of the first hour of the first day of the year, with a maximum of 124 verifications to go back to the beginning of the current year.

So to verify pulse 502025 (Aug 16th 2019, 14:14 Z) against the start of the month pulse of 479573, you skip back 15 minutes to 502013, then in 14 skips of an hour (60 pulses) back to 501173, then in 15 skips of a day (1440 pulses) to 479573, for a total of 44 verifications, compared to 22453 without the skip list feature.

The final point of note is that this is not the only implementation of the version 2.0 beacon technology, there are services run by the University of Chile and government of Brazil. In addition to a hardware RNG, the Chilean beacon uses entropy sources gathered from seismic measurements in Chile, a stream from a local radio station, a selection of Twitter posts, and data from the Ethereum blockchain. Brazil actually runs multiple beacons, including their primary which uses a photonic quantum TRNG, as well as a combination beacon which also includes the outputs of the Chilean and NIST beacons as sources of entropy. The output of the Chilean beacon is also one of several inputs to Cloudflare's own beacon, which is not based on the NIST design or API.

At this point, the design seems sound, and if they fix the cert issues and get RNG3 active (maybe it already is), this and others like it do appear to have many uses, although cryptographic use may not be one of them, except as an additional source of entropy and not as a primary source.


Let $(\mathsf{Enc},\mathsf{Dec})$ be an authenticated encryption scheme, i.e. it is both IND-CPA secure and INT-CTXT secure (and thus by extension IND-CCA secure). Let $\mathcal{M}$ be the message space of this encrytion scheme and let $\hat m\in\mathcal{M}$ be an arbitrary fixed message.
Now construct the symmetric encryption scheme $(\mathsf{Enc}',\mathsf{Dec}')$ with $\mathsf{Enc}'=\mathsf{Enc}$ and $\mathsf{Dec}'$ defined as
\begin{align*}
&\underline{\mathsf{Dec}'(k,c)}\\
&m := \mathsf{Dec}(k,c)\\
&\textrm{if } m = \bot\\
&\quad \textrm{return } \hat m\\
&\textrm{else}\\
&\quad \textrm{return } m
\end{align*}
It is easy to show that this scheme remains IND-CCA secure. The reduction to the IND-CCA security of $(\mathsf{Enc},\mathsf{Dec})$ merely needs to replace all $\bot$-responses of the decryption oracle with $\hat m$.
At the same time, it is trivial to break INT-CTXT security of $(\mathsf{Enc}',\mathsf{Dec}')$ by simply presenting literally anything as a ciphertext.
This means that if secure authenticated encryption exists, there also exists IND-CCA secure encryption that is not INT-CTXT secure.


Here is a small scheme how this works :

 Server         Client
   |              |
   |     r,n      |  S: Find s such as HMAC(s,r) = xxxx0000
   |  ==========> |
   |              |  C: *compute HMAC(0,r) = 123456789*
   |              |  C: *compute HMAC(1,r) = 124687946*
   |              |  C: *compute HMAC(2,r) = 164946518*
   |              |  C: *compute HMAC(3,r) = 165498451*
   |              |  ...
   |              |  C: *compute HMAC(42,r) = 16540000*
   |              |
   |    s = 42    |  C: Found it ! s is 42
   | <=========== |
   |              |  S: *compute HMAC(42,r) = 16540000*
   |      OK      |  S: Ok, access granted for you !
   |  ==========> |
   V              V

As an example, lets assume you want only the last digit to be 0.
What are the chances if you were to compute the HMAC for a random number ? well $\frac{1}{10}$. So if you try 10 random numbers, the chances that you got at least one HMAC ending with 0 is pretty decent:

$P = 1 - ((1-\frac{1}{10})^{10}) \approx 65\%$.

However, the more 0 you ask at the end the harder it will be to find a solution. e.g. if you were to ask for 4 zeroes at then end, the chances that you would find $s$ after 1000 trials are :

$P = 1 - ((1-\frac{1}{10000})^{1000}) \approx 9,5\%$.

And after 10000 trials :

$P = 1 - ((1-\frac{1}{10000})^{10000}) \approx 63\%$.

Thus simply by increasing the number of zeros demanded, you increase a lot the time required to find the solution.

Why it is "secure", because you change the $r$ at each tentative. Therefore the client cannot pre-compute the solution.


Necessary conditions for construction of $n$ to $p(n)$ pseudorandom generators from $n$ to $n+1$ generators?

It is not necessary, that $G_1$ is a PRG.

Let $G_2: \{0,1\}^{n-1} \rightarrow \{0,1\}^n$ be a PRG, define $G_1: \{0,1\}^n \rightarrow \{0,1\}^{n+1}$ as
\begin{align*}
G_1(s_1||\ldots||s_n) := 1||G_2(s_2||\ldots||s_n).
\end{align*}
and consider the distinguisher $\mathcal{D}_1$, which returns the first bit $w_1$, when given the $n+1$ bit string $w := w_1||\ldots||w_{n+1}$ as input.

For $s_1 \leftarrow \{0,1\}^n$ and $r_1 \leftarrow \{0,1\}^{n+1}$ we have
\begin{align*}
\Big|\text{Pr}[\mathcal{D}_1(G_1(s_1))=1] - \text{Pr}[\mathcal{D}_1(r_1)=1]\Big| = \Big|1 - \frac{1}{2}\Big| = \frac{1}{2} > \mathsf{negl}(n),
\end{align*}
which implies that $G_1$ is not a PRG.

Nevertheless, we can still prove, that $G$ is a PRG, by using a slight modification of Katz' and Lindell's proof for theorem 6.20 in "Introduction to Modern Cryptography". (I assume you are familiar with it, since you are using the exact same notation.)

We construct a distinguisher $\mathcal{D}_2$ for $G_2$ using another distinguisher $\mathcal{D}$ for $G$, with
\begin{align*}
\Big|\text{Pr}[\mathcal{D}(G(s))=1] - \text{Pr}[\mathcal{D}(r)=1]\Big| =: \epsilon(n).
\end{align*}

Let $\mathcal{D}_2$ behave as follows, when given a $w := w_1 || \ldots || w_n \in \{0,1\}^n$ as input.

$i \leftarrow \{0, \ldots, p(n) - 1\}$
$r \leftarrow \{0,1\}^i$
$p := G(1||w)$
Construct a bit-string $w'$ as the concatenation of $r$, $w_{n}$ and the first $p(n) - i - 1$ bits of $p$.
Output $\mathcal{D}(w')$

You can easiliy verifiy the following two statements:

If $i = 0$ and $w = G_2(s_2)$ for $s_2 \in \{0,1\}^{n-1}$, then $w' = G(s)$ for $s = b||s_2$ and $b \in \{0,1\}$.
If $i = p(n) -1$ and $w = r_2 \leftarrow \{0,1\}^n$, then
$w' \leftarrow \{0,1\}^{p(n)}$.

Using the same argument as Katz and Lindell, we obtain
\begin{align*}
\mathsf{negl}(n) \geq \frac{\epsilon(n)}{p(n)} && \Longrightarrow && \mathsf{negl}(n) \geq \epsilon(n),
\end{align*}
which means, that $G$ is a PRG.

Similar arguments apply to your other two questions.


What is the main difference between a key, an IV and a nonce?

A key, in the context of symmetric cryptography, is something you keep secret.  Anyone who knows your key (or can guess it) can decrypt any data you've encrypted with it (or forge any authentication codes you've calculated with it, etc.).
(There's also "asymmetric" or public key cryptography, where the key effectively has two parts: the private key, which allows decryption and/or signing, and a public key (derived from the corresponding private key) which allows encryption and/or signature verification.)
An IV or initialization vector is, in its broadest sense, just the initial value used to start some iterated process.  The term is used in a couple of different contexts and implies different security requirements in each of them.  For example, cryptographic hash functions typically have a fixed IV, which is just an arbitrary constant which is included in the hash function specification and is used as the initial hash value before any data is fed in:

Conversely, most block cipher modes of operation require an IV which is random and unpredictable, or at least unique for each message encrypted with a given key.  (Of course, if each key is only ever used to encrypt a single message, one can get away with using a fixed IV.)  This random IV ensures that each message encrypts differently, such that seeing multiple messages encrypted with the same key doesn't give the attacker any more information than just seeing a single long message.  In particular, it ensures that encrypting the same message twice yields two completely different ciphertexts, which is necessary in order for the encryption scheme to be semantically secure.
In any case, the IV never needs to be kept secret — if it did, it would be a key, not an IV.  Indeed, in most cases, keeping the IV secret would not be practical even if you wanted to since the recipient needs to know it in order to decrypt the data (or verify the hash, etc.).
A nonce, in the broad sense, is just "a number used only once".  The only thing generally demanded of a nonce is that it should never be used twice (within the relevant scope, such as encryption with a particular key).
The unique IVs used for block cipher encryption qualify as nonces, but various other cryptographic schemes make use of nonces as well.
There's some variation about which of the terms "IV" and "nonce" is used for different block cipher modes of operation: some authors use exclusively one or the other, while some make a distinction between them.  For CTR mode, in particular, some authors reserve the term "IV" for the full cipher input block formed by the concatenation of the nonce and the initial counter value (usually a block of all zero bits), while others prefer not to use the term "IV" for CTR mode at all.  This is all complicated by the fact that there are several variations on how the nonce/IV sent with the message in CTR mode is actually mapped into the initial block cipher input.
Conversely, for modes other than CTR (or related modes such as EAX or GCM), the term "IV" is almost universally preferred over "nonce".  This is particularly true for CBC mode since it has requirements on its IV (specifically, that they are unpredictable) which go beyond the usual requirement of uniqueness expected of nonces.


You're correct, the proof isn't precisely correct, because we don't necessarily have $c^{\phi(n)} = 1$, specifically in the case $c \equiv 0 \pmod p$.

Here is a more correct approach; we have $c^1 \equiv c \pmod p$ (trivially), and $c^{p-1} \equiv c \pmod p$ for any $c$, prime $p$ (Fermat's little theorem [1]).  By induction, we get $c^{k (p-1) + 1} \equiv c^1 \pmod p$ (for any $k$), and hence $c^{k (p-1) + \ell} \equiv c^\ell \pmod p$.

If we designate $x = k(p-1) + \ell$ for $0 \le \ell < p-1$ (and any $x$ can be put in that form), we have $c^x \equiv c^{x \bmod p-1} \pmod p$, for any $x, c$ and prime $p$; in particular, if $x = d$

[1]: The most common expression of Fermat's Little Theorom is that $1 \equiv x^{p-1} \bmod p$ for prime $p$, $x$ relatively prime to $p$.  However, an equivalent formulation (and what Fermat originally stated) is that $x \equiv x^p \bmod p$ for prime $p$, any $x$ - I'm using this alternative formulation.


What are the consequences of removing a single byte from a sha256 hash?

Does this bias the hash in any way?

We want the avalanche criteria on the output bits, that is a change in the any of input bit must randomly affect half of the output bits. Each bit of the hash function must depend on the input bits; removing one bit doesn't affect the others.

  My assumption is this would decrease the computational power needed to reverse the hash by 1/256th. Is that correct?

First of all, hash functions are not really reversible since they are compression functions, that is, they map from a large input space to a shorter space.

$$ H:\{0,1\}^* \rightarrow \{0,1\}^l$$

If we want to talk about collision resistance, see the next answer.
For generic pre-image search, yes; it will decrease the computational power, as you noted.

  My assumption is this would increase the likelihood of a hash collision by 25600%. Is that correct?

Collision resistance is measured by the generic birthday attack, that is, $\sqrt {2^l}$, $l$ being the output size of the hash function. SHA256 has $\sqrt {2^{256}} = 2^{128}$ generic birthday attack time.

In your case we will have $\sqrt {2^{256-8}} = 2^{124}$ as generic birthday attack time. Thus, we have a $2^{4}= 16$ speed-up in the attack time.

TL;DR: Truncating the hash to 31 bytes will be safe (see also this stack exchange answer

Note 1: Bitcoin miners reached $\approx 2^{92}$ SHA-256 hashes per year in 06 Agust 2019..

Note 2: SHA-224 defined in FIPS180-4 is calculated by truncating the SHA-256 hash value with using different initial constants for domain separation so the value is not the same as the first 28 bytes of the SHA-256 value.


Secure Key exchange using javacard applet

Both RSA and DH have a similarity which is the Modulus Exponential (modexp) function (RSA encrypt/decrypt function). Since both RSA and DH uses the same modexp function, you can make full use of the Cipher for ALG_RSA_NOPAD in JavaCard's crypto API.

I have sat down and taken time to adapt the RSA crypto functions for traditional non-ECC type of DH functions and you can find the open source applet code here (https://github.com/ASKGLab/DHApplet/blob/master/src/dhapplet/DH.java).

I have not yet done up the APDU commands to create a full fledge demo but I guess if you study the DH.java codes, it should be more than enough to give you a head start. I have included a ton of commends in the source code on how to adapt it to different scenarios and the thought process as well when designing the entire DH class and it's significance.


Generating a key pair using a signature generated by an existing key

Several issues with the proposition of generating a derived private/public key pair as (or from) a signature computed with a master private key.

Not all signature schemes are deterministic, thus what's proposed might end up not allowing reproduction of the derived key.
We would need to discriminate the particular message input to the signature scheme used to generate the derived key, and ensure that an adversary can not obtain the signature of that message with the master key, thus ruining the confidentiality of the derived key.
For arbitrary signature scheme, we could imagine some security issue where signatures (past and future) with the master key weaken signatures with the derived key.

A more conservative option is to use the master private key itself as the key input of a symmetric Key Derivation Function (unrelated to the signature scheme), which output is (or is used to deterministically generate) the derived key. This can be generalized to any number of derived keys, using an auxiliary input of the KDF for a derived key type or index. That option assumes that the master private key is not in a box/HSM/Smart Card/enclave restricting its use to signature, and that a strict policy to the same effect is not in force (which is common, e.g. by reference to FIPS 186-4).

Update: a comment mentions that the master private key is not directly accessible (making the above conservative option impossible); and a deterministic (variant of) ECDSA.

If we can reserve a message $C_D$ (solving 2.), post-processing as$$\text{DK}\gets(H(\text{Sign}_\text{MK}(C_D))\bmod(n–1))+1$$seems to be good way to derive a private key $\text{DK}$ from master private key $\text{MK}$, with $n$ the generator's order and $H$ a hash at least 64-bit as wide as $n$ is. The modular reduction and 64-bit limit is per FIPS 186-4 apendix B.4.1. If $H$ is secure in the Random Oracle Model and as costly as a signature verification, then this is computationally secure (argument: an attack allows to forge the signature of $C_D$, or otherwise breaks the signature scheme, or the hash). It can only help to use a purposely slow KDF for $H$.

The above formula assumes ECDSA with only the signature TRNG changed to a deterministic PRF keyed by the private key. For EdDSA, we only need to hash the signature of the reserved message $C_D$ to the width of a private key, and condition that with the masking prescribed in EdDSA.

More generally, with a deterministic signature scheme, a reserved message, and a key generation procedure using a KDF independent of the signature scheme and at least as costly as signature verification, we are good to go.

Caveat: any key derivation should be performed in a safe environment, or otherwise guarded from side channels.


From a cryptographic standpoint (ignoring implementation issues and password sniffing), the security depends primarily on the entropy $s$ in the password, and the number $n$ of iterations in PBKDF2. Work to break is about $n\,2^{s-1}$ SHA-256 (for large $n$).

Per the obligatory XKCD, a good password has like 44 bits of entropy; a bad password (among the 1000 most common) like 10 bits.

According to that source, $n$ was $10^4$ in iOS 4.x; I'll use $n=2^{16}$ (6.5 times more).

Thus the effort to break the system is like $2^{25}$ to $2^{60}$ SHA-256.

$2^{25}$ SHA-256 is very easy. $2^{60}$ is considerable, but feasible for an entity like the NSA if it decides to invest in the necessary hardware (ASICs specialized in cracking PBKDF2). As a comparison, according to this source, bitcoin miners currently hash at a rate of $10^{19}$ SHA-256d per second, where one SHA-256d is two SHA-256; that is over $2^{70}$ SHA-256 per minute.

Nowadays, if something is protected only by a password, and can be accessed on a mobile device, and the key stretching step uses PBKDF2 without the hash in hardware, and the password is of average quality, likely it could be broken. For something safer, we want scrypt or Argon2, that leverage RAM to make the investment in a password cracker much higher; or an exceptionally good password.


Are the first 4 bytes of a Ed25519 public key random?

If the 32-bit ids are assigned independently, the best you can hope for with a uniform random assignment of ids is a collision probability no more than about $n^2/2^{32}$ where $n$ is the number of ids you have, if $n$ is small; once $n$ grows past $2^{16}$ the probability of a collision rapidly approaches 1.  This is the standard birthday paradox.

Using a nonuniform distribution on ids is even worse.  The distribution of bits in the encoding of uniform random curve points is detectably nonuniform—enough that it was one of the first problems reported in Dual_EC_DRBG before everyone realized there was a back door.  The low-order 32 bits are probably close enough to uniform in this case that it won't affect the collision probabilities; to alleviate that concern you could pass the encoded curve point through a hash like SHAKE128-32 first.

But you should be more concerned with what you hope to achieve using 32-bit ids in the first place!  This has been a consistent source of trouble in OpenPGP, for example—fraudulent keys have been forged and uploaded to the key servers for every 32-bit key id possible.  To avoid this trouble, you fundamentally need to:

make the id assignments non-independent, e.g. use a secret permutation of 32-bit strings so that you can have up to four billion ids
use a much larger id space, e.g. 256 bits
accept that collisions will happen and find a way to deal with them gracefully, even under adversarial inputs that are all collisions


Is there a difference between password and key?

Passwords or pass phrases are basically a human equivalent of keys used by algorithms on computers. However, because of that passwords also carry a lot of burden that make them unsuitable as keys:

they are generally much less random than they symmetric key counterparts, because humans are quite incapable as random number generators;
they may be dynamically sized, which makes them unsuitable for many cryptographic algorithms;
they often use a specific set of characters (al alphabet) of their own;
they can be converted to bytes in many ways, if just because there are many character encodings;
the chances of reuse are rather high, so the leaking one password may influence security of many systems.

Generally cryptographers use a PBKDF or password hash to create a statically sized, random byte array from a password. This byte array can then be used as a key, or it can be used to authenticate a person on e.g. a webservice.

These PBKDF's strengthen or stretch the security of the password by a certain work factor. This work factor is usually represented by an iteration count or by a value that is converted into an iteration count (bcrypt uses a work factor which is exponential).

Furthermore, they require a salt to avoid that the same password will create the same hash, even on multiple systems. Because of this rainbow table attacks can be avoided.

Other configuration parameters such as deliberate use of more memory to avoid attacks by specialized hardware or GPU based systems may also be present. See e.g. scrypt. Another common configuration parameter is to allow multiple threads to calculate a single password; it doesn't seem used much.

One configuration parameter that is often missing because it is simply implied is the character encoding. Quite often initial operation to convert characters to bytes is the cause of interoperability issues. Some PBKDF's are also limited to the amount of input bytes (e.g. some bcrypt implementations limit to 72 bits, which can be problem for passphrases).

OpenSSL uses its own PBKDF called EVP_BytesToKey. It uses a rather insecure iteration count of 1, which means that no real strengthening is performed. Furthermore, it also uses a salt, which is stored in the positions 8..15 of the ciphertext, preceded by a magic value "Salted__" in ASCII (take a look at the head of your ciphertext!). You may have to decode the base 64 first though (or compare against U2FsdGVkX1 at the start, most of Salted__ encoded).

The salt is generated during encryption, and with the iteration count it is able to derive a key, which is used to encrypt your plaintext. During decryption the salt is read so it is able to derive the same key - but only if you give it the correct password of course. Once the key is calculated again it can decrypt the ciphertext.

Newer versions have an option to use PBKDF2 instead. This algorithm doesn't disallow hackers to use specialized hardware, but it is at least more secure than the original EVP_BytesToKey with an iteration count of 1.

Neither the password or key is stored with the ciphertext. The password is supplied by the user, the key is derived from that password and the salt.

Note that the ciphertext allows an attacker to perform a so called offline attack, where all computing resources can be used on the ciphertext to try and get to the password by guessing it (using dictionary attacks and such). This is different from web services that can e.g. include a timeout between tries or only allow a certain number of guesses - as long as the password hash is kept secret.

A much more secure way of encrypting files is to use a trusted public key of the receiver. Then the receiver can use their private key to decrypt the ciphertext. Commonly this is used in a hybrid cryptosystem that uses both asymmetric cryptography and symmetric cryptography. However, it does require that the public key can be trusted, so you need a Public Key Infrastructure of some kind to trust the keys. This is what e.g. PGP uses for file encryption.

Often a password may still be used, but that's just to decrypt the private key, and the private key is usually kept on the system of the user, so it isn't available to adversaries.


UMAC: to what extent is it in use today?

UMAC is described in full details in RFC 4418.

When the RFC talks about "secret selection", it really means "there is a secret key involved here". UMAC works with universal hashing, which can be viewed as a family of hash functions, and a key which selects which hash function we are talking of. The term "hash function" might be a bit confusing here, because this is not at all the same kind of beast than, say, SHA-256. These "hash functions" would be utterly weak if left alone in the wild.

So UMAC works like this:

There is a nonce which must be used only once; for each new message a new nonce value must be selected (this is extremely important).
There are two keys $K_1$ and $K_2$. $K_1$ selects the universal hash function $h$ in its family, while $K_2$ is used in a suitable function which can operate on a block; namely, the AES or another block cipher.
The input message is processed with $h$, and the output of $h$ is then encrypted by XORing it with $\mathrm{AES}_{K_2}$ (nonce)_.

The idea is that the hash function $h$ (selected by $K_1$) remains "hidden" by the final encryption. Thanks to the nonce, and assuming that the final encryption is decent, successively MACed messages leak no information whatsoever on $h$ to the attacker. This is valid even in the presence of a very lightweight $h$, much faster than a conventional hash function.

UMAC is not much used by itself, because it is quite recent, and the nonce is a hard requirement, quite similar to IV management for block ciphers. HMAC is much easier, in the sense that it is much harder to get it wrong. UMAC or UMAC-like systems are however quite popular when integrated with encryption, because the nonce/IV requirement can then be shared. This is how OCB and GCM work, for instance.


Is Base64(SHA1(GUID)) still unique like the original GUID?

Base64 provides a 1:1 transform from input to output (and back again if desired). So if you take a set of unique items and base64 encode all of them they will all be unique.

So the question becomes if you run a GUID through SHA1, will the resulting hash have the same uniqueness as the GUID?

The answer is practically - yes; theoretically not quite. Multiple inputs to SHA1 map to the same output, but in reality if your GUIDs are unique then there is negligible probability that there will ever be a collision leading to loss of uniqueness.


Why does orthogonal basises makes it easier to solve SVP in lattices?

Is it only because it somehow makes it easier for algorithms such as LLL(-BKZ) to reduce the basis vectors?

You have this somewhat backwards --- the point of basis reduction is to find a basis that is "shorter" and "more orthogonal", which you then use for useful applications.
Babai's nearest planes is a fairly well-known algorithm to solve an approximate form of CVP, that is defined relative to some fixed basis $B = [b_1,\dots,b_n]$ of a lattice.
If $x\in\mathbb{R}^n$, and:

$v$ is the output of Babai's nearest planes, and
$v_{opt}$ is the closest vector to $x$,

then one can prove that:
$$\lVert v-v_{opt}\rVert_2^2 \leq \frac{1}{4}\sum_{i = 1}^n \lVert b_i^*\rVert_2^2$$
where $\{b_1^*,\dots, b_n^*\}$ is the Gram-Schmidt orthogonalization of $B$.
Note that as the Gram-Schmidt orthogonalization applies solely elementary operations, one has that:
$$\det([b_1^*,\dots, b_n^*]) = \det B$$
e.g. the total product $\prod_{i=1}^n \lVert b_i^*\rVert_2 = \det B$ is kept invariant.
It should be easy to see that the error bound in Babai's nearest planes will be minimized if this "$\det B$ amount of mass" is "spread out evenly" through all of $\{b_1^*,\dots, b_n^*\}$, e.g. if the basis is short and nearly orthogonal.


Encryption and decryption of Request and response for REST API

In case you want to use AWS KMS without the raised issues, you can use AnonyFlow API for encryption/decryption. it is using the AWS KMS in the background and manage the private keys for you in order to avoid the keys issues you have raised, therefore you enjoy the service without worries.
It's very easy to consume the api, you can use the anony-value for encrypting one or more string values (string array) or use the anony-packet for encrypting json data - you can even define specific keys in order not to encrypt the entire json.
the best practice would be to consume it in your server side code. you can even create a serverless service on aws or any other platform to handle it.
Disclosure: I'm part of AnonyFlow creators.


Is this approach to generating a "random" number from a sha512 hash effective?

In general, your way to select one of the entries seems unnecessary complicated. As fgrieu pointed out, you should be fine by reducing the hash value modulo the number of participants (But with $n$ people, you calculate $h$ mod $n$, and assign the numbers from $0$ to $n-1$).

An important question though, is how you determine the input to your hash function. If you seed it with something random, people can't really be sure you didn't cheat (by trying out different seeds).

In order to provide confidence, you might want to do something like this:

Initially you provide a commitment to some secret value of your choice. After everything is done, you can unveil the commitment and show the secret value.
Then you run your raffle. People can sign down their names, and you keep the list public. This way they can make sure that their name is in the raffle. The list index also gives the "lucky number" to each participant.
Afterwards you first reveal the secret value by publishing the decommitment. Then you create a long bitstring: concatenate all the names in the list and the secret value. Use this bitstring as input to a hash function (SHA512 does the trick, but with an final result  of at most $2^8$ possibilities, any cryptographic hash function should work). Calculate the number modulo the number of participants. If you want results from $1$ to $n$ instead of $0$ to $n-1$, then just add 1 (or interpret the $0$ as $n$).

Why can no one cheat in this scenario?

You can't cheat, because your input to the function is fixed before the raffle starts (at least if your commitment scheme is binding; btw. you can also just use something like "I encrypt my name with AES. The commitment is the ciphertext and the secret value is the used key")
The other people can't cheat either, because without knowledge of your input they should not be able to change the outcome in their favor on purpose.
Since the growing list of names changes with each additional entry the hash result, no one could predict the outcome before the last person entered his name.
The worst attack scenario I can think of, is that you work together with the last person added to the list. This person could try out different variations of his name and calculate the result with knowledge of the secret. But right now I can' think of anything to solve this problem.


Is deriving the IV from the password secure?

Yes, it is. PBKDF2 derives a DK, a "derived key", which is indistinguishable from random. This is mainly because function within PBKDF2 is HMAC, and HMAC is a PRF. Let's see the definition from Wikipedia:

  In cryptography, a pseudorandom function family, abbreviated PRF, is a collection of efficiently-computable functions which emulate a random oracle in the following way: no efficient algorithm can distinguish (with significant advantage) between a function chosen randomly from the PRF family and a random oracle (a function whose outputs are fixed completely at random).

This also means that the bytes of the derived key are independent, even from each other. So that means that as long as separate bytes from the output are used, we can split the DK value into a key and an IV.

Now, fortunately, the scheme provided uses SHA-512 as the underlying hash function. This means that no additional calculations need to be performed if we require 256-bit key material and 128 bit IV material.

If the SHA-256 hash would have been used the PBKDF2 function would require an additional run. Unfortunately, in the scheme above, an attacker would not have to perform such an additional run. This is because the attacker only has to verify the key; it can calculate the IV when it finds the key. So using a smaller hash function requires a lot more operations for the legit user, while not giving any security advantage. This is a bad property for a PBKDF - which unfortunately is present for PBKDF2.

So as long as your key and IV stay below the output size of the hash the scheme above is secure.

If you'd ever required more output than the single hash requires then it is possible to perform additional calculations using a key based key derivation function (KBKDF) such as HKDF. In that case, a good scheme would be:

derivedKey = PBKDF2(password, salt)
key = HKDF(derivedKey, "Key")
iv = HKDF(derivedKey, "IV")

That the scheme is secure doesn't mean that it is optimal. You could think of using a memory hard PBKDF such as scrypt or one of the newer Argon2 variants instead of PBKDF2. You might also have a look at authenticated ciphers such as GCM to add integrity and authenticity to your ciphertext.

Of course, the scheme does depend on the salt being a secure random value. Please make sure this is the case, otherwise, you may end up with a repeating key, IV for identical passwords, destroying security.

A high number of iterations (the "work factor") for PBKDF2 makes it harder to attack relatively weak passwords (and most passwords are relatively weak).


Pollard's Kangaroo-- What is the failure probability (assuming random functions)?

Edlyn Teske has had a look at this question in her paper, specifically in section 6.3. I restate it in your notation:

  Kangaroos running in cycles During a kangaroo's travel, there is a possibility that the sequence of its spots beomes periodic. While cycles are the ultimate goals in the rho method, they
  do not reveal any information about $x$ (the discrete log) in the kangaroo method. [..] They don't find new distinguished points, they slow down the algorithm and even might cause it to fail.

  We show that if $w\leq  order(g)/4$, this is very unlikely to happen. As before, we first assume that
  we have only one tame and one wild kangaroo and that we work with jump distances of mean value $\beta=\sqrt{w}/2.$

She is looking at parallelization, but the above is for the non-parallel method. She then proves that the probability $\mathbb{P}$ that a kangaroo ends up in a cycle before a useful collision has occured is upper bounded by
$$
\mathbb{P}\leq \exp(-(4n/w)-2),
$$
where $n$ is the order of $g,$ in the discrete log problem $h=g^x$ under consideration.

Furthermore, Teske remarks that assuming uniformity of DL values, this bound can be tightened.


Just stick to the standard algorithm, also remember that you are working in $\mathbb{Z}_p^*$.

Select $q$ with at least $2k$ bits, that means you are targeting $k$ bits security. In the RFC at least 160 bits is recommended for $q$. In addition select a prime $p$ with at least 1024-bit.

Regarding the generator, we know that every generator will generate the subgroup of order $2q$ or $q$. The reason that $g=2$ is chosen is that is desirable for faster computations of modular exponentiation.

You will find all the information regarded to Diffie-Hellman implementation in RFC. Also there's a method for generating $p$,$q$ and alternatively $g$, if desired.


Show How to Efficiently Solve the Computational Diffie-Hellman Assumption given an Algorithm that Solves the Square-DH Problem

This is a reduction showing that if you can compute $g^{a^2}$ given $g^a$, then you can solve the computational Diffie Hellman problem. Here is the reduction.

Let $A$ be an adversary that given $g^a$ for a random $a$, outputs $g^{a^2}$ with probability $\epsilon$. We construct $A'$ who receives $u=g^a$ and $v=g^b$ and works as follows. $A'$ runs $A$ three times on input $u$, on input $v$ and on input $u\cdot v$. If $A$ returns a correct answer each time then $A'$ will have $A=g^{a^2}$, $B=g^{b^2}$ and $C=g^{(a+b)^2}=g^{a^2 + 2ab + b^2} = g^{a^2}\cdot g^{b^2} \cdot g^{2ab}$. Thus, $A'$ outputs $\sqrt{\frac{C}{A\cdot B}}$, where the square-root is of course modulo $p$.

It remains to compute the probability with which $A'$ succeeds. Naively, we would like to say that since $A$ has to succeed on all 3 inputs, $A'$ succeeds with probability $\epsilon^3$. The problem is that the inputs given by $A'$ to $A$ are not independent. This is solved by having $A'$ choose random $r$ and $s$ in ${\mathbb Z}_p^*$ and giving $A$ the inputs $g^{ra}=u^r$, $g^{sb}=v^s$ and $u\cdot v$. This will ensure that all inputs are completely independent. Now $A'$ outputs $\sqrt{\frac{C}{A^{1/r^2}\cdot B^{1/s^2}}}$ and this will be correct with probability $\epsilon^3$.

We conclude that if the original problem can be solved with non-negligible probability then so can the computational Diffie-Hellman problem.


Mapping of message onto elliptic curve and reverse it?

When using ElGamal on elliptic curves you have two possibilities:

Encoding free Version of El Gamal

Use a version of ElGamal such as "hashed ElGamal" that avoids the task of mapping
messages to points on the curve. In standard ElGamal on elliptic curves you would compute
the ciphertext as $(C_1,C_2)=(kP,M+kY)$ where $k$ is a random integer, $M$ the message $m$
mapped to a point on the curve, $Y$ the public key and $P$ the generator point.

In hashed ElGamal, the ciphertext is $(C_1,C_2)=(kP,m\oplus H(kY))$ where $H:G\rightarrow \{0,1\}^n$
is a hash function that maps points on the curve to $n$ bit strings. Consequently, you can encrypt $n$ bit
messages, for instance 256 bit if you use SHA-256 for $H$. For the input to $H$ you need to encode the points of the curve in a suitable way.

What you describe in your question, i.e., encode $m$ as $mP$, is also known as exponential ElGamal and typically
used to make it additively homomorphic. But in this case, you have to compute discrete logarithms after decrypting.
Note that decryption will yield $mP$ and you have to compute $m=\log_P mP$ which means you have to solve the elliptic
curve discrete logarithm problem. This is only practical for small messages.

Map Messages to the Curve

A standard probabilistic encoding that can be used for curves over $\mathbb{F}_p$ (for a large prime $p$) is that you fix some value $\ell$,
for instance half the bitlength of $p$, and then simply choose a random integer from $\mathbb{Z}_p$ and set the least
significant bits of this value to represent your message, i.e., you have a value $r\|m$. Then, treat this value $r\|m$ as the $x$ coordinate of a (potential) point on the
curve (in affine coordinates). If it is on the curve, take one of the two possible $y$ values and you have your encoding of the
message to a point. Otherwise, start over again
with a new $x$ value.

This is one probabilistic encoding and if you want to have injective maps that
are also efficiently invertible take a look here as pointed out in my comment.

Third possibility: Avoid ElGamal

As @poncho pointed out, you could simply replace ElGamal with another elliptic curve encryption scheme such as
ECIES. It is a hybrid encryption scheme and avoids
the task of mapping messages to points on the curve. In practice this seems to best solution if you want to use
your scheme simply for encryption (and do not need it as a building block in protocols which require proofs of
knowledge or stuff the like).


Is it possible to acquire the next keystream of Salsa20? (If you know part of the keystream)

It is impossible for computationally bounded adversaries
What you are looking for is impossible in modern stream ciphers. If ever one finds to break a stream cipher in this way, you will see in the cryptographic news!

but the keystream is 0x100000?

First of all, the keystream is too small to extract the key and IV, even there is an attack. There is a lot of occurrence of this keystream on the period of the Salsa20's keystream but you cannot reach them in your lifetime.
The expected period of Salsa20 (Oversimplified!):
The Salsa20's core function maps a 256-bit key, a 64-bit nonce, and a 64-bit counter to a 512-bit block of the keystream. So we have 384-bit random input and 512-bit output. If we assume that the output of the Salsa20 is a pseudo-random sequence with an output size of $n=512$-bit the expected period length will be  $\sum_{i=1}^n i/n = (n + 1)/2 \approx 2^{511}$ with the Harris' 1960 work. Salsa20, however, limited with the counter 64-bit. So can simply say that, a key with a nonce will not be periodic.
What is the expected occurrence on a pseudo-random sequence of size $2^{64}$? It is $2^{64}/2^{24} = 2^{40}$. So, for a single (key,nonce) pair, there is around $2^{40}$ occurrence of your string randomly sitting somewhere on the keystream. What is the following as the next bit? Nobody knows. For how many (key,nonce) pair you can store this to attack? And how you will be lucky that your target will be hot on your tiny list?
The next-bit test
This is more formal in the The next-bit test;

In cryptography and the theory of computation, the next-bit test is a test against pseudo-random number generators. We say that a sequence of bits passes the next bit test for at any position $i$ in the sequence, if any attacker who knows the $i$ first bits (but not the seed) cannot predict the $(i+1)$st with reasonable computational power.

If one computationally bounded entity can predict the next bit from the given bits, then this is a big problem for any stream cipher. There is no known such attack on Salsa20.
And, note that next-bit test is not sufficient, a non-Pseudo-Random-Sequence can pass the test.
Attacks on Salsa20
The best attack on the Salsa20

in 2008, New Features of Latin Dances (PDF) by Aumasson at al. They have shown 8 round attack on Salsa20/12 and 12 round on full Salsa20/20;

The other attacks;

in 2005, The paper Truncated differential cryptanalysis of five rounds of Salsa20 by Paul Crowley won Bernstein's US$1000 prize for "most interesting Salsa20 cryptanalysis"

in 2006, Fischer et al. in the paper Non-randomness in eSTREAM Candidates Salsa20 and TSC-4 demonstrated an attack on Salsa20/6 with estimated time complexity  $\approx 2^{177}$. They also showed a  related-key attack on Salsa20/7 with estimated time complexity $\approx 2^{217}$. The related key attacks are not important for the encryption, since the keys are selected randomly, it is important when uses in hash constructions.

in 2007, there is an attack on 8 rounds of Salsa20 in the paper Differential Cryptanalysis of Salsa20/8 by Tsunoo et al. This attack has no improvement over the brute force since they have $2^{255}$ complexity. In the same paper, they have also shown a related-key attack on the 7 rounds of the Salsa20 with $2^{117}$ complexity.

in 2012, Shi et al. improved the attack of Aumasson et al. on the paper
Improved Key Recovery Attacks on Reduced-Round Salsa20 and ChaCha. Note that the improvement is on 128-bit keyed Salsa20/7 with $2^{109}$ complexity time and on 256-bit keyed Salsa20/8 with complexity $2^{250}$.

in 2013, Mouha and Preneel gave proof on differential cryptanalysis. Towards Finding Optimal Differential Characteristics for ARX: Application to Salsa20. They showed that 15 rounds of Salsa20 are 128-bit secure against differential cryptanalysis. Their work proved that Salsa20 has no differential characteristic with higher probability than $2^{130}$, as a result, the differential cryptanalysis would be more difficult than 128-bit key exhaustive key search.

in 2018, it is shown that the Salsa20 has no integral distinguisher after 6 rounds, Finding Integral Distinguishers with Ease by Eskandari et al.

in 2020, Improved Related-Cipher Attack on Salsa20 Stream Cipher by Lin Ding. They demonstrated an attack on the use of two different IVs on the same key for Salsa20/12 and Salsa20/8 They can recover the 256-bit secret key with time complexity of about $2^{193.58}$. This is an improvement on the existing attack by a factor of $2^{30.42}$ This seems the best-realated cipher attack.


How to learn the first bit of m in padded RSA

I assume that this is a homework problem, and so I won't give you the answer.  However, here are a few hints:

What does 'it is a valid ciphertext' mean?
If $c$ decrypts to the value $m'$ (not counting the depad operation; that is, if $m' = c^{1/e} \bmod N\ $), what does $2^ec \bmod N\ $ decrypt to?  What is the relationship to those two values?


Risks of full length KCV (components and full keys)?

The usual (or at least traditional) blockcipher KCV is not a hash but rather the truncated encryption of zero; see How to obtain KCV from the key and KCV and compatibility with block cipher modes of operation

If 3DES (TDEA) key components K1,K2,K3 (i.e. single-length) (or their shares) are checked separately, a full-length (64-bit) check value on a 56-bit key component is practical to bruteforce, with small chance of ambiguity. Similarly for AES-128 where block size equals key size, if 2^128 bruteforce were practical you would be unlikely to get more than a very few candidate keys, which in most situations is a break. For a double-length or triple-length 3DES key, the key is longer than a (full) data block, by 48 or 104 bits; the former is probably safe and the latter definitely so.


Practical Uses for Timing Attacks on Hash Comparisons (e.g. MD5)?

There is no timing attack possible on MD5 as practically implemented on most platforms. That's because MD5 uses only 32-bit addition, 32-bit bitwise boolean operators, and constant rotations/shifts, which exhibit no data-dependent timing for any reasonable implementation, even written without consideration for resistance to timing attacks.

There is however a conceivable timing attack, unrelated to MD5, on the code shown (which is PHP, but that holds in many other languages, with minor variants), aiming at finding the first few characters of the hash value if that's unknown (the equivalent of the constant 550b1f8802ca3d7a987fc46a2af408c3 in the code sample). Assuming the string comparison of === is performed from left to right, character by character, and stopping on the first non-matching character, there can be a timing attack on the string comparison: if on average the password test1 (hashing to 5a1…) is rejected significantly slower than test0 (hashing to f6f…) and test2 (hashing to ad0…), then the true hash of the password can safely be assumed to starts in 5. We can then find and time the rejection of other test passwords which hash starts in 5 (like test8 hashing to 5e4…) to try find the second character of the hash; and so on. In this way we need to perform (significant) timing measurements for at most 32×16 well-chosen test passwords in order to find the whole hash.

That's fine in theory. In practice the attacker trying this will face at least two hurdles:

The difference in timing is very small, and a variety of things will conspire to mask it: network delays, other tasks and how they left the various CPU caches, numerous clocks on the hardware..; in order to make any progress, the attacker will need an awful lot of measurements, a direct network connection, a low-load server, and a sound strategy (like considering the average of observed times for a given test password after some setup-dependent filtering, perhaps keeping the few lowest measurements if all the accidental masking factors are additive).
Finding the leftmost $n$ characters of the hash requires about $2^{4n}$ evaluations of MD5 in order to find the test passwords to be timed; with $2^{60}$ evaluations (which is already requiring serious effort), the attacker only gets 12 characters (60 bits) out of 32 (128 bits).

If the first of these two hurdles can be overcome, the method has a benefit: the attacker can explore test passwords according to a synthesized list of candidate passwords approximately by decreasing likelihood, so that a low-entropy password will be found with (hopefully) fewer online queries to the server than without the timing attack; and no more offline hashes than required for a brute force attack with the hash known, even though the attack is performed without the hash.

I would be slightly surprised if that was a real threat for any server accessed through a few network hops; and I'm unsure this is worth academic publication in a first-tier conference or journal.


What you are wondering about is the difference between weak one-way function, and strong one-way function. Google should give you the definitions (e.g. here is the first link I found). The factoring function for general inputs is not a strong one-way function, since there are outputs for which it is easy to invert. But it is a weak OWF, because no polytime adversary can have more than a probability $1-1/\mathsf{poly}$ of inverting it (as far as we know).

Furthermore, even though a weak OWF is not a strong OWF in general, we know a generic way of building strong OWFs from weak OWFs - in other words, both assumptions are formally equivalent. See e.g. this online course, that deals specifically with the product function which you care about.


Short answer: 32 bytes of full-entropy key is enough.

Assuming full-entropy key (that is, each bit of key is chosen independently of the others by an equivalent of fair coin toss), the security of HMAC-SHA-256 against brute force key search is defined by the key size up to 64 bytes (512 bits) of key, then abruptly drops to 32 bytes (256 bits) for larger keys; that's because in the later case, the key is hashed to 32 bytes before use. It is an argument to use a 64-byte key: it's the size giving the maximum resistance to brute force key search; and beside the key being harder to manage than a 32-byte one, using 64 bytes does not harm security, and leaves speed almost unchanged (there is no additional hashing done).

On the other hand, 256 bits of security is way more than enough for anything even vaguely foreseable, including quantum computers. If MACs are computed at a rate of $2^{88}$ per year (requiring hashing effort slightly superior to what's devoted to bitcoin mining), and they could be checked among known MACs for $2^{32}$ different keys at that rate (arguably requiring more additional effort than hashing), and we wanted residual odds of $2^{-35}$ that any key is found within 32 years, 160 bits of key entropy is enough, ignoring quantum computers.

HMAC-SHA-256 is designed for 256-bit (32-byte) cryptographic resistance in mind, with no strong argument that using a key with more entropy improves the security; beyond that, there is no assurance given by the best security proof available (Mihir Bellare: New Proofs for NMAC and HMAC: Security without Collision-Resistance, with extended abstract in Crypto 2006 Proceedings).
Thus if the key is full-entropy, there is no strong argument to use a key of more then 32 bytes.

If the key is not known to be full-entropy, there is an obvious, reasonable argument that large keys are necessary. For example, if the key was a diceware passphrase, which has an entropy of $5\log_2(6)\approx12.9$ bit/word, there needs to be 20 words in the key, that is up to 139 characters (with 6 characters per word, and space between words), to reach 256 bits of entropy.


It will happen immediately, because you just posted your password to the internet, where the adversary is watching.

On the other hand, if you can describe the procedure you used to generate it, we can quantify the adversary's probability, knowing only the procedure and not the specific outcome, of guessing the password in one trial.  From there one can quantify the expected cost of an attack that finds it, or the number of trials to find it with any prescribed probability.

For example, if you picked it uniformly at random out of a hat containing

7okufZ308@lB$^KTINX1NWbpdw6rkysxv@giMW5jgI#ZaX*#YwloT3Y$*c*2qVCW
aqfSLH4)K{*zDH:$t6(G^alcSEN\Tbc#8X)W3P[whp%kC@Kn>T#.Q8BQ6=q+![/>
D%]Auqkuel:W4l(/YqBuXSTx7Oh.0]Wq"jly>["t?8wVmUnR+ivCS?<)}+P=-:1N
I am the very model of a modern major passphrase

then the adversary has a 1/4 probability of getting it right in the first trial, and the expected number of trials before the adversary will get it right is 2.

I recommend picking it uniformly at random out of a hat containing at least $2^{128}$ possibilities.

For example, you could flip a coin 128 times and use the outcome as a seed for a CSPRNG from which you sample octets, rejecting those that do not encode graphic characters in US-ASCII, until you have collected 64 of them.

That's not a very efficient use of the password space, though: the adversary's most efficient attack is probably on the 128 coin flip outcomes rather than on the password.  So you could safely bring your password down to 20 US-ASCII characters.

Alternatively, if you want it to be more memorable, you could pick a sequence of 10 words independently and uniformly at random out of a list of 7776 of them, with the help of diceware and a standard household appliance, or with the same rejection sampling technique on a CSPRNG if your name is not Raphael Weldon.

Note that for a uniform distribution on $2^{128}$ possible passwords to be safe against multi-target attacks, you must be sure to combine your password with a hefty salt.  Otherwise, or if you are concerned about quantum computers, it may be prudent to double these numbers (256 coin flips, 40 US-ASCII characters, 20 diceware words) to bring it up to $2^{256}$ equiprobable possibilities, or at least bring it up to $2^{192}$.


I created a spreadsheet "picture" which explained to me how the encoding & wiring works to encrypt the letter 'A' twice, starting with all 3 rotors in the 'A' position.


What information is signed by a Certification Authority?

The information that is signed may differ by certificate, but basically the procedure can be found by looking at RFC 5280 and working downward:

4.1.1.3.  signatureValue

   The signatureValue field contains a digital signature computed upon
   the ASN.1 DER encoded tbsCertificate.  The ASN.1 DER encoded
   tbsCertificate is used as the input to the signature function.  This
   signature value is encoded as a BIT STRING and included in the
   signature field.  The details of this process are specified for each
   of the algorithms listed in [RFC3279], [RFC4055], and [RFC4491].

   By generating this signature, a CA certifies the validity of the
   information in the tbsCertificate field.  In particular, the CA
   certifies the binding between the public key material and the subject
   of the certificate.

Note that signature value is the signature put over the certificate by the CA here, it's not a digital signature over a document.

The next section contains a content description:

4.1.2.  TBSCertificate

   The sequence TBSCertificate contains information associated with the
   subject of the certificate and the CA that issued it.  Every
   TBSCertificate contains the names of the subject and issuer, a public
   key associated with the subject, a validity period, a version number,
   and a serial number; some MAY contain optional unique identifier
   fields.  The remainder of this section describes the syntax and
   semantics of these fields.  A TBSCertificate usually includes
   extensions.  Extensions for the Internet PKI are described in Section
   4.2.

TBS in TBSCertificate stands for To Be Signed which makes things pretty clear.

To be more precise, the contents of the TBS certificate are

TBSCertificate  ::=  SEQUENCE  {
     version         [0]  Version DEFAULT v1,
     serialNumber         CertificateSerialNumber,
     signature            AlgorithmIdentifier,
     issuer               Name,
     validity             Validity,
     subject              Name,
     subjectPublicKeyInfo SubjectPublicKeyInfo,
     issuerUniqueID  [1]  IMPLICIT UniqueIdentifier OPTIONAL,
                          -- If present, version MUST be v2 or v3
     subjectUniqueID [2]  IMPLICIT UniqueIdentifier OPTIONAL,
                          -- If present, version MUST be v2 or v3
     extensions      [3]  Extensions OPTIONAL

subjectPublicKeyInfo above contains the encoded public key.

And the list of extensions can be found by looking at the index:

    4.2. Certificate Extensions ....................................26
           4.2.1. Standard Extensions ................................27
                  4.2.1.1. Authority Key Identifier ..................27
                  4.2.1.2. Subject Key Identifier ....................28
                  4.2.1.3. Key Usage .................................29
                  4.2.1.4. Certificate Policies ......................32
                  4.2.1.5. Policy Mappings ...........................35
                  4.2.1.6. Subject Alternative Name ..................35
                  4.2.1.7. Issuer Alternative Name ...................38
                  4.2.1.8. Subject Directory Attributes ..............39
                  4.2.1.9. Basic Constraints .........................39
                  4.2.1.10. Name Constraints .........................40
                  4.2.1.11. Policy Constraints .......................43
                  4.2.1.12. Extended Key Usage .......................44
                  4.2.1.13. CRL Distribution Points ..................45
                  4.2.1.14. Inhibit anyPolicy ........................48
                  4.2.1.15. Freshest CRL (a.k.a. Delta CRL
                            Distribution Point) ......................48
           4.2.2. Private Internet Extensions ........................49
                  4.2.2.1. Authority Information Access ..............49
                  4.2.2.2. Subject Information Access ................51


YES. What mix-networks provide is anonymous routing. Using a chain of proxies, incoming messages are shuffled and then they are sent in random order. So, the sender remains anonymous. Similarly the Bitmessage protocol mixes all encrypted messages of a given user with all other encrypted messages of the network. As a result, the sender remains invisible. Here, each peer acts as a mix-node.


Finding IV in AES-128 having partial Key and plaintext

The way to solve the problem is the following:

Bruteforcing the last 2 elements of the key.
With that key, trying to decrypt the second block of the ciphertext.
XORing that result with the second block of the plaintext.
Comparing the new result with the partial first part of the ciphertext.
If there is a correspondance we have found the right key (also the complete first ciphertext block), else go to step 1.

The last step is applying XOR to the decryption of the first block of the ciphertext and the first plaintext block. This should return the IV that we are looking for.

Since there is no padding (plaintext is 32 char long) this was not too difficult after a better understanding of the algorithm.


RSA accumulator exclusion proof without set

Great observation! Just a quick recap: $A=g^u\bmod{N},$ where $A$ is the accumulated value, $u=\Pi_{i\in S} x_i$, is the product of the accumulated values $x_i$, where $x_i\in S$ and all accumulated values $x_i$ are primes. An exclusion proof of $x$ is a pair of group elements, $\pi=(g^a,b)$ such that $ax+bu=1$, using the Extended Euclidean algorithm, since $x\notin S\implies (x,u)=1$.
There are essentially two possibilities with respect to generating the exclusion proofs in an RSA accumulator.

The factorization of $N$ is known

This might occur in some use cases if there is an authority who manages the accumulator, e.g., in the Accumulator Manager setting, see this work for an example. In this case $u\bmod{\phi(N)}$ is computable since $\phi(N)=(p-1)(q-1)$ is computable from the factorization of $N=pq$. You can imagine that the Accumulator Manager periodically updates/publishes $u\bmod{\phi(N)}$ to facilitate to efficient exclusion/inclusion proof generation for its users. Therefore, in this centralized setting the mentioned problem does not occur as the bit length of $\log_2(u)\approx\log_2(\phi(N))\approx\log_2(N)$.
Note that even though the exponent $u$ might be large, the Accumulator Manager can convince its users that given $N,g$ and $u$ the exponentiation $g^u\bmod{N}$ was computed correctly without disclosing its users the factorization of $N$. Efficient proofs of exponentiation protocols were proposed by Pietrzak and Wesolowski.

The factorization of $N$ is unknown

This is the tricky setting! Let's assume that there are $n$ accumulated elements, i.e., $\vert S\vert=n$. Then, the size of $u$ is $\log_2(u)=\sum_{x_{i}\in S} \log_2(x_i)=\log_2(p_n\#)$, where $p_n\#$ is the $n$-th primorial. Just to illustrate the growth rate of primorials, $\log_2(p_{2021}\#)=25151$, that is roughly $3.07$ KiB. Unfortunately, $u$ cannot be reduced $\bmod{\phi(N)}$ since the factorization of $N$ is not known. You were not missing anything, if we were in this setting, then unfortunately the RSA accumulator is not efficient to store thousands of elements.
Are there any accumulators that do not require the knowledge of the full set for computing exclusion proofs ?
The simplest example could be a sorted Merkle-tree used as an accumulator. In a sorted Merkle-tree leaves are sorted according to some ordering. In the case of sorted Merkle-trees, computing the exclusion proofs do not increase linearly in the size of the accumulated set, rather logarithmically. With 2 inclusion proofs of neighbouring leaves, a prover can show that a certain leaf between those elements is not contained in the sorted Merkle-tree.


Why would you want to keep the Initialization Vectors Public?

@kelalaka's comment answers this very succinctly, but in the event that a slightly more in-depth explanation helps, here's my stab at it.

The initialization vector is to encryption as a salt is to salted-hashing/key-derivation.  It ensures that if in a given protocol the same values are used multiple times, a different initialization vector can allow the output to still appear random instead of repeating.
With salted hashing (or key derivation) you are using a known deterministic process to generate an output values.  The salt adds additional entropy to help ensure the result is apparently random.  If the same values is hashed twice without a salt, the hash is the same.  When a unique salt is added to each we help ensure that the outputs are different. Even if the output is coincidentally the same (usually extremely unlikely), we introduce doubt that even if the outputs are the same that the original input was the same.
Encryption needs to be reversible and as a result the algorithms are similarly deterministic.  And in many protocols keys are re-used to encrypt many messages.  In the event that the message is encrypted twice with the same key, we risk revealing that fact by producing the same output.  To avoid this, we include the initialization vector.  When a unique initialization vector is used for each message we again help ensure that the outputs are different.  And again even if the outputs are the same, the fact that a different initialization vector was used makes it extremely unlikely that the original message is the same.
Finally, it's also important to note that the fact that IV is tied to a given act of encryption means that it is not always practical to agree to one ahead of time as you would for a key.  In addition, if the key is still secret, getting it to the recipient is all that matters, as that is what you are relying on to keep your encrypted data safe.  So transmitting it publicly isn't a problem.  It's effectively just a parameter of the algorithm you used to encrypt the message.


Write $d$ for the order of an element of $(\mathbb Z/P\mathbb Z)^\times$, we know that $d|P-1$, and that there are at most $d$ elements of order exactly $d$ as they all form roots of the polynomial $t^d-1\pmod p$. Then counting the number of elements of order less than some bound $B$ is less than summing $d$ over the divisors of $P-1$ less than $B$. Taking $B=(P-1)/m^\ell$ shows that $F(P-1)$ is an upper bound for the number of elements of order less that $(P-1)/m^\ell$.
Considering all possible $g$ and $P$, we want to know the proportion of $(g,P)$ pairs for which $\mathrm{ord}(g)<B$. We divide into two cases: either we have a $P$ where the number of $g$ of small order is greater than some bound $C$ (this is bounded by $\mathrm{Pr}(F(P-1)>C$), or the chance of picking a $g$ from a set of size less than or equal to $C$ is bounded by $C/X$. Taking $C=X/m^{\ell'}$ gives the formula stated.