Serpent uses 8 different 4-bit S-boxes (i.e. each S-box contains 16 elements) a total of 32 times. There are no "rows" or "columns" as it is a one-dimensional array containing a derangement of 16 elements. For each S-box, a 4-bit integer from 0 to 15 is mapped to another 4-bit integer from 0 to 15. When implementing the S-box as an array, the input is used as the index and the contents of the array are what make up the S-box itself. The output is simply the element at the index given by the input.
The 8 different Serpent S-boxes (ignoring the inverse S-boxes) are described by the following table:
\begin{equation}
\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
\text{Input}&\operatorname{S_0}&\operatorname{S_1}&\operatorname{S_2}&\operatorname{S_3}&\operatorname{S_4}&\operatorname{S_5}&\operatorname{S_6}&\operatorname{S_7}\\
\hline
0&3&15&8&0&1&15&7&1\\
1&8&12&6&15&15&5&2&13\\
2&15&2&7&11&8&2&12&15\\
3&1&7&9&8&3&11&5&0\\
4&10&9&3&12&12&4&8&14\\
5&6&0&12&9&0&10&4&8\\
6&5&5&10&6&11&9&6&2\\
7&11&10&15&3&6&12&11&11\\
8&14&1&13&13&2&0&14&7\\
9&13&11&1&1&5&3&9&4\\
10&4&14&14&2&4&14&1&12\\
11&2&8&4&4&10&8&15&10\\
12&7&6&0&10&9&13&13&9\\
13&0&13&11&7&14&6&3&3\\
14&9&3&5&5&7&7&10&5\\
15&12&4&2&14&13&1&0&6\\
\hline
\end{array}
\end{equation}
This means that the integer $9$ (binary $1001$) fed through the 3rd S-box ($\operatorname{S_2}$) would be the element at index 9, which happens to be the integer $1$ (binary $0001$). In other words, $\operatorname{S}_2[9] = 1$. The S-box that is used in any given round is determined by the round number. Round $r$ uses $\operatorname{S}_{r\bmod 8}$. The Serpent authors decided to use 8 different S-boxes instead of 32 because the security benefit did not appear to be worth the added ROM footprint, and fewer than 8 would be insecure for such a small S-box.
Each of the 4-bit S-boxes operate on 4-bit chunks of input, returning 4-bit chunks of output. Each round's substitution step involves 32 parallel applications of the same S-box. This substitution is done 32 times (one time for each round). This is realized by splitting the 128-bit block into four 32-bit words. The first bit of each word is used as input for the first S-box. The second bit of each word is used as input for the second S-box. This continues 32 times. Since there are always four words, each S-box only takes 4-bit inputs. The following is taken from a blog post on an implementation of Serpent which explains how a 4-bit S-box is capable of operating on four 32-bit words (i.e. the 128-bit round state):

The diagram below shows how the s-boxes are implemented in bitslice mode. The 128 bit input block is divided up into 4 x 32 bit words: |w0|w1|w2|w3|. These are then arranged as shown in the diagram. The substitution is then applied by taking 32 slices of 4 bits each and putting then through 32 copies of the s-box in parallel. Bit 0 is the lsb in the 4 bit value.


An unusual use-case for HMAC as compression function in web browsers

The collision resistance of this hash will be the collision resistance of $\operatorname{HMAC-SHA256}_{IV}(M)$. Beware of the fact that pre-hashing of the key is a thing with HMAC, so $$\operatorname{HMAC-SHA256}_{\text{ReallyLongIV}}(M)=\operatorname{HMAC-SHA256}_{\operatorname{SHA256}(\text{ReallyLongIV})}(M)$$

  Do I still need to include file length in the final block?

To get the benefits of the Merkle-Damgard proof? Yes, because abstractly your HMAC invocations are just compression function calls.
However if you're willing to assume that it's impossible / really hard to find $(IV',m')$ such that $\operatorname{HMAC-SHA256}_{IV'}(m')=IV_0$ then you don't need to pad with the message length. You see this when you follow the standard Merkle-Damgard proof. That is go backwards through the message and if at any point the inputs differ but the outputs match you got a collision in the underlying compression function. There will be a point where one message may be shorter than the other, assumning both end with the same suffix - because otherwise there would be a collision - both end up at $IV_0$ at some point and as one message is longer one of them must expose a preimage to $IV_0$.

  What are the characteristics of such construct with regard to length-extension attack?

It's a standard Merkle-Damgard, so it has the same length-extension weakness. To fix this you could e.g. use HAIFA and use $C(S,M,P)=\operatorname{HMAC-SHA256}_S(P\mathbin\|M)$ as HAIFA's compression function for some fixed-length integer $P$.


How to key an HMAC with keys from separate mutually untrusted parties?

I would just concatenate.

Two 256-bit keys lead to a 512-bit key which is short enough for HMAC with common hash functions to use as is. XOR would allow the second party to easily choose a related key (and has worse behavior when neither key is perfectly random). Hashing and double HMAC use more resources without a clear benefit, unless you care about the size of the key, in which case hashing would be the way to go.

If you had longer/more keys, concatenation would become equivalent to hashing, because HMAC internally hashes keys that are longer than block size (512+ bits for all SHA-x).


Is encrypting credit card numbers one by one with rsautl secure?

As long as you use a secure padding mode (i.e. -pkcs or -oaep, not -raw).  The default padding mode for openssl rsautl is -pkcs (i.e. PKCS#1 v1.5), so you should be OK.  That said, OAEP is recommended over PKCS#1 v1.5 padding, so you might want to use the -oaep switch.


Hiding and Binding key in Groth-Sahai NIZK proof system

I am still not very familiar with these kinds of proofs, but from what I understood:

1) This inclusion is actually a condition which defines in itself what a hiding key is. That is to say that this paragraph does not say that the inclusion is ensured, but that we should make sure that it is, if we want a perfectly hiding key. However, you may find sets of $u_i$'s that verify this property in the three different instantiations. If you use the short version of the paper where they do not appear, look here instead.

In the second (SXDH) instantiation for instance, to commit in $G_1$, you get $u_1=(\mathcal{P}_1,\alpha\mathcal{P}_1)$ and either $u_2=tu_1$ for a binding key, or $u_2=tu_1-(\mathcal{O},\mathcal{P}_1)$ for a hiding key ($t$ and $\alpha$ are chosen at random). In this last case, $\iota(G_1)\subset \langle u_1,u_2\rangle$ because for $g\in G_1$, you can write $g=\mathcal{P}_1^n$ and then you have $\iota(g)=(\mathcal{O},\mathcal{P}_1^n)=(tu_1-u_2)^n\in\langle u_1,u_2\rangle$. Note that you don't have this with the binding parameters.

2) You are right, they probably meant to write $p\circ\iota$ instead.


A PRF does not have to be length-preserving. We sometimes define it that way for simplicity. In general, $F:\{0,1\}^n \times \{0,1\}^{\ell_1(n)} \rightarrow \{0,1\}^{\ell_2(n)}$ for polynomials $\ell_1,\ell_2$.


Is super encryption (aka “multiple encryption”) always good?

Since you are deriving the key from a password, there is generally not a security advantage to using multiple encryption in the way you described. The entropy of key material generated is less than the maximum security provided by AES, which means an attack on the password will be more effective than a generic key recovery attack on the cipher.

A devastating attack on AES will break the entire system since you are only using a single cipher. The general reasoning for using multiple encryption is that if a single cipher algorithm falls, the system does not. This means you need to use different ciphers, such as AES and Twofish.

In terms of efficiency, any multiple encryption system will be less efficient than a single cipher mode. In your case, you loose the ability to have one of your AES instances available as an in-register cipher with hardware acceleration on a single core, since there is not enough register space to hold the round keys from both instances. If you have multiple cores available this is not a problem, since the CTR stream can be generated in advance of the plaintext, but with CFB it cannot. Spreading across 2 cores using different modes will probably slow it down to less than 50% because of memory access latencies involved when combining the instances. You could keep everything on one core and hop between instances; generate chunk of CTR stream and store, then switch to CFB and use CTR stream while processing plaintext, then repeat as needed. Performing a single mode at a time on the entire plaintext will use the least processor resources, but the most memory, unless you are first writing all intermediate ciphertext to disk.

Depending on implementation, this system may be more vulnerable to a multitude of attacks. Dual AES instances use double the round subkeys, which may need to be stored in RAM rather than CPU register space. This may leave them vulnerable to skimming or cold boot recovery.

There is also more than 1 way to do this. You can perform CFB on all plaintext, then add the CTR stream. Or you can add the CTR stream to the CFB ciphertext block before it is fed back. In the 2nd way, this is equivalent to adding the CTR stream to the plaintext before CFB mode, since both use XOR. You also did not describe any type of authentication scheme, which is extremely important since neither mode is authenticated, especially in the case of stream type ciphers which are vulnerable to bit-flipping.


When the salt is applied before the text is salted , then what is "that"?

It seems you are looking at Modular Crypt Format.

2y identifies a specific version of the bcrypt algorithm
10 specifies the number of rounds
M8z/Bcli/eh3ay5.4w4Y5. is the salt

and the rest is the hash according to the modular crypt format bcrypt page.

It seems the Modular Crypt Format is "deprecated" in favor of PHC-SF which does however look similar.


Non-standard signature security definition conforming ed25519 malleability

Ed25519 in the default implementation is malleable.

It includes the public key $A$ in the hashed message, so it cannot be modified
It includes $R$ in the hashed message, so it cannot be modified
$S$ is encoded as a 256 bit. But since it's a scalar, $S^\prime = S + k \cdot l$ is equivalent to $S$ for any integral $k$ (where $l$ is the order of the subgroup, slightly larger than $2^{252}$).

This means that $S$ is malleable if the implementation doesn't verify that $S < l$. I verified this malleability with the Ref10 implementation.
There could be equivalent values for $S$, even when verifying that $0 \leq S < l$. The paper says:

  Malleability. We also see no relevance of “malleability” to the standard definition of signature security. For example, if we slightly modified the system then
  replacing $S$ by $−S$ and replacing $A$ by $−A$ (a slight variant of the “attack”
  of [75]) would convert one valid signature into another valid signature of the
  same message under a new public key; but it would still not accomplish the
  attacker’s goal, namely to forge a signature on a new message under a target
  public key. One such modification would be to omit $\underline{A}$ from the hashing; another
  such modification would be to have $\underline{A}$ encode only |A|, rather than A.

The way I understand this is that there are no such equivalent values.
$S$ malleability is implementation dependent. Other implementations or batch verification might have different properties.


The question fails to mention a functionality that must be part of any secure True RNG (as the question aims to build): supervision.

Supervision is responsible to detect a failure of the "Random sources" or "stream generating" stages (hereafter unconditioned source), and in that event reliably prevent use of what the "Whitening and stream mixing" (hereafter conditioning) outputs.

Experience and reasoning show that effective supervision is of paramount importance for security. Wear, build defects, and deliberate attacks against unconditioned sources result into sources that e.g. output a stream of constant bits, or that repeat in a very short cycle, or that reproduce the noise on the power supply, or can be controlled by an adversary beaming smurfons. Should this happen, the conditioning would produce apparently random output that

Stands a fair chance to be the same from one use to another. This is the archetypal disaster leading to private keys being identical on many devices (thus not secret as they should), or otherwise vulnerable (example: smartfacts) even without knowing the details of the RNG
Or at least, is vulnerable to attack by one knowing the conditioning, and able to guess the output of the unconditioned source, perhaps by influencing it.

True RNG supervision comprises a test that determines misbehavior of the unconditioned source, and the mechanism (alarm management) acting upon that (like: inactivate everything until the next power cycle). FIPS 140 uses the name "power-up test" and did not mandate further supervision, but the need for supervision actually extends to whenever the RNG might be used: failures and attacks are not bound to strike at power-up!

Supervision also faces a functional requirement of not generating false alarms at a rate that would hamper use of the device. This makes statistical random number generator tests (or at least, their usual parametrization) ill-suited to build supervision. That's because such tests are typically designed to have a quantified and sizable probability of failure for a truly random input, when even 0.01% failure is typically intolerable for mass-produced devices without human operator. Moreover, a practical test must tolerate whatever deviation from uniformly random is expected from its unconditioned source when healthy, and that's heavily dependent of the unconditioned source.

The imperious necessity to tailor supervision to source has been overlooked. Until a change notice in late 2002, FIPS 140 mandated tests (in particular monobit and poker tests) that could not tolerate a small bias or bit cross-correlation. Conformance of a practical device required pre-conditioning of the unconditioned source, in turn making the test less effective, and totally ineffective for a cryptographically strong pre-conditioning. Because FIPS 140 has long been the only public standard specifying test of TRNGs, that mistake is deeply entrenched in literature and standards on secure TRNGs.

A modern, minimal practical approach fro a secure TRNG with supervision as above:

A theoretical model of the unconditioned source must be made, including a target min-entropy rate $r$ (a quantity without unit, in range $(0,1)$, specifying how much true entropy there is per bit output).
The conditioning must be cryptographically secure under the hypothesis that the unconditioned source meets its target $r$. That could mean feeding a Cryptographically Secure Pseudo Random Number Generator $256/r$ bits before it can output anything.
The test in the supervision must catch, with high likelihood, any failure mode of the unconditioned source that can be anticipated to occur according to the model and would bring the unconditioned source below its target $r$; and then prevent use of the output of the conditioning.
Yet the availability of the output must match operational requirements.

There may be other requirements, like detecting a failure/attack of the conditioning, recovering from compromise of the conditioning's state.. that complicate the conditioning.

Rough sketch for an appropriate model and conditioning in the question's context: we can model the hardware (when working properly) as a noise source followed by a 10-bit ADC at frequency $2f$ usable to digitize signal from DC to a certain upper frequency commensurate with $f$, with the source noise having an average voltage excursion of say 1/32 full scale at that $f$ (for some loose definition of that). The ADC is 10-bit, with a specified non-linearity of 4 steps.

Thus when things are working properly, each pair of 10-bit samples (drawn over an interval $1/f$, or more due to, say, interrupts) carries at least $10-\log_2(32)-\log_2(4)=3$ bits of entropy ($r=\dfrac3{20}$ when we count bits output by the ADC). This means we are confident that $256/r=2707$ bits or 271 samples have 256 bits of entropy. We take a factor of two for leeway in the (currently unspecified) test, and use 342 samples, that is 748 bytes when representing a sample as 2 bytes. Acquires that, hash it with SHA-256 (quite easy on an Arduino), and we have 256 bits that we can affirm indistinguishable from random, if our source including ADC is not defective (that is, meets at least half its target $r$) and the program is running correctly.

Note: We are talking of a sampling rate $2f$ about 10kHz according to this. The LM324 is rated at about 1MHz Gain×BandWidth Product @5V, thus up to a gain of roughly 100, that amplifier is unlikely to limit the bandwidth.

Note: I have intentionally grossly oversimplified and ignored large constant factors, but (I hope) erred on the safe side (lowering $r$), except for the "1/32 full scale" assumption which depends on the unstated schematic.

As often, defining the test is the hard part (to be continued).

We can't define a useful test of an entropy source without some model thereof. Argument: Assume a Cryptographicaly Secure Pseudo-RNG. Seed it once by a fixed constant. By definition of Secure in this context, the output is practically indistinguishable from truly independent random bits without knowledge of the constant. This is an insecure source, since it is easily predictable for one knowing the fixed constant. Yet no test exists able to give any indication of this.


How to properly sign and verify using DSA? Can anyone spot my mistake?

Keeping your notation, signature generation in DSA is the following:

$r = (\alpha^{kE} \bmod p) \bmod q$
$s = kEinv \times (h(x) + d\times r) \bmod q$

where $kEinv$ is the modular inverse of $kE$ modulo $q$.

But you actually did was using the formula $s= (h(x)+d\times r) \times \alpha \bmod q$, and you forgot to reduce $r$ modulo $q$. You can take a look at the wikipedia page.


Signature based on public key cryptography and forgery

The standard definition of existential forgery allows the adversary to ask and obtain the signature of any message she wants, and claim success if she can exhibit (with sizable odds) any acceptable (message, signature) pair, for any message for which she did not ask signature.

Update: There is also strong existential unforgeability, where the adversary should not be able to exhibit any acceptable (message, signature) pair for which she did not obtain that signature by asking for the signature of that message. For a use case making the headlines where that strong makes a huge difference, see these links.

Note: in a signature scheme with message recovery, any fraction of the message embedded in the signature needs not be exhibited by the adversary, and is as obtained by the verifier for the purpose of comparison to what the adversary submitted.

Corrected: If "a signer is able to generate a signature which is valid for an other document (that is, message) of his choice", then that scheme is vulnerable to existential forgery. The adversary obtains the signature of the first message, submits that signature unchanged together with the second message, and wins with 100% odds the existential forgery game. Oh no, only the signer could do this, using access to the private key!

Existential forgery is the strongest a strong theoretical criteria for signature. However, it assumes that the signer does not misbehave beside allowing the signature of arbitrary messages; in particular, it is assumed that the signer (or the Smart Card used for signature) does not leak the private key only uses the private key as prescribed, and properly implements every step in the algorithm, like generating truly random numbers.

Update: This spot-on comment by Ricky Demer gives names of security criteria for signatures protected from some attacks by the signer / private key holder.

Update: as pointed by DrLecter in a comment, the standard way to model the signer for a scheme secure against existential forgery (we also say: secure under chosen message attack) is as an oracle that accepts any message and outputs its signature. That oracle is assumed to implement the signature scheme exactly as specified. For more details, I refer to DrLecter's thesaurus of signature security models.


compact hardware implementation of inversion based 8-bit s-boxes

$\DeclareMathOperator{\GF}{GF}$
You can rebuild the transition matrix by using the fact that it is linear (which is why you make a transition matrix) and that it is a field isomorphism. Also, the solution is not unique: you may find several distinct transition matrices that will ultimately allow you to compute inversions in $\GF(2^8)$, but going through different representations in the tower of fields.

In general, you want to find the mapping of $\GF(2^k)$ within $\GF(2^n)$, for $k$ a divisor of $n$. By field isomorphism, $0$ is $0$, so you now want to consider the non-zero elements. For any $x \neq 0$ in $\GF(2^k)$, you know that $x^{2^k-1} = 1$ (since the non-zero elements in a field form a multiplicative group). But a polynomial equation of degree $2^k-1$ cannot have more than $2^k-1$ solutions. So the elements of $\GF(2^n)$ that actually are the elements of $\GF(2^k)$ are exactly the solutions to $x^{2^k-1} = 1$.

Moreover, the multiplicative group of non-zero elements in a field is cyclic. So, for any $k$ that divides $n$, there exists at least one value $g$ whose order is exactly $2^k-1$. In fact about half of them should be such generators. To find an element of of order exactly $2^k-1$ in $\GF(2^n)$, apply the following:

Generate a random non-zero element $h$ in $\GF(2^n)$.
Compute $g = h^{(2^n-1)/(2^k-1)}$.
Order of $g$ is guaranteed to be a divisor of $2^k-1$. You just have to verify that it is not a strict divisor, by computing $g^e$ for any $e$ that divides $2^k-1$. For an AES S-box with $n = 8$, number of elements is so small that trying all of them is a workable strategy. So simply check that $g^e \neq 1$ for all $e$ from $1$ to $2^k-2$.

Therefore, you can compute your mapping in the following way:

$0$ maps to $0$.
Select an element $g$ of order exactly $2^n-1$ in the tower of fields.
Select an element $g'$ of order exactly $2^n-1$ in the target field ($\GF(2^n)$).
Define that $g$ maps to $g'$. Thus, for all integers $i$, $g^i$ maps to $g'^i$. By trying all $i$ from $0$ to $2^n-2$, you will cover all non-zero elements.

At that point you have a complete transition map. The corresponding matrix (since that map is linear) is obtained by simply selecting the map elements for $1$, $z$, $z^2$, $z^3$... $z^{n-1}$.

You might also want to have a look at this article by Boyar and Peralta. They built the smallest known so far circuit for computing an AES S-box. Notably, they begin in the same way as Canright, but they don't make a full tower of fields; instead, they stop at $\GF(2^4)$, for which they compute a fast circuit with a heuristic approach, which appears to yield better results than the full tower. They also explore the problem of minimal circuit for a linear transform.


Get secret_value from multiple hashes md5(known_value_n + secret_value)

No, having multiple hashes will not make determining the secret which was hashed any easier.


The bcrypt hash value consists of the following parts:

$2b — this indicates that the hash is generated according to the OpenBSD implementation of bcrypt.

10$ — this is the "cost" parameter, indicating that the password is hashed with 210 (i.e. 1024) iterations of the blowfish cipher. A higher cost parameter results in password hashes that are harder to crack by brute force.

kn7yEh2nYiDqDYNY.hjiZO — This is the 128-bit salt value, encoded in base64 as 22 ASCII characters

The remaining characters correspond to the 184-bit blowfish hash value, encoded in base64 as 31 characters.

If you check the length of your string, I think you'll find that it's actually one character short, which would explain why you're getting error messages. If this character is simply missing, you could always try appending every possible character from 0-9, A-Z, a-z, . and /. One of them ought to work.
Incidentally, I think it would make more sense to use the checkpw() function in the bcrypt module instead of trying to extract the salt yourself. Here's some code that can check every possible last character. It will take a long time to run if the word list is large.
def check_partial_hash(h, words):
    import string
    for last_char in list(string.digits + string.ascii_letters + '/.'):
        hash = h + last_char
        for word in words:
            if bcrypt.checkpw(word.encode('UTF-8'), hash.encode('UTF-8')):
                return (word, hash)
    return None

partial_hash = u'$2b$10$kn7yEh2nYiDqDYNY.hjiZOtASBKT9uO4KozbFWDW2XLYnW58nkpq'
word_list = [ u'foo', u'bar', u'asd', u'baz' ]
check_partial_hash(partial_hash, word_list)


All fully homomorphic encryptions (FHE) are converted into homomorphic commitments?

Yes, all known FHE schemes are also commitment schemes (BGV included). The reason why GSW if much more often explicitly described as a commitment is that, unlike the alternatives, it leads to a commitment scheme with very nice property - for example, it gives a dual mode commitment (i.e. it can be perfectly binding or perfectly hiding depending on how exactly the parameters are generated), which is a very useful property (at the heart, to mention one application, of the constructions of fully homomorphic signatures).


Could a fixed RSA encryption be used instead of a salt to prevent rainbow table attacks?

I don't see a point of using RSA for password hashing. Using SHA and RSA will not make the bruteforce attack slower. The massive GPU/ASIC attacks will still work if we assume the public key $(e,n)$ is known. That is why we need memory hard functions to make the attacks slower. Sticking the standard is still better like using Argon2id ( Argon2 was the winner of the Password Hashing Competition in 2015). The unique salt also helps to eliminate the rainbow tables. Rainbow tables are dead for passwords system that deploys unique salts!.
A minor point is that one doesn't need to store the RSA private key $(d,n)$ since one cannot reverse the SHAx. So it is useless.
Back to Rainbow
in case of protection against the rainbow tables, one needs to make sure that every password needs a domain separations. This is achieved by unique salt for all. If you want to use the RSA then you need to use OAEP padding or PKCS#1 v1.5. padding. Both are probabilistic encryption scheme that as long as you have a good random number source like /dev/urandom then if you encrypt the same message again and again you will get different results, up to a huge limit of course ( the size of $r$ in the OAEP). One can think of the salt as this randomization.
A side note: the pepper, which is unique salt for each application server, is used to separate the domains of the applications in the case of hitting the same salt for the same user. Also, If an attacker downloads the users' table with only an SQL injection, then they cannot apply even brute-force without the pepper of the server.
Note 2: According to Hashcat list, only OpenSSH uses RSA in a combined mode RSA/DSA/EC/OpenSSH

Addendum
This part is based on the comments of @fgrieu in the case that @marcus considered these;

$(\text{salt},hash = \text{PasswordHash}(\text{salt},\text{DeterministicPadding}(\text{password})^d\bmod n))$

$(\text{salt}, hash = \text{Hash}(\text{DeterministicPadding}(\text{salt}\mathbin\|\text{password})^d\bmod n))$

Here the deterministic padding stands for padding the message for RSA encryption, but deterministically, like RSASSA-PKCS1-v1_5.
It is obvious that if the salt is unique for each user then it is already secure against the rainbow tables. The password crackers if access to the passwords' hashes, cannot test it without the knowledge of the private key.
The biggest problem is the protection of the RSA private key. The usual approach is using HSM to handle those encryptions where the RSA key is stored, too, however, for heavy systems, it may be a bottleneck for the speed. This is no a real comparison, and the usual advice for the password hashing algorithms is adjusting the iteration so that it takes around 1 second per user. This is for user-friendliness. i.e. the general user may not want to wait too much for the login process.
Knowing the public key $(n,e)$ won't help the attackers since they, as of public knowledge, cannot break RSA > 829-bit. See current records on How big an RSA key is considered secure today?
We can consider this RSA operation as a pepper of the application server, too. Also, instead of RSA, one can use HMAC-SHA256 for the same usage, which has a lower key size.
In short, if the key can be protected, It has more protection against the usual approach.


Is GPG symmetric encryption only based on a passphrase?

In GPG the symmetric key used to encrypt data is generated randomly.  That key is then wrapped (encrypted) using a public key or multiple public keys and anyone with any of those private keys can then unwrap (decrypt) the symmetric key and decrypt the data.  Typically, private keys are protected with passwords.  So yes, under normal circumstances, an attacker would need a copy of your encrypted private key and knowledge of your password in order to decrypt data sent to you.
Notice I said "multiple public keys" above.  So, anyone who's public key was included can decrypt the data so if multiple people are included in then any of them can decrypt the data and the compromise of any of their private keys or passwords would result in that encrypt data being compromised as well.


why? ... why wasn't it designed like this? Today we need MAC's to confim the integrity. So, we need 2 different algorithms to achieve this goal... wouldn't it be easier if one algorithm would do all of it?

Yes, but the fact that a MAC is almost always required is simply an idea that surfaced later. MAC constructions themselves surfaced later than ciphers. Before them there was a focus on error propagation and cribs (checksum values also encrypted).

  ... could CBC be modified in a way so that it would support it? In this case my "security Tag" could be ... well... don't know... maybe sending the first block again? If it matches, everything was fine? Or does it have a huge flaw I don't see right now? ... or, is it simply not practical because of the computational power it needs or... lack of parallelization... things like that...

There are single pass algorithms such as OCB, but it is patented. GCM is another one which has a relatively cheap operation over all the blocks, so it is often called a 1,5 pass algorithm.

As you don't describe your algorithm well we cannot analyze it. Your altered CBC scheme obviously doesn't work. The way you XOR you can easily get repeat ciphertext for instance, leaking information about the plaintext. For instance, just encrypt all zero plaintext. A mode of encryption must be secure without any restrictions on the plaintext.

A MAC should be over all the data you need to protect (encrypted or not). I don't see that in your scheme (then again, I don't see any tag displayed in your scheme).


Does there exist a compression function (from four 32-bit words to one 32-bit word) that always detects any modification of a single word?

I may be missing some subtlety intended by the problem-setter, but the simple answer that satisfies the stated conditions, or damn near, is to just xor the words:

$$F = w_1 \oplus w_2 \oplus w_3 \oplus w_4$$

If we model any change to $w_i$ as xoring with a nonzero error term $e_i$, since xor is linear in $GF(2^n)$

$$F' = (w_1\oplus e_1)\oplus (w_2\oplus e_2)\oplus (w_3\oplus e_3)\oplus (w_4\oplus e_4)
\\
= F \oplus (e_1\oplus e_2\oplus e_3\oplus e_4)$$

If only one of $e_i$ is nonzero, the net error is nonzero. If more than one of $e_i$ is nonzero, independently at random, the probability that the net error is zero is almost $2^{-32}$ -- excluding zero from some of the choices throws it off slightly, but I don't remember enough probability to compute exactly how.


what's the advantages of identity-based systems over certificate-based ones?

Public key crypto vs. identity-based crypto made short:
In traditional public key cryptography, a user $A$ generates a
private/public key pair $(sk_A,pk_A)$ and since this key pair has
absolutely no indication to which indentity (user $A$) it belongs, it
is necessary to certify the public key, i.e., bind the public key
$pk_A$ to the user $A$'s identity. This is commonly done by lettig some
trusted authority sign $pk_A$ with additional identifying information
of user $A$ after user $A$ proves by some means that he really is user
$A$ (the result is what is called a certificate).
Identity-based cryptography aims at letting the users public key
be its identity (e.g., the email address) and so to remove the
requirement for certificates. In ID based cryptography a user $A$ uses
his identity (e.g., his email address) as public key. Now, however,
since this information could be used by anybody as an identity it is
clear, that there needs to be some other entity involved in generating
the respective private key. We require a trusted authority (the key
generation center) to compute the private key $sk_A$ that corresponds
to the public identity string $ID_A$ and this trusted authority has to
check whether $ID_A$ (e.g., the email address) indeed corresponds to
$A$ and then issues the private key $sk_A$ corresponding to the
identity $ID_A$. Since the private keys are generated with respect to some public parameters, every party in the system needs to be in possession of an authentic copy of the public parameters (this is similar to a root CA certificate in certificate-based crypto).
Pros and Cons
In theory, the main advantage of identity-based crypto and in particular identity-based encryption is that you do not need to obtain the public key of the recipient but simply can use the recipients identity (=public key) for encryption and the recipient actually does not even need to be in the possession of the respective private key at the point of time when the ciphertext is produced.
In practice, this, however may be not that easy to achieve as theory makes it look like.
Actually, there are various issues which are discussed in the papers I have linked in my previous comments, but I think the most relevant issues are:

Key generation: In traditional public key crypto users generate their keys locally and they are only known to them, while in
the identity-based setting the keys are generated by the trusted authority (inherent key escrow - the party may decrypt all user's
ciphertexts and or may issue signatures on behalf of users. Since the latter is also a problem in certificate-based systems, i.e., the CA
can always produce valid certificates for users and thus sign on their behalf, the decryption issue seems to be far more
problematic). In theory, there is the possibility of distributed key generation in context of identity-based systems, i.e., more than one key generation centres are involved in private key generation, but I doubt that they will really see wide deployment/application.

Revocation: Certificate-based approaches, e.g., PKIX, employs certificate revocation lists or certificate status protocols to check whether a private key has been compromised. If one wants to use the full power of identity-based systems, then ideally the identity (public key) is some information everyone knows, e.g., an e-mail address. But what happens if the corresponding private key gets compromise? Close the email address and choose a new one to get issued a new private key (that does not seem to be really possible in practice for various reasons). Thus, identities need to contain some additional information such as a key expiration date, e.g., mail@bla.com||expiry_date. Now, this forces public keys to be strings that are no longer that well known to other users and require look-ups (sounds similar as whats done in certificate-based crypto). Furthermore, what happens when the key is compromised before the expiry_date? One needs some mechanisms to signal and check that keys have been compromised (sounds similar as whats done in certificate-based crypto). So where are the theoretical advantages now?

Moreover, in what environments the identity-based systems is recommended(or needed) and why?

I would say that, since distributed key generation has not really shown to be used in practice,
identity-based crypto is more for closed environments (enterprises, maybe sensor networks) and not for open environments. Essentially, in any situation
where key escrow is not such an issue, key renewal can be efficiently performed and revocation checks can be made efficient, identity based crypto may be an alternative.
Anyways, it seems that a hybrid between identity-based crypto and certificate-based crypto seems more realistic.
There is also something in between:
Certificateless public key cryptography is inbetween these two
approaches. It aims to get rid of the problem that the key generation
center gets to know the entire  private keys of all users.
In this approach the key generation center only
computes a partial private key of user $A$ based on the identity $ID_A$ and the user then combines this partial private key with some secret information (only known to him). Then the user needs
to take the public parameters of the key generation center and combines
the secret with this parameter to obtain the user's public key. The
advantage here is, that this public key does no longer need to be
certified, since it contains the identity $ID_A$ of user $A$ and if the
key generation center is trusted (and the public parameters of the key
generation center are authentic) one can assume that the user
associated to $ID_A$ really corresponds to $A$ and holds the
corresponding private key.


Are there any good examples of Contemporary Mechanical Cryptography?

While we obviously don't know who is using what and where, we know the U.S. phased out their last mechanical systems (the KL-7) in the 1980s.  The M-94 (Jefferson Cipher Disk) was a clever and simple implementation of a polyalphabetic substitution cipher, so there's no reason it couldn't be used today.  But the U.S. Army stopped issuing them during WW-II.

Note that none of the known mechanical cipher machines would stand up to the kind of brute force cryptanalytic attack available on today's personal computers.

A cryptanalysis of the M-209 (Hagelin machine) written by Dennis Ritchie, James Reeds, and Robert Morris, went unpublished in 1978 as they were informed by the NSA that the principles of their attack were still in use in cryptosystems of the day.  Dennis Ritchie still isn't publishing it.


PBKDF2 with SHA-256/512 for low entropy input?

There is not much of a substantive difference between using SHA-1 or SHA-256 with PBKDF2 to hash a password: they use nearly the same amount of memory (20 bytes vs. 32 bytes of state, plus 8 bytes of message length and 64 bytes of input buffer), and SHA-512 uses only double what SHA-256 uses (64 bytes state, 16 bytes length, 128 bytes buffer).

If you can, forget PBKDF2 and consider using Argon2id instead, so that if you have (say) 128 MB free for password hashing—and perhaps a few extra CPU cores—you can use it all to drive up an adversary's costs.


Dimension of secret key vector tensor with itself?

Maybe it is because the ring is commutative, so the products $s_j[\ell]s_j[k]$ and $s_j[k]s_j[\ell]$ are equal, and therefore, it is not necessary to store all the $(n_j + 1)^2$ elements.

But even so, in this case, it would be needed to store $\frac{(n_j + 2)(n_j + 1)}{2}$ elements, which is equal to $\binom{n_j+2}{2}$ instead of $\binom{n_j+1}{2}$...


How to decrypt a PGP message with only the two primes and the public exponent?

Look up the OpenPGP secret key format (some kind of ASN.1 I think?).
Use your favourite bignum implementation to multiply p by q and store this as the modulus n (in the correct format).
To calculate the decryption exponent, you need $d$ such that $ed=1 \pmod{(p-1)(q-1)}$. This can be found with the extended Euclidean algorithm (the wikipedia pages for RSA and the Euclidean algorithm explain the details) - you're probably going to end up implementing this in your favourite bignum library too.
Store $d$ in the secret key file you're building, import it into gnupg and decrypt normally.

Depending on what programming languages you know, there may be shortcuts - instead of building a key file you might be able to build a key data structure directly and use your language's gnupg/libgcrypt wrapper to work with that.


Block cipher does not provide security by itself

That statement is ambiguous, so I'll list a couple of limitation of block ciphers and cryptography in general:

A raw blockcipher by itself only permutes a fixed size block (128 bits for AES). You need to add a mode of operation (together with IVs and possibly padding) to make it flexible enough for practical use. There are many modes to choose from, including CBC, CTR, OCB, SIV, GCM and XTS. Each one has different properties and strength, so which one is best depends on the the situation.
Encryption without integrity checks (e.g. using AES in CBC mode) is often vulnerable to active attacks, so you need to add a MAC. A modern trend is to use a mode-of-operation that provides both integrity and confidentiality (authenticated encryption, AEAD).
Encryption reduces a confidentiality problem to a key management problem. You still need to solve the key management problem.
Cryptography doesn't provide security by itself. You always need to consider the larger system. This includes endpoint security, threat models, key and identity management and much more.


Statistical tests for pseudorandom permutations

Typically, the output of format-preserving encryption is easily distinguishable from a random bitstream, precisely because the ciphertexts conform to some non-random format.  Thus, you cannot use standard statistical tests on them, at least not directly.

If the format of your FPE scheme is flexible enough, you may be able to test some aspects of it by configuring your scheme to use, say, "a block of $n$ bits" as the format.  More generally, any format that has exactly $2^n$ possible ciphertexts can be bijectively mapped to $n$-bit blocks and tested that way.  However, this will not let you test how your PRP behaves on domains whose size is not a power of two, which is probably what you're most interested in.

(Generally, statistical tests intended for random bitstreams can also be applied to the output of $n$-bit PRPs, e.g. with a simple counter as the input, provided that the number of $n$-bit blocks in the output to be tested is significantly below $2^{n/2}$.  Above that "birthday limit", the probability of observing a repeated $n$-bit block in a truly random bitstream becomes significant, allowing a PRP to be distinguished from a random bitstream.)

In principle, you could also write your own statistical tests that can handle arbitrary ciphertext formats, e.g. by looking at existing test suites and adapting them.  (Alas, while the math is not necessarily all that difficult, many standard test suites tend to be written and documented in a rather abstruse style.)

However, neither of these approaches solves that fundamental issue that, in general, statistical testing is a very poor way to test the security of a cryptographic primitive.  Sure, if your "PRP" output fails a statistical test (for some reason other than its format or the birthday bound), it's a clear sign that it's not secure, but alas, the converse does not hold — it is quite possible for a totally insecure primitive to pass all standard statistical tests not specifically designed to detect the hidden weakness in that particular primitive.

Thus, to convincingly demonstrate the security of your PRP, you need to either:

construct it so that its security can be provably reduced to that of some other cryptographic construction which is already widely believed to be secure, or
publish it and invite other cryptographers to try to break it.

The difficult part with the second option is getting enough attention — good cryptanalysts are few and far between, and often busy, whereas new ciphers are dime a dozen.  Thus, unless you're already a big name in the field, it can be difficult to get anyone to even look at your system.  There are various ways to try to get around that, such as getting someone already well known in the field to publish an analysis of your scheme, submitting it to an international crypto standards competition, or offering a large cash prize for breaking it, but none of them are easy.  Thus, where possible, a provable reduction to an existing scheme is generally preferred.


Convert a state-dependent hash-based signature scheme into a stateless message-dependent one

Can this be salvaged by using some unique-mapping function?

A "unique-mapping function"; that is, a hash function that somehow never gets a collision???

  Or we have a better chance rely on UTC time

Which means that it's still stateful (it's just that the state resides in the time)

  Or use SPHINCS-family schemes?

Actually, what you propose isn't that far off of Sphincs+ (or Gravity Sphincs); both take your general approach of taking the message, hashing it, and using that value to select the path through the hypertree (or, as you put it, interpret as integer leaf indicies at every layer).  The difference is that, at the bottom, they use a Few-Time signature scheme rather than a one-time signature scheme (and so the hypertree doesn't have to be so tall as to make collisions improbable; they just need to make sure that you are unlikely to get too many collisions at the same spot).

  What benefit can we get out of using XMSSMT over SPHINCS-family schemes?

Well:

The signatures are considerably smaller
The signature generation time is considerably faster (and the generation time for the related LMS scheme is faster still)


Ciphertext with uneven letter distribution

I would have expected Vigenère and Playfair ciphers to reduce the skew in the letter distribution, so I think you can rule them out for the time being. Here are some other things you could consider:

Perhaps one of the letters corresponds to a space:

  hello world → itssgxvgksr

Perhaps there is no letter "e" in the plaintext

  A Void by G. Adair → Q Cgor wn U. Qrqok

Perhaps the text was encrypted using a monoalphabetic cipher with homophones (so that two or more letters in the ciphertext correspond to the same letter in the plaintext)

  hello world → itxyg vgkxr

Perhaps the text was encrypted with an additional transposition step

  hello world → itssgvgksr → isggstsvkr

If the ciphertext contains mixed upper and lower case letters, then perhaps it's just been Base64 encoded:

  hello, world → aGVsbG8sIHdvcmxk

If the letters are printed using different styles (e.g., different colours or sizes), then perhaps this is a Baconian cipher

  hello → 00111 00100 01011 01011 01110 → rrvuv ysljq akjsz amshc wvieh


Here is a list of products and companies who have had their EC DRBG algorithm validated by NIST.
http://csrc.nist.gov/groups/STM/cavp/documents/drbg/drbgval.html

The validation lists all modes that have been validated, so you can see which ones have gone to the effort of having their implementation of Dual_EC_DRBG validated.  Tim Dierks points out that, for Lancope's certification (NIST validation #288), Dual_EC_DRBG is the only listed mode of operation that was tested or validated.  It's hard to know why Lancope would have submitted their library for validation if they weren't using it.  So, it sounds like there exists at least one implementation in the wild that uses Dual_EC_DRBG.  (Thanks to Tim Dierks for this analysis.)


With AES-CTR, it is trivial; it's actually one of the advantages of using the scheme. In AES-CTR, there is a counter which is incremented for each block, encrypted, and then XOR'ed to the ciphertext in order to obtain the plaintext. To parallelize the decryption of, e.g., 100 blocks, you simply encrypt the counter for the 1st-50th blocks in one thread and the counter of the 50th-100th blocks in another (simply add 50 to the initial counter value and start from there).

AES-GCM is more or less the same, since it also uses something like CTR internally for encryption. You will have to also check the authenticity, but this can also be done in parallel. (Some people are not confortable with starting decryption before checking the authenticity, but that's another discussion...)


Is WPA2(PKS) AES vulnerable to 4 way hand shake and brute force attack?

Yes. Both WPA-TKIP and WPA2-AES use the same 4-way handshake, and the same way of deriving the PTK from the PSK. AES does not affect this. To launch the brute-force attack on the PSK you only need to capture the 4-way handshake (including the nonces). This is also true for WPA2-AES-PSK.


Why can you use shorter keys with elliptic curve Diffie Hellman key exchange?

There must be some attacks that you can use to try and crack the DLP that can't be used on ECDH and that would force you to chose a longer key for it to be safe.

Indeed, there are algorithms applicable to DLP in groups that are a subgroup of $\Bbb Z_p^*$, but not to Elliptic Curve (sub)groups:

A variant of (G)NFS. See e.g. this article about solving a 768-bit DLP. That used to be the record before this December 2019 announcement about solving a 795-bit DLP.
Index calculus, which in not quite as efficient, but still much more efficient than generic algorithms like baby-step/giant-step and Pollard's rho, which can attack the DLP in any group.

This website specifically lists recommendations for key size. Depending on crystal ball hypothesis, 250-bit ECC (giving the equivalent of about 125-bit symmetric security against classical computers running distributed Pollard's rho) is conjectured to be about as safe as 2000 to 8800-bit DLP in $\Bbb Z_p^*$ (the discrepancy is mostly due to the lesser confidence about the implausibility of better algorithms in $\Bbb Z_p^*$).


Is there a lower cost cryptography than elliptic-curves based cryptography?

In fact, for public-key operation (message encryption and signature verification, as opposed to message decryption and signature generation), RSA and, even more, the Rabin cryptosystem, outperform ECC. This may matter to, for instance, low-power embedded systems that try to connect to a powerful server with a TLS-like protocol.

In the domain of signatures, signature size can also be an important parameter. A plain signature based on elliptic curves (ECDSA, EdDSA) will use about 512 bits (64 bytes) for the customary "128-bit" security level. The BLS scheme does twice better (256-bit signatures) through the use of pairing-friendly curves, which are a very special kind of curve with complicated mathematics, and a substantially higher computational cost. Some multivariate cryptographic schemes can conceptually yield both even shorter signatures and faster operations.

For asymmetric encryption, it is known that the McEliece cryptosystem offers really fast operations (but public and private keys are much larger).

There is currently a flurry of activity with "post-quantum schemes" that offer various additional performance trade-offs; notably, some Ring-LWE schemes have public-key operations that outperform even RSA.

Asymmetric cryptography performance is not a simple metric; many features are amenable to measurement, such as speed of public-key operations, speed of private-key operations, signature size/overhead, encryption overhead, public key size, private key size, implementation RAM and ROM usage,... Classic elliptic curve cryptography tends to perform well in each of these, but for each category, there are other algorithms that outperform them.


Are applications aware of data records received before and after tls rehandshake?

Section II-B talks about this. The answer to this is implementation-dependent. For example, if you're using GnuTLS, you can get some non-fatal error codes if you try to read after parameters change. Then you can look in your logs and distinguish data from before you got the error code from data that's timestamped afterwards. But you may have to be actively looking or polling for it.

You may have better luck on Stack Overflow with this one for particular implementations.


Replay attack is a form of network attack in which the attacker records messages and replays them later. Generally attacker uses them to get authenticated during one way or two way authentication.
Random nonces are used to prevent them instead of timestamp as the latter requires clock synchronization which is tough in practice.


Pseudo-Hadamard transform, most significant bit

The Pseudo-Hadamard Transform on $n$-bit integers $a$ and $b$ is defined as

$$\begin{align}
a^\prime &= a + b &\pmod {2^n}\\
b^\prime &= a + 2b &\pmod {2^n}
\end{align}$$

It is true that the most significant bit (MSB) of $b^\prime$ does not depend on the MSB of $b$. Whether or not this is a problem depends on exactly how it is used in the cipher. While I'm not aware of whether or not this makes any attacks possible on SAFER, Twofish, which also uses the PHT, considers this to be a non-issue. While the MSB is indeed lost, the reduction of security is insignificant, and any measures used to preserve the bit are not worth the performance impacts. From section 7.8 of the Twofish paper:

  The two outputs of the $g$ functions ($T_0$ and $T_1$) are then combined using a PHT so that both of them will affect both 32-bit Feistel XOR quantities. The half of the PHT involving the quantity $T_0 + 2T_1$ will lose the most significant bit of $T_1$ due to the multiply by two. This bit could be regained using some extra operations, but the software performance would be significantly decreased, with very little apparent cryptographic benefit. In general, the most significant byte of this PHT output will still have a non-zero output difference with probability $254/255$ over all 1-bit input differences.


Encoding of the message in Regev encryption

I think there are are several ways to do that. For instance, the "BGV-like" way is to embed the bit $a$ in a vector $\vec{a} = (a, 0, 0, ..., 0)$.

Then, the encryption is quite the same: $a \mapsto (Ar, Br + \vec{a}\lfloor \frac{q}{2} \rfloor)$. And to decrypt, you can subtract $SAr$ from the second component to get $v := Er + \vec{a}\lfloor \frac{q}{2} \rfloor$. Then, notice that $v$ is a vector whose the first entry is $er + a\lfloor \frac{q}{2} \rfloor$ where $e$ is the first row of $E$. Therefore, if you take the first entry of $v$, you get the same that you have in the original scheme and you can proceed as before.


Long Term Security of Truecrypt's hash function?

Unlike the ciphers, the hash algorithm is not used directly to protect your data. Its only purpose is to take your ASCII passphrase and mix it up, shrinking or expanding it to the size required by the underlying ciphers. In order to make brute force attacks more infeasible, this process is repeated thousands of times in an algorithm called PBKDF2-HMAC so that each password attempt takes time. Because they are not used to directly protect your data, it would not be a major problem if the hash function were found to be weaker than believed. In fact, if your password was strong, even using the infamously broken MD4 algorithm would be technically acceptable, although it would be a rather nasty cryptography faux pas.


easy hash algorithm to use without computer

There has been a similar question. The accepted answer there refers to Manuel Blum's HCMU hash function.

Check out Manuel Blum's human computable hash function. He calls it HCMU for Human Computable Machine Unbreakable.
He claims you have to spend an hour memorizing the technique and then you can apply the has function in about 20 seconds without even using pencil and paper.

I have found an implemention of this function here, in just over 60 lines of Python code. Unfortunately I cannot find any paper on it on the go and the link in that other question is broken.


AES in counter mode works by XORing the output of an encrypted counter against the plain-text. This easily allows you to flip bits in the ciphertext and have that bit flip in the plain-text.

The easiest way to get the kind of behaviour you're looking for is rather than XORing the encrypted counter against the plain-text, add it mod $2^{128}$. Decryption proceeds by subtracting the encrypted value mod $2^{128}$.

Then if you deduct $5\mod 2^{128}$ from the ciphertext, that deduction will also affect the plain-text.

This is because:

$c = m + AES(counter,k) \mod 2^{128}$

$m = c - AES(counter,k) \mod 2^{128}$

So:

$c+5 = (m + AES(counter,k))+5 \mod 2^{128}$

$c+5 = (m + AES(counter, k)+5) \mod 2^{128}$

$c+5 - AES(counter, k) = (M+ AES(counter, k) - AES(counter,k) + 5) \mod 2^{128}$

$c+5 - AES(counter, k) = m+5 \mod 2^{128}$

$(c - AES(counter, k)) + 5 = m+5 \mod 2^{128}$

We can then clearly see that the left hand side is the decryption equation + 5 and this five is carried through in to the plain-text.


Why are RSA key sizes almost always a power of two?

In RSA, the bit size $n$ of the public modulus $N$ is often of the form $n=c\cdot2^k$ with $c$ a small odd integer. $c=1$ ($n=512$, $1024$, $2048$, $4096$.. bit) is most common, but $c=3$ ($n=768$, $1536$, $3072$.. bit) and $c=5$ ($n=1280$..) are common. One reason for this is simply to limit the number of possibilities, and similar progressions are found everywhere in cryptography, and often in computers where binary rules (e.g. size of RAM).

The difficulty of factoring (thus, as far as we know, the security of RSA in the absence of side-channel and padding attacks) grows smoothly with $n$. But the difficulty of computing the RSA public and private functions grows largely stepwise as $n$ increases (more on why in the next paragraph). The values of $n$ just below a step is thus more attractive than the value just above a step: they are about as secure, but the later is more difficult/slow in actual use. And, not coincidentally, the common RSA modulus sizes are just below such steps.

One major factor creating a step is when one more word/storage unit becomes required to store a number. When the storage unit is $b$-bit, there is such step every $b$ bits for the RSA public function $x\mapsto x^e\bmod N$; and a step every $r\cdot b$ bits for the RSA private function $x\mapsto x^d\bmod N$, with $r=1$ for the naïve implementation, and $r$ equal to the number of factors of $N$ when using the CRT with factors of equal bit size (most usually $r=2$, but I have heard of plans up to $r=8$). On any modern general-purpose CPU suitable for RSA, $b$ is a power of two and at the very least $2^5$, creating a strong incentive that $n$ is at least a multiple of $2^6$ ($r=2$ is common, and the only reasonable choice for $n$ below about a thousand).Note: $n=1984=31\cdot2^6$ is not unseen in the field of Smart Cards, because the next multiple of $2^6$ would break the equivalent of a sound barrier in a common transport protocol, ISO/IEC 7816-3 T=0. For a list of common RSA modulus size in this field, search LENGTH_RSA_1984.

As an aside, it is significantly simpler to code quotient estimation in Euclidian division (something much used in RSA) when the number of bits of the divisor is known in advance. This creates an incentive to reduce the number of possible bit sizes for the modulus. The two simplest cases are when the number of bits is a multiple of $b$, and one more than a multiple of $b$; the former won.


Given $g^a, Y$, is it hard to distinguish $e(g,g)^{ab}$ from a random value?

I'll assume that the attacker has the value $g$ as well.

If so, we can rewrite $M \cdot e(g, g)^{ab} = M \cdot e(g^a, g)^b = M \cdot h^b$ (where the attacker knows the value $h = e(g^a, g)$.

Assuming that $a$ is relatively prime to the size of the subgroup generated by $e(g, g)$, and that $M$ is a member of that subgroup,then, yes, it is indistinguishable; for any message $M'$ within that subgroup, there a $b'$ for which $Y = M' \cdot h^{b'}$


Quantum resistance of Lamport signatures

The security of the LD scheme can be reduced to the one-wayness (aka preimage resistance) of the used hash function. The reduction is quite easy:

Assume you want to invert the one-way function $f$ for image $y=f(x)$, given a forger for LD-OTS. Then you generate a valid LD key pair using $f$, sample a random position i in the key pair and a bit b and replace $pk_{i,b}$ by $y$ and run the adversary on the modified $pk$. If the adversaries query has bit $b$ in position $i$ you abort and restart the proceedure. Otherwise, you can answer the query. Now you hope that the adversaries forgery hash bit $b$ at position $i$. If this is the case, the $i$th element of the signature is a preimage of $y$ under $f$.

The reduction works with only a slight loss in success probability, i.e. you loose something as you abort in some cases. However, this loss can be bounded by $1/2m$ for $m$ bit messages. You can find the details in the post-quantum cryptography book by Bernstein et al..

Now, the argument for the LD scheme to be quantum secure follows from the fact that the best known generic attack against the one-wayness of a hash function using a quantum computer is Grovers algorithm that has exponential runtime. Moreover, there exist several hash functions that are conjectured to be one-way, even in the presence of a quantum computer.

Something else was recently shown by Boneh and Zhandry in their Crypto2013 paper. There they show that the scheme remains secure even if the adversary is given the ability to make super position queries. This models the case that the scheme itself is run on a quantum computer, not only the adversary.


Any point in waiting for the SHA-3 standard?

From John Kelsey on the NIST mailing list for SHA-3 (http://cio.nist.gov/esd/emaildir/lists/hash-forum/msg02656.html if you are on it — it's password-protected):

a.  We plan to allow the collision and preimage resistance to be the same for SHA3, since that fits with the notion of a single security level, and since that will substantially improve hashing performance.  That is, for a security level of 256 bits, we can accept a capacity of 512 bits, representing both collision and preimage attacks of $2 ^ {256}$ work.
b.  We plan to allow the variable-length feature of Keccak by default, since it seems like such a useful feature.
c.  We are considering whether it makes sense to have many different capacities or only one or two.

So short answer, they do seem set to lower the required capacity from the initial proposal so it isn't as dog slow in software, but haven't figured out what the exact settings will be.


The standard for full-disk encryption (FDE) is XTS mode or ESSIV-AES-CBC.

XTS tweaks each block within each sector differently (and hence avoids ECB's problems) and is considered the best choice available at the moment.

ESSIV-AES-CBC works by using AES-CBC with the IV being the hash of the sector index. The problem with this mode is that you can flip bits at arbitrary positions if you can accept the previous block being "destroyed"(completely scrambled), which you can  very often. F.ex. one could tweak down attack security critical bits and hence compromise the online-security of the system.

CTR would be a really bad idea for disk-encryption as you'd have the same problems as with CBC but you'd also loose "poor-man's-authentication" (-> at least one block gets scrambled), as you can know flipped bits at arbitrary positions without any problems.

What would be optimal for disk encryption would be a mode that turns a small block blockcipher (->AES) into a very large block cipher without too much speed penalties. (2 calls at max) That's was Bitlocker's elephant diffuser tried.

The best solution in my eyes would be to simply have a blockcipher with a very large blocksize that is considered secure. In my personal opinion, Threefish(-512/-1024) would be a nicer option than AES, but it isn't adopted.

You might be interested in this.


Generators and Multiplicative group $\mathbb{Z_7}$

is each element a generator here? if not why?

Take the $2$ and calculate $2 \cdot 2 \cdot 2 \equiv 8 \equiv 1 \mod7$. Therefore, not every element is a generator.

  is an element considered as generator only if $Order(G) = Order(g)$ i.e $Order(g) = 6$  hence $g=3$ is a generator.

A generator must generate all the element. If the order of $Order(a) = x < g = Order(G)$ then it cannot generates all the elements. $a^x =1 $ and the cyclic sub-group generated by $x$ contains only $x$ elements:

$$a^1,a^2, \ldots, a^x = 1$$

  is there any formula to find the number of generators?

No, there is no formula.

  Some website says $\varphi(n)$ gives the order of group some says $\varphi(n)$ gives the number of generators some says $\varphi(n)$ gives the number of elements with a multiplicative inverse. Which of these is correct?

Remember the $\mathbb{Z_7}$ is a field.

$\varphi(n)$ gives the order of the multiplicative group. In your case $\varphi(7) = 7-1 = 6$
2 and 4 are not generators therefore $\varphi(n)$ cannot give the number of generators.
Being a field implies every element is invertible, thus  $\varphi(7)$ gives the number of invertible elements, also for the composite case $-\mathbb{Z_n}-$, where $n$ is a composite number,  $\varphi(n)$,  gives the number of invertible elements.


To calculate the KCV for AES, you take the first three bytes of the encryption of zero under your key.

Indeed, the case you've given is precisely this - the zero vector encrypted under the key 48C3B4286FF421A4A328E68AD9E542A4 is 77dc841daeb43315fed9acdf2f965f45, which restricts to 77dc84.

In your question you say you already have AES-128 encryption, at which point calculating the KCV shouldn't be a problem. I won't ask why you're calculating a KCV, but be warned that there may well be better ways to achieve your actual goal. The other article with this tag provides a reasonable discussion about the benefits of them.


XXTEA (also known as Corrected Block TEA) is a block cipher with $128$-bit key and block width parameterizable to $n\cdot32$ bits for $n\ge2$. It is an Unbalanced Feistel Cipher making $q=6+\lfloor52/n\rfloor$ passes over the block, with $q\cdot n$ rounds each modifying $32$ bits of the block. The round function is a simple Add-Rotate-Xor function of two 32-bit words (one for $n=2$), which are the next and previous ones modified in the round.

In Cryptanalysis of XXTEA, it is presented a chosen-plaintext attack, making use of differential cryptanalysis, recovering the key with about $2^{59}$ chosen-plaintext/ciphertext pairs and work comparable to enciphering that amount of data, applicable when $q=6$, that is $n>52$. The article is not peer-reviewed, but the argument seems plausible to me, and I take this attack as a given.

The practical significance of the attack in the context of the question is very low. That's because there is no way the attacker can obtain even a tiny fraction of the required ciphertext from the original publisher, much less with chosen plaintext; thus the only way that even a huge improvement of the attack could be performed is by using some derivative form of the original software with its original key as an encryption mean. The assumed attacker then has the key right in the software it is trying to use, and can recover it by reverse engineering (like stepping execution). Given the tremendous number of encryptions necessary, the attacker must deeply optimize its software, thus will have no trouble to spot the key. Therefore, the only practical risk I can see of using XXTEA (rather then an unbroken symmetric cipher and operating mode) in the context of the question is a tiny one of image for the publisher: one could demonstrate that the software is using a broken algorithm.

There's an easy solution to that: repair the algorithm by increasing the number of passes, e.g. by changing to q = 6 + 52/n to q = 16 + 52/n in the source code. This single-character insertion is more than adequate to block any attack remotely similar to the existing one, with a much less than threefold reduction in performance, entirely acceptable in the context. Update: If we want to keep the original $32$ rounds for the minimum $n=2$, which motivate the constant $52$, we should make an extra change and use q = 16 + 32/n.

The question does not detail how XXTEA would be used in the licensing scheme: it is not stated in which direction the data transfer is, and if the goal is to protect confidentiality or integrity. I note that towards that later goal, enciphering the whole data as a single block with some fixed field (checked after decryption, and wide enough, say at least $10$ bytes) is sound, because changes in the ciphertext propagate everywhere in the plaintext. That would not be achieved using the more conventional approach of a fixed-block-size cipher in some operating mode like CBC or CTR.

I must point out that public-key cryptography can make sense in this context: it allows enciphering data to the publisher and verifying integrity of data from the publisher without any secret key on the customer side. This in turn enables things theoretically impossible with symmetric algorithms. In particular, even assuming that an attacker has a rightfully licensed software, and gains complete understanding of how the copy-protection works, it remains impossible to illegitimately activate an unmodified copy of the software on another computer, assumed to be distinguishable from the licensed one by some identifier(s), such as MAC address, disk serial number, volume ID, OS-supplied UUID. The best attacks would require modifying the software, or the APIs it uses to get the identifiers (which nowadays is often as easy as licensing the software in a virtual machine, then cloning that).

Update: I'm facing a reasonable diverging opinion, stating that "You should never ever use a cipher or a hash function, that has been broken in academic terms". I agree with that advise in general when defining a new system, and I do suggest to at least summarily repair the academically broken XXTEA rather than use it as is. But there are a few exceptions beside using deployed gear with a minor dent when the risk is acceptable (which is common and perfectly justifiable). One such exception is when using a cryptographic primitive outside the normal hypothesis of cryptography, in particular this cornerstone: the key of a block cipher is assumed secret. Here we are in software copy protection, and in that game the key is next to the hands of the adversary; that makes cryptanalytic resistance of secondary importance. What is much more important is that the code using cryptography is hard to locate and  circumvent, and that means one should avoid use of standard cryptographic libraries, or OS-provided cryptographic APIs. This is one of few cases where rolling one's own implementation of cryptographic code is justified; then, given the secondary importance of cryptanalytic resistance, the simplicity of XXTEA (combined with a static field anywhere in the plaintext for authentication purposes) is appealing compared to the complexity of AES-GCM, which in addition is arguably more likely to become practically vulnerable in the field due to a weakness in the TRNG or whatever is used for the initial value of the counter.


Hash ratchets with truncating hash function

Collisions in the hash will make fewer and fewer keys possible based on the number of iterations, resulting in a sort of "entropy loss". (Aside, I don't think "entropy loss" is the correct term as the system is deterministic and the entropy is provided by the original key.)

Importantly, though, the effect will be very small with a 256 bit hash, as covered by this question.

In short, "yes, but not enough to matter from a security perspective".

I would add a 64-bit counter variable to that hash step as is done in some KDF and password-hashing constructions to ensure there is no chance of falling into a short cycle of keys - no matter how unlikely such a cycle would be.


Beginner question about secure communication with one user using DES

Yeah, the question is something like "A customer wants to to secure their communications with <company> but the customer can only use a DES crypto system and does not have a shared DES key with <company>. How can they securely communicate without help from a third party?"

Well, the customer could call the company and arrange for a meeting with a representative.  After meeting the representative and verifying that they're really working for the company, the customer should hand the representative a note (or a thumb drive) with a randomly chosen DES key on it, saying "Here, use this to communicate securely with me."

(Actually, they should hand the representative two or three DES keys, and tell them to use triple DES, since a single DES key is too short to resist brute force attacks nowadays.)

If the customer and the company representative cannot physically meet, they could perhaps use e.g. the Diffie–Hellman key exchance protocol to obtain a shared secret value, and then each feed it to a key derivation function to turn it into a shared (triple) DES key.  However, Diffie–Hellman alone is not secure against active man-in-the-middle attacks — without some kind of a previously shared secret, there's no way for the customer and the company rep to know for sure that they've really swapped keys with each other, rather than each of them having exchanged keys with some third party who intercepted the original Diffie–Hellman exchange (and keeps intercepting their subsequent communications to decrypt, read, re-encrypt and relay any messages).

If the customer and the company do have some kind of a shared secret — say, a password — then it's possible for them to use a password-authenticated key exchange to "upgrade" the password to a shared (triple) DES key.  One fairly simple way would be for them to first do a normal anonymous D–H key exchange, but then concatenate the resulting shared secret value value with the password and feed it through a deliberately slow key derivation function to turn it into (triple) DES keys.  This ensures that, if a middle-man who doesn't know the password tries to intercept the key exchange, they will not be able to derive a matching DES key with either party.

(This simple protocol does have the weakness that the middle-man, having spoofed the D–H key exchange and intercepted at least one DES-encrypted message using the correctly derived key, now has enough information to mount an offline brute force attack against the password.  The security of this scheme is thus entirely dependent on the strength of the password and the slowness of the KDF.  At the very least, the customer and the company should minimize the attack surface by only using this protocol once, to exchange proper shared keys, and not repeating it later; better yet, they should use a more advanced PAKE protocol that uses an interactive zero-knowledge proof to convince the authenticating parties that they both have the same password and D–H key.)

Depending on the additional assumptions we may make, there can be other options as well.  For example, if the company has a private asymmetric encryption key, and the customer knows the corresponding public key, then the customer can simply generate a random (triple) DES key, encrypt it using the public key, and send the encrypted key to the company, knowing that, even if it's intercepted, only the correct recipient can decrypt it.

(Of course, this only lets the customer know that they're talking to the right company; it doesn't help the company know that the customer is really who they say they are, since the public key, being public, could presumably be used by anyone.  Also, it presumes that the customer somehow already knows that the public key they have really belongs to the company, and not to an attacker.)

Even if the company only has a private key for a digital signature algorithm, there are still ways it could be used to securely establish a shared (triple) DES key.  For example, the customer and company could start with a D–H key exchange, as above, and company could then sign their D–H secret value (preferably after hashing it, to make sure the signature leaks no information about the key) and send the signature (over the DES-encrypted channel) to the customer, who verifies it using the public half of the company's signing key.

In any case, my point is that this problem really has nothing to do with DES as such.  It's really a key-agreement problem, and the solution depends on what kind of existing shared information the customer and the company have (and what kinds of additional tools, besides DES, they many use).  If they really know nothing about each other that an attacker could not spoof, then the problem is strictly speaking unsolvable: if the customer has no way to tell if they're talking to the right company, an attacker can just intercept the customer's messages and reply to them, pretending to be the company.


Does a hash function have a Upper bound on input length?

Does hashing algorithms have an upper bound in the input space?

They can, but they don't have to and it depends on their specification.

All Merkle-Damgård based hash functions do have an upper limit, because appending the message length simplifies the security proof and the backdoor-resistance of the function and they usually use a fixed-length encoding of the length.

Though it appears that MD5 (Spec RFC) kindof just ignores this and indeed accepts message of infinite length. The encoded length in this case are the low 64 bits (so it's reduced $\bmod 2^{64}$; Thanks to forest for making me actually check).

SHA-3 (Spec PDF) does not have such a limit as it's based on the sponge-construction.
Skein (Spec PDF) does have a limit of $2^{96}$ bytes.
Blake2b (Spec PDF) has a limit of $2^{128}$ bytes.


Two formulas work for this three-pass exchange problem, but I can't figure out why one of them works

TL;DR: the second method works only for a vanishing proportion of primes $p$.

The question uses the same relation between $a_1$ and $a_2$ as in the Pohlig-Hellman symmetric cipher. In this:

$p$ is a public prime parameter,
the encryption key is a random integer $a_1$ coprime with $p-1$,
the decryption key is an integer $a_2$ such that $a_1\,a_2=k\,(p-1)+1$ for some integer $k$.
encryption is per $m\mapsto c=m^{a_1}\bmod p$, for $m$ in $[0,p)$,
decryption is per $c\mapsto m'=c^{a_2}\bmod p$, and it holds $m'=m$.

Proof: $$\begin{align}
m'&=c^{a_2}\bmod p&&\text{by construction of $m'$}\\
&=(m^{a_1}\bmod p)^{a_2}\bmod p&&\text{since $c=m^{a_1}\bmod p$}\\
&=m^{a_1\,a_2}\bmod p\\
&=m^{k\,(p-1)+1}\bmod p&&\text{by construction of $a_2$}\\
&=m^{(p-1)\,k}\,m^1\bmod p\\
&=(m^{p-1})^k\,m\bmod p\\
&=(m^{p-1}\bmod p)^k\,m\bmod p\\
&=1^k\,m\bmod p&&\text{per Fermat's little theorem}\\
&=m\bmod p\\
&=m&&\text{since $m$ is in $[1,p)$}
\end{align}$$
Note: Fermat's little theorem tells that when $p$ is prime and $m$ is not a multiple of $p$, it holds $m^{p-1}\bmod p=1$.
One suitable integer $a_2$, and the only one in range $[0,p-1)\,$, is ${a_1}^{-1}\bmod(p-1)\,$: the multiplicative inverse of $a_1$ modulo $p-1$. That's what's used in the question's official solution.
The textbook method to compute that multiplicative inverse is the Extended Euclidean algorithm. For practical implementations, I recommend this variant which uses two less variables and never manipulates negative quantities.

The question's other solution differs only by computing the same $a_2$ using a different formula: ${a_1}^{p-2}\bmod(p-1)$. So the question boils down to:
For prime $p>2$, why/when is it that $a^{-1}\bmod(p-1)$ can be computed as $a^{p-2}\bmod(p-1)$ ?
By definition, $a^{-1}\bmod(p-1)$ is the integer $x$ in $[0,p-1)$ with $a\,x\bmod(p-1)=1$. It is defined only when $a$ is coprime with $p-1$. It follows that the question is equivalent to:
For prime $p>2$, why/when is it that $a^{p-1}\bmod(p-1)=1$ for all $a$ coprime to $p-1$?
That's for many $p$ including the question's $p=101$, but not always. The smallest counterexample is $p=11$, $a=3$. Another it $p=103$, $a=5$. It can be verified that using the second method for these $p$ and encryption keys leads to incorrect decryption for most $m$.
These are the primes form A337119 (created for the occasion), starting with
2 3 5 7 13 17 19 37 41 43 61 73 97 101 109 127 157 163 181 193 241 257 313 337 379 401 421 433 487 541 577 601 641 661 673 757 769 881 883 937 1009 1093 1153 1201 1249 1297 1321 1361 1459 1601 1621 1801 1861 1873

These also are the primes $p$ such that $p-1$ is a Novák-Carmichael number A124240; or equivalently the primes $p$ such that $\lambda(p-1)$ divides $p-1$ (where $\lambda$ is the Carmichael function). They quickly thin out as $p$ grows.
Therefore the question's second method is wrong in general, and most primes $p$ of interest for the application at hand (since they mush be large: thousand bits). Likely it came as an incorrect extension of the following fact: when $p$ is prime, $a^{-1}\bmod p\;=\;a^{p-2}\bmod p$ unless $a$ is a multiple of $p$, which follows from Fermat's little theorem.

In the question's three-pass exchange, $m'$ obtained by Bob in the end is $m$ since
$$\begin{align}
m'&={m_\text{AliceToBob2}}^{b_2}\bmod p\\
&={({m_\text{BobToAlice}}^{a_2}\bmod p)}^{b_2}\bmod p\\
&={m_\text{BobToAlice}}^{a_2\,b_2}\bmod p\\
&={({m_\text{AliceToBob1}}^{b_1}\bmod p)}^{a_2\,b_2}\bmod p\\
&={m_\text{AliceToBob1}}^{b_1\,a_2\,b_2}\bmod p\\
&={(m^{a_1}\bmod p)}^{b_1\,a_2\,b_2}\bmod p\\
&=m^{a_1\,b_1\,a_2\,b_2}\bmod p\\
&=m^{(a_1\,b_1)\,(a_2\,b_2)}\bmod p\\
&=(m^{a_1\,a_2}\bmod p)^{b_1\,b_2}\bmod p\\
&=m^{b_1\,b_2}\bmod p\\
&=m
\end{align}$$


What does the term "differential" in "differential privacy" mean?

The term "differential" was proposed by Mike Schroeder, to characterize the guarantee as being a relationship between distributions with and without any input record. At the time most papers simply defined "(x,y,z)-privacy as ..." and the work felt of a sufficiently different character (both weaker and stronger than prior work) to call out the distinction.

Other adjectives that were discarded were "incremental privacy" and "marginal privacy", for retrospectively obvious reasons.

The name stuck in part due to the analogy to differential cryptanalysis.
Yes, per Ted's answer, which is exactly correct.


I suspect that the professor is thinking of Quadratic Residuosity.  A value $x$ is a quadratic residue (modulo $p$) if there exists a $y$ such that $y^2 \equiv x \pmod p$.

This is important, because:

For any value $x$ (and prime $p$), it's easy to determine whether it's a quadratic residue or not.
If $e$ is relative prime to $p-1$, then $x^e$ is a quadratic residue iff $x$ is.

Now, if we have two plaintext messages, one of which is a quadratic residue, and one is not, can you see how the above observerations can be used to distinguish the two messages from any message in the 3-pass exchange?


Is there any trapdoor that can solve elliptic curve subgroup membership problem?

Here is one (somewhat impractical) possibility:

We pick an Elliptic Curve that has a group size $n$ that is a secret factorization $n = pr$ (I'd say $pq$, except you already gave a separate meaning to $q$)

As our generator $G$, we pick an element of order $p$.

The trapdoor information is the value $p$

It would appear to be a hard problem to determine whether a random element $P$ is in the subgroup $<G>$; however with the knowledge of $p$, we can compute $pP$; that will be the null element iff $P$ is in the subgroup.
Now, $n$ has to be large enough for factorization to be infeasible (as anyone looking at the elliptic curve can run a point counting algorithm to obtain $n$); that means that $q$ (the prime the curve is based on) must be 2048 bits (or larger); hence computations on this curve will be expensive.  It also begs the question "why are you using an elliptic curve at all, rather than (say) the group of quadratic residues in $\mathbb{Z}_{2pr+1}^*$ with $2pr+1$ prime"


What are the consequences of a MAC tag collision?

Whether we get any information from a MAC collision rather depends on the details of the MAC.

HMAC is one extreme.  If you happen to find a collision (that is, two distinct messages that happen to MAC to the same value), well, that doesn't tell you very much.  We don't know how to use that to generate any more collisions, or to gain any information on the key.

MACs based on universal hashes (UMAC) are on the other extreme; in these MACs, the message is sent through a universal hash primitive (which takes a key, and has the property that any two distinct messages hash to the same value for only a small number of keys), and then that hash is protected with some cryptographical primitive.  These types of MACs typically take a nonce; two messages with two nonces that hash to the same value is generally harmless; however, if you MAC two messages with the same nonce and they evaluate to the same value, that usually means that the result of the universal hash happened to be the same, and that gives the attacker information about the key used in the universal hash; usually enough for the attacker to generate second preimages for other messages.  Also, with some MACs of this type, sometimes it is not necessary for the two messages to have the same MAC, the fact that the attacker knows the messages and MAC values based on the same nonce may be sufficient.

CMAC and XCBC are similar to the UMAC case (even though a universal hash is not involved); if you find two messages that have the same CMAC value, it is likely that a simple length-extension to the two messages will allow the attacker to create other pairs of messages with the same MAC.  However, this observation gives no information about the CMAC key; whether this is actually useful in practice depends on whether those length-extended messages happen to be something the attacker can use.


Fiat–Shamir: why do r and s have to be smaller than n?

Because we are working modulo $n$.  There's not much more to say.  There's no reason why any honest user would ever want to use a larger value.  You might want to review modular arithmetic and its use in cryptography.


Would calculating the nth prime ruin encryption?


Trying to calculate the strength of a Bitcoin brain wallet created with a custom diceware password

Generally correct.

It would take approximately 7 years to brute-force all possible keys generated by your brainwallet format, for an attacker with 1Petahash/sec hashing power. For reference, the current hash rate of the entire Bitcoin network is roughly 1 exabyte / second, 1000 times your hypothetical attacker's hash rate.

This means that on average it would take approximately 3.5 years to crack a single brainwallet.

You also mentioned precomputed hashes. For an attacker to precompute all of the given hashes (assuming 32 bytes per SHA256 hash), they would need to store $46656^5 * 32 \approx 7.07 * 10 ^ {24}$ bytes, amounting to 7.07 yottabytes. This is currently an unpractical amount of storage.


RSA - Recover private key if each letter is encrypted separately and we got n,e,m

Encryption letter by letter without padding is very insecure, at best as a mono-alphabetic substitution cipher. But no, it practically does not help one recover a private key matching a known public key. As far as we know, the least costly general method involves factoring the public modulus $n$ part of the public key.
An exception: for extremely small $n$ and/or pathological choices of $(n,e)$, a working private key $(n,d)$ sometime is $(n,e^k)$ for some small integer $k\ge0$. Thus trying a few small $k$ with the help of a few plaintext/ciphertext pairs might be a viable strategy. Silly exercises where $d=e$ or even $d=1$ works are not unseen. And it's common that $d=e^2$ or $d=e^3$ works in exercises that encrypt letter by letter using a 3-digit $n$.

Recovering a working private key $(n,d)$ is not the same a recovering the private key $(n,d)$. For the later, we must factor $n$, and know something about how the private key was computed, or have some other hint (like examining side channel information from a device using the private key). When $n$ is the product of two distinct odd primes $p$ and $q$, methods to obtain $d$ include:

Computing $d=e^{-1}\bmod((p-1)\,(q-1)/\gcd(p-1,q-1))$ (the common modern practice and the one mathematicians prefer, for it gives the smallest working positive $d$).
Computing $d=e^{-1}\bmod((p-1)\,(q-1))$ (still commonly taught).
Computing $d=e^{-1}\bmod((p-1)\,(q-1)/2)$ (that saves the GCD operation while often offering the same minor performance benefit).
Choosing a prime $d$ at random in some interval like $]\max(p,q),p\,q[$, and computing $e$ from that (as in the original RSA article). Now we can find $d$ for sure, or not, depending on what we know about how $e$ was computed, and what the interval really was.

More generally, it is generally believed that no amount of known or chosen plaintext or ciphertext helps recover an RSA private key. But we have no proof of that statement, despite efforts of literally generations of researchers. See this question.


I'm assuming the index of the first bit is 0 instead of 1, which would make 255 the last bit.

Yes. That's made clear by example at the end of section 2, showing bits numbered starting from 0. In this RFC the  i'th bit really is the (i+1)th bit when numbering things the way America does with floor levels and the way many others standards number bits. I accommodate diversity rather than fight it, that's coward but makes life easier.

  When you interpret the string as an integer I'm assuming you're supposed to interpret it in two's compliment?

Sign comes after the decoding to integer. That same section 2 states that integers are non-negative and have a non-signed representation, and section 3.1 states how "negative" elements of GF(p) are encoded:

  The encoding of GF(p) is used to define "negative" elements of GF(p): specifically, x is negative if the (b-1)-bit encoding of x is lexicographically larger than the (b-1)-bit encoding of -x.

My brain hurts parsing that: if $x$ is negative then the $(b-1)$-bit encoding of $x$ (which the statement seems to try to define) is undefined yet, making the definition at best self-referential, at worst preposterous. I get that "lexicographically" combined with little-endian implies that low-order bit matters most in the comparison made.

The Ed25519 paper has something on the tune of that part of the standard, with $\mathbf F_q$ where the standard has GF(p), followed by the helpful

  If $q$ is an odd prime and the encoding is the little-endian representation of $\{0,1,\dots,q-1\}$ then the negative elements of $\mathbf F_q$ are $\{1,3,\dots,q-2\}$.

An element $x\pmod p$ of GF(p) is defined to be negative if and only if $((x\bmod p)\bmod 2)=1$ where the two-arguments operator $\bmod$ (recognizable by not having an opening parenthesis immediately on its left) produces non-negative integers less than its second argument; and that quantity $((x\bmod p)\bmod 2)$ is what's stored as a spare bit.

Thus in the question's quote and what follows, the first $(b-1)$ bits of the $b$-bit representation of point $(x,y)$ on the curve are $y$, little-endian, considered a non-negative integer; and the last bit (the high-order bit of the last byte) defines the sign of $x$. The method stated is enough to fully recover $y$ then $x$ as elements of GF(p), and thus the point.


Pseudo-random Number generation for Passwords

Scrypt is the best function for key-stretching we have. With such a bad password, you'll need all the stretching you can get, so make sure to use a large work parameter and a fast implementation.

But you should really consider using a stronger password. 10 random characters are much better than only 6.


What is the point at infinity on secp256k1 and how to calculate it?

Point at Infinity
Yes, there is a point at infinity $O$ (or denoted as $\infty$) on Elliptic Curves (EC) as the identity element of the Elliptic curve group. Let the EC be given in Weierstrass equation;
$$y^2 = x^3 +a x + b$$
$O$,  the point at infinity can have different values according to the underlying coordinate system;
Coordinate Systems
For an elliptic curve over $\mathbb{F}_p$;

In Homogeneous Coordinates (also known as Projective Coordinate), the points are defined as $(x:y:z),z\neq 0$ corresponding to affine point $(\frac{x}{z},\frac{y}{z})$. The point at infinity  is $(0:1:0)$ and negative value of $(x:y:z)$ is $(x:-y:z)$
In Jacobian Coordinate the points are defined as $(x:y:z),z\neq 0$ corresponding to affine point $(\frac{x}{z^2},\frac{y}{z^3})$. The point at infinity  is $(1:1:0)$ and negative value of $(x:y:z)$ is $(x:-y:z)$

Now, what is $O$ in affine coordinates? Try to convert $O$ back into an affine coordinate! Well, we cannot represent it! See this answer Thus, we simply say it is $O$. But, magically, it can be encoded in implementations.
The Group Law
The points on an elliptic curve form an additive group with an identity $O$. For geometrical meaning please see the below image from Wikipedia Elliptic Curves The group law.

The Group Law on Affine Coordinates
Arithmetically can define the addition rules in affine coordinates. These are derived from the line intersection and tangent equations. The formulas are;
Let $P=(x_1,x_2)$ and $Q=(x_2,y_2)$ be two point in the elliptic curve.

$P+O=O+P=P$
If $x_1 = x_2 $ and $y_1 = - y_2$ and $Q =(x_2,y_2)=(x_1,−y_1)=−P$ then $P + (-P) = O$
If $Q \neq -P$ then the addition $P+Q = (x_3,y_3)$ and the coordinate can be calculated by;

\begin{align}
x_3 = & \lambda^2 -x_1 - x_2  \mod p\\
y_3 = & \lambda(x_1-x_3) -y_1 \mod p
\end{align}
$$
\lambda =
\begin{cases}
\frac{y_2-y_1}{x_2-x_1},  & \text{if $P \neq Q$} \\[2ex]
\frac{3 x_1^2+a}{2y_1},  & \text{if $P = Q$} \\[2ex]
\end{cases}$$
The Group Law on projective Coordinates
Let $P_i = (x_i : y_i : z_i ), i = 1, 2$, be points on the elliptic curve $$y^2 z = x^3 + Axz^2 + Bz^3.$$ Then
$$(x_1 : y_1 : z_1 ) + (x_2 : y_2 : z_2 ) = (x_3 : y_3 : z_3 ).$$ The formulas are;

$P_1 \neq \pm P_2$

$u = y_2 z_1 − y_1 z_2,$
$v = x_2 z_1 − x_1 z_2,$
$w = u^2 z_1 z_2 − v^3 − 2v^2 x_1 z_2,$ then

$$x_3 = vw, \quad y_3 = u(v^2 x_1 z_2 − w) − v^3 y_1z_2, \quad z_3 = v^3 z_1 z_2$$

$P_1 = P_2$

$t = a z_1^2 + 3x_1^2,$
$u = y_1 z_1,$
$v = u x_1 y_1,$
$w = t^2 − 8 v,$

$$x_3 = 2uw, \quad y_3 = t(4v − w) − 8y_1^2 u^2 , \quad z_3 = 8 u^3.$$
For Jacobian Coordinate operations see this link.


TL;DR; Just give me the numbers;
\begin{array} {|l|c|c|c|c|}\hline
 & \text{in a second} & \text{in an hour} & \text{in a day} &  \text{in a year} \\ \hline
\text{Summit on SHA-1} & \approx 2^{49.7} & \approx 2^{61.5}  & \approx 2^{66.1}  & \approx 2^{74.6} \\ \hline
\text{Titan on SHA-1} & \approx 2^{49.1}& \approx 2^{61.0}   & \approx 2^{65.5} & \approx 2^{74.1} \\ \hline
\text{Bitcoin Miner on SHA-256D} & \approx 2^{67.1} & \approx 2^{78.9} & \approx 2^{83.5} & \approx 2^{92.09} \\ \hline
\end{array}

Summit can reach $\approx 2^{63}$ SHA-1 hashes around 3 hours, $\approx 2^{74.6}$ hashes in one year.
Titan can reach $\approx 2^{63}$ SHA-1 hashes around 4 hours, $\approx 2^{74.1}$ hashes in one year.
Bitcoin miners reached $\approx 2^{92.09}$ SHA-256D hashes per year in 7 February 2021 ( or $\approx 2^{93.09}$ SHA-256)

Performance Results of some GPU's

On Amazon AWS P2, up to 16 Nvidia Tesla K80 GPUs has total $31,664.7$ MH/s SHA-1 calculations on average per board $\approx 1,992$ MH/s with hashcat-3.10
on 8x Nvidia GTX 1080 Hashcat Benchmarks has total $68,771.0$ MH/s SHA-1 calculations and on averageper board $8,596.4$ MH/s with hashcat 3.00
Tesla V-100 has $17,225$ MH/s with hashcat 4.0, ( very big? see comparison of NVdia's)

The below tables is constructed from various web-sites [1][2][3] and not taken on average.
\begin{array}{|l|c|}\hline
Device & MH/s \\ \hline
\text{GTX 1080 TI} & 12098.4 \\ \hline
\text{RTX 2070S}   & 11283.1 \\ \hline
\text{RTX 2080 TI} & 16823.6 \\ \hline
\text{RTX 3090}    & 22220.5 \\ \hline
\text{Tesla T4}    &  5428.3 \\ \hline
\text{Tesla P100}  &  9653.8 \\ \hline
\text{Tesla V100}  & 17535.9 \\ \hline
\text{Tesla K80}   & 31664.7 \\ \hline
\end{array}
Calculation based on Tesla V-100
This answer based on the 3rd GPU, Tesla V-100. Tesla V-100 has listed price as $10,664 and has 250 W power consumption. This is closest to
$ 17,225\;MH/s  \approx 2^{35} H/s$
If you run the Tesla V-100 for one hour;
$2^{35}\cdot 2^{12} \approx 2^{47} H/h$ calculations.
OCLF's Summit
The Summit contains  27,648 ($\approx 2^{16}$) NVIDIA Volta architecture GPUs.  According to Oak Ridge Library's news the GPU's are Tesla V100. From the picture of the server board, it is Tesla V100 SXM2, ~10% faster than Tesla V100 PCle and consumes 300W.
Total SHA-1 calculations of Summit in one hour $ \approx 2^{47}*2^{16}= 2^{63}$

The SHAttered hash collision attack on SHA1 can be executed in a little more than 1 hour with Summit.

OCLF's Titan
The Titan contains $18,688 \approx 2^{15}$  physical nodes each contains an NVIDIA Kepler™ accelerator (GPU)1. Assuming that Kepler = Tesla V-100
Total SHA-1 calculations of Titan in one hour $ \approx 2^{47}*2^{15}= 2^{62}$

The SHAttered hash collision attack on SHA1 can be executed in 2 hours with Titan.

Cost
Here I will only talk about the initial cost of GPUs and their runtime cost by power consumption.

Titan :The initial cost of GPUs : $27,648 * 10,664 \approx \\\$300M$
Summit :The initial cost of GPUs : $18,688 * 10,664 \approx \\\$200M$
Titan : Each VT-100 requires $250W*18,688 = 4.67MW$, and taking 12 cents per kilowatt-hour is an average in US, one year cost is \$4,896,256
Summit : Each VT-100 requires $300W*27,648 = 8.29MW$, and taking 12 cents per kilowatt-hour is an average in US, one year cost is \$8,709,120
And, if you rent AWS using p3.16xlarge instance the $2^{64}$  SHA1 evaluations cost about 1M USD.SEjPM's comment

security
There are two question on this site answer the practicability of the shattered;

Does “Shattered” actually show SHA-1-signed certificates are “unsafe”?
After Google's collision attack, is RSA-SHA1 signature still safe?

tl;dr; for this answers;

But it is not safe, regardless of Google's attack. Before Google attacked, we knew that SHA-1 is not the best choice.
You are already too late. Migrate away from SHA-1 now.

notes;
1 This calculation is based only GPUs and CPUs are slower in magnitude order. Only Titan has GPU on the Summit of Oak Ridge National Laboratory. rhea has only 9. Eos and ARM don't have any.