How does ECC go from decimals to integers?

I think what's going on is that a lot of introductions to elliptic curves start off with the geometric description of the group laws so as to be as visual as possible (it certainly is not intuitive to me at all). And then they switch to elliptic curves over finite fields, which look very different than the continuous case over $\mathbb{R}$ even though the group laws are the same:

$$y^2 = x^3 - 2 x + 1 \text{ over } \mathbb{Z}_{89}$$

[source]

I know; that doesn't look like a curve at all. So the idea of a "curve" is really weird over a finite field. But doing all of your calculations  $\bmod p$ (i.e., adding points, calculating "slopes") will always be integral.

Let's go through an example using the curve $E: y^2 = x^3 - 2x + 1$ over $\mathbb{F}_{89}$. Picking $x=4$ gives us $y^2 = 4^3 - 2\cdot 4 + 1 = 57 \bmod 89$. Now, in general, to take the square root modulo a prime, you have to use the Tonelli-Shanks algorithm. Understanding this involves some number theory, such as quadratic residues. Here's a Python implementation. So like "regular" square roots, you can get two answers, and it turns out that $\sqrt{57} \equiv \{71,18\} \bmod 89$. So $(4,18)$ may be the point you mean.

Let's demonstrate addition. Let $P = (P_x, P_y) = (4, 18)$ be the point we just found. I'll pick $Q = (Q_x,Q_y) = (15,63)$. (I iterated through all $x$ from $1$ to $88$ and computed $y$ as above with the modular square root, and just picked one.)

The slope is $\lambda = (Q_y - P_y)\cdot (Q_x - P_x)^{-1} =  45 \cdot 11^{-1} = 45 \cdot 81 \bmod 89 \equiv 85 \bmod 89$

($81$ is the modular inverse of $11$, $\bmod 89$.)

Now calculate $\nu = P_y - \lambda P_x = 18 - 85\cdot 4 \bmod 89 \equiv -322 \bmod 89 \equiv 34 \bmod 89$, and finally,

$$x_3 = \lambda^2 - Q_x - P_x = 85^2 - 15 - 4 \bmod 89 \equiv 86 \bmod 89$$

$$y_3 = -(\lambda x_3 + \nu) = -(85 \cdot 86 + 34) \bmod 89 \equiv 43 \bmod 89$$

So we have $P + Q = (86,43)$ on $E(\mathbb{F}_{89})$. You can check that this point is on the curve since $86^3 - 2\cdot 86 + 1 \equiv 43^2 \bmod 89$.

You may like exploring these ideas with Sage as well.


Why does finding a collision mean that we have solved the problem?

If we find a collision:

$\alpha^{i1} \cdot \beta^{j1} = \alpha^{i2} \cdot \beta^{j2}$

then we know that:

$\alpha^{i1-i2} = \beta^{j2-j1}$

And so, if we know the order of the group (which we generally do), then we can compute $({i1-i2})^{-1}$, and so, we have:

$\alpha = \beta^{(j2-j1) \cdot ({i1-i2})^{-1}}$

Tada, we're done.

  I understand Pollard’s Rho Method for factorization ,but I can't see how it's similar to Pollard’s Rho Method for solving discrate log

Actually, the similarity isn't in what you do when you find a collision, it's a clever way of searching for collisions without using a huge amount of memory.

Here's that idea behind the Rho method: if we designate $F^n(x)$ as the function $F$ iterated $n$ times, for example, $F^4(x) = F(F(F(F(x))))$, and $F$ as a finite range of size $\lambda$, then $F^n(x) = F^{2n}(x)$ for some $n$.  In addition, if $F$ is a random function, then $n$ will (with good probability) be $O(\sqrt{\lambda})$.  This allows us to search for a collision with a small amount of memory (and at a constant cost factor over more obvious techniques that do use a table for $F$ values).


Using the Chinese Remainder Theorem I can compute $M^3$, and then take the cube root. This is why multiple recipient RSA is insecure.


Is Chaocipher a secure cipher under ciphertext-only attack?

While a known plaintext attack successfully finds the keys, nobody has been able to put forward a general solution to this cipher. Is that possible?

You really have to go back in time to learn that ChaoCipher has been subject to some cryptanalysis before the description of the algorithm/device was published. As an example: Here’s one of the oldest papers I found related to the cryptanalysis of the ChaoCipher which was first published in 2003… long before the algorithm was published in 2010 and long before the cipher was subject to a complete break.

If you do a bit of research, you’ll find a few more papers. Most cryptanalytic looks at ChaoCipher have shown ample weaknesses in the distribution, producing anomalies which could be exploited.

Having used the algorithm description to code a C version, I quickly discovered it works somewhat like a substitution cipher that incorporates a primitive version of an lfsr which scrambles the S-box. Nothing you would want to use in times of modern cryptography. It’s more like a most-primitive rotor machine.

Anyway… getting back to the core of your question: is it possible that no one has created a general “this breaks it from every side” solution?

Sure! One reason can be found in the fact that a known-plaintext-attack counts as a complete break (and in this case, a practically feasible one too). Finding additional attack vectors can be fun as a hobby, or it may be something you might want to check on while writing a thesis about ChaoCipher… but it’s not that interesting for most cryptanalysts to dive in deeper when a cryptographic algorithm already was subject to a complete break. Instead, cryptanalysts will be more interested in finding weaknesses in more modern (currently used) ciphers. Compared to modern cryptography, ChaoCipher can’t hold up.

On the other hand, there are ample  websites that talk about its internals… leaving the chance that one day, someone may find ways to break it from all sides – after investing enough time and efforts.


XOR of 16-bytes variables gives a result of size not equal to 16

In implementing crypto, it is essential to distinguish strings (of characters) from byte vectors, also known as bytestrings or byte arrays.

In most computer languages, strings store characters, not bytes, and are not adequate for (un-encoded) intermediary values, ciphertext, keys, Initialization Vectors.. even when and if adequate for plaintext. In C, characters can be signed, and 0 ends a string. In Java, strings contain 2-byte characters. In many modern languages, strings contain abstract Unicode points, or a subset of that, or their representation as bytes per UTF-8 (1 to 4 bytes per character).

The first computational step of encryption of a string is to convert it to byte vector. In modern Python practice, that can be

myString = 'Per Pythagoras: x²+y²=z²'
myByteVector = bytes(myString, 'utf-8')

which here turns a 24-character string into a 27-byte vector. It happens that with UTF-8 encoding, what an American considers a normal character takes one byte, except when it doesn’t (that’s two examples since the previous comma!).

Then byte vectors can be processed, XORed.. (typically, much more naturally than strings) and won't change length unexpectedly.

On decryption, the byte result needs to be changed back¹ to characters, perhaps as a string. In modern Python, the idiom can be

myString = str(myByteVector, 'utf-8')  # can cause exception!

Note: when and if a ciphertext, key, Initialization Vector.. needs to be represented as string, it should be encoded per some binary-to-text encoding, such as the popular Base64.

¹ Beware that's not always possible, e.g. when the ciphertext was altered or the deciphering key is wrong. In such case, the best outcome is an exception; others include garbage text, a beep when that's displayed, a devastating security vulnerability, execution of the HCF instruction, torn out paper on a  Teletype.


Is it possible to decrypt cryptowall-encrypted files?

Cryptowall (from about version 3 and onward) uses AES encryption. The kind of attack you are describing to recover the key(s) used is a known-plaintext attack. Even with an absurd amount of plaintext-ciphertext pairs, there are no known reasonable attacks on AES in the foreseeable future. The AES key itself is encrypted with RSA, but the known plaintexts aren't relevant, as the RSA key is not used to encrypt your files directly.

If you can't live without the documents, your only real option is to pay the ransom. The only other option is to live without your files, and hope that in the future the perpetrator is arrested and the keys are released.

And of course, be sure to keep your antivirus software up-to-date and follow other good practices in the future.


What is different between G1×G1→GT and G1×G2→GT in the bilinear pairing?

The most general form of a bilinear map is $e : G_1 \times G_2 \to G_T$. We can categorize a scheme's usage of the bilinear map into 3 standard categories:

Type 1: in addition to the bilinear pairing, the scheme requires efficiently computable homomorphisms $\phi_{12} : G_1 \to G_2$ and $\phi_{21} : G_2 \to G_1$. In other words, the scheme sometimes needs to "convert/cast" a $G_1$-element to a $G_2$-element and vice-versa. This is the same thing as requiring that $G_1 = G_2$.

Type 2: the scheme requires an efficient homomorphism $\phi_{12} : G_1 \to G_2$. In other words, the scheme sometimes needs to "convert/cast" a $G_1$-element into a $G_2$-element (but not vice-versa).

Type 3: the scheme never needs to "convert/cast" between groups.

See Pairings for Cryptographers by Galbraith, Paterson, and Smart for more discussion about these types (especially section 2).
Type 3 is the most desirable since it places the fewest restrictions on the bilinear map. Type 1 demands a lot of structure from the bilinear map, and I think type-1-compatible groups/pairings are less efficient.


SKID (Secret-Key IDentification protocol), by Walter Fumy and Markus Dichtl, originates from a research effort in Europe in 1992 (Research and Development in Advanced Communication Technologies in Europe, RIPE Integrity Primitives: Final Report of RACE Integrity Primitives Evaluation (R1040), RACE, June 1992), also available in the Springer's LNCS-series, vol. 1007.

Unfortunately, the original text seems to be unavailable in the web. The part I of the book can be found here: http://oai.cwi.nl/oai/asset/5295/5295D.pdf. However, SKID was sent for standardization in ISO/IEC, and is essentially the same as ISO/IEC 9798-4:1999(E)-standard's three-pass authentication mechanism for mutual authentication. This standard seems to be plentifully available via simple googling despite the apparent IPR issues.

SKID-2 means a unilateral (two-pass) auth.protocol, while SKID3 means the (three-pass) mutual authentication (ISO 9798-4, Chapter 5.2.2).

There are indeed some variations on the protocol. Most notably there is confusion on whether $B$ (resp. $A$) should include $B$'s (resp. $A$'s) identity in Step 2 (resp. Step 3) or vice versa. Notably Schneier's Applied Cryptography orders the identities differently (2nd ed. Chapter 3.2 about SKID).

The "original" version of SKID3 (where $B$ will include $A$'s identity inside the MAC in Step 2 and $A$ will include $B$'s identity in Step 3) is correct, at least from the point of view of protecting against reflection attack: adding the identity inside the MAC means that the sending party (here: $B$) is able to distinguish between messages sent by $B$, $A$ and other possible parties $A'$. If the message includes merely $B$'s own identity, such a distinction cannot be made.

The actual questions:

Order of $r_A$ and $r_B$. Within one message it is indeed the same, in which order the nonces appear. However, they need to be in a different order from Step 2 to Step 3, or (as one variation goes) leave out $r_A$ in Step 3. There is a type of attack against a public-key authentication protocol featured in ISO 9798-3 authentication mechanisms called Canadian attack (e.g. p.112 of Boyd and Mathuria's Protocols for Authentication and Key Establishment), which is applicable here as well, if the MACs are too similar. In essence, the attacker may try to fool B to accept a token from Step 2 as a token from Step 3, unless they are dissimilar.
The omitting of $r_A$ does not expose the protocol to typical attacks including reflection, parallel sessions and MitM. This is basically due to the reason that it is difficult for an attacker to get through to Step 3, since Step 2 already includes both nonces and the token is unique in construction and format in the protocol. Other attacks may apply, though.
Even though SKID3 can be considered as a standard mechanism, one will still have to be careful to consider the circumstances where to use the protocol. The protocol does assume a pre-shared secret between $A$ and $B$ and is used for entity authentication only. The notion of universal composability for protocols only came around in 2000 by Canetti, so SKID has been designed on a per-attack basis rather than general security.


Why doesn't this factoring to order-finding reduction work?

Aaronson's notes discuss finding $p$ and $q$ if we know $\phi(N)$ by solving the quadratic equation $X^2-(N-\phi(N)+1)X+N=0$ whose roots are $p$ and $q$. This only works if $N$ is the product of two distinct primes (which is the case in most applications of interest) and if we know $\phi(N)$ exactly.
What doesn't often get mentioned about RSA and multiplicative orders is that although the multiplicative order divides $\phi(N)$, it is never equal to it. In fact it always divides the smaller quantity $\lambda(N)$, the Carmichael function of $N$ and sometimes is equal to it. In the case of two distinct prime factors $p$ and $q$, $\lambda(N)=\mathrm{LCM}(p-1,q-1)$. Shor's algorithm has a pretty good chance of delivering $\lambda(N)$ and the LCM of multiple runs should give the exact value. One then knows (in the two prime case) that $\phi(N)=\mathrm{GCD}(p-1,q-1)\lambda(N)$ and might hope to exhaust over possible values of the GCD in order to use the quadratic equation.
People could start to build $p$ and $q$ to make this GCD large (which is not a good use of time) specifically to block the quadratic equation recovery. Instead we prefer to teach the ``random square root of unity'' recovery of the factors which only needs $\lambda(N)$, which works for moduli with more than 2 prime factors and is not effectively blocked by trying to choose $p$ and $q$ in strange ways.
ETA: On further reflection, rather than exhaust over possible values of $\mathrm{GCD}(p-1,q-1)$ on could take the GCD of $N-1$ and $\lambda(N)$ and mess around. This would probably lead to $\phi(N)$ in short order in the two prime case, but the details begin to get more involved than the square root of unity description.


Why is plain-hash-then-encrypt not a secure MAC?

$\operatorname{Encrypt}(m\|H(m))$ is not an operating mode providing authentication; forgeries are possible in some very real scenarios. Depending on the encryption used, that can be assuming only known plaintext.

Here is a simple example with $\operatorname{Encrypt}$ a stream cipher, including any block cipher in CTR or OFB mode. Mallory wants to forge an authenticator for some message $m$ of his choice.

Mallory intercepts a cryptogram $\operatorname{Encrypt}(m_0\|H(m_0))$ of the form $IV\|C_0$, with $m_0$ known and at least the size of $m$; $C_0$ is the size of $m_0\|H(m_0)$ and the eXclusive-OR of the later with keystream $K$ function of $IV$.
Mallory computes $K$ as $C_0\oplus(m_0\|H(m_0))$, truncated to the size of $m\|H(m)$ if $m$ is shorter than $m_0$.
Mallory computes $C=(m\|H(m))\oplus K$.
Mallory replaces the cryptogram by $IV\|C$, which will pass the authentication check of the receiver, and decipher as $m$.

Another example: assume $\operatorname{Encrypt}$ is AES in CBC, CFB, or OFB mode with random $IV$; and $H$ is SHA-256. Mallory wants to forge an authenticator for some message $m$ of his choice, with size $s$ blocks of 16 bytes (the block size of AES).

Mallory computes $m_1=m\|H(m)$, of $s+2$ blocks.
Mallory manages to insert $m_1$ into some message $m_0\|m_1\|m_2$ sent by a legitimate holder of the AES key, who chooses $m_0$ and $m_2$, with $m_0$ non-empty and of size multiple of the block size known by Mallory.
Mallory intercepts the cryptogram $IV\|C$.
From $C$ Mallory removes one less block than in $m_0$; keeps the next block, forming $\widetilde{IV}$; then the next $s+2$ blocks, forming $\widetilde{C}$.
Mallory replaces the cryptogram with $\widetilde{IV}\|\widetilde{C}$, which will pass the authentication check of the receiver, and decipher as $m$.

That scenario is not far fetched: if Mallory is in a position to choose some file in a CD-ROM image, like a movie he pretends will be a promotion, then he can make a fake enciphered-and-authenticated CD-ROM image, which will appear as an authentic CD-ROM image and decipher to something Mallory chooses arbitrarily.

If $m_0$ can be empty (which is less realistic), an even simpler attack works: $\widetilde{IV}$ is $IV$, $\widetilde{C}$ is the first $s+2$ blocks of $C$.

The title of the question asks if $\operatorname{Encrypt}(m\|H(m))$ is a secure MAC, which to a Vulcan means that $\operatorname{Encrypt}(m\|H(m))$ is appended to $m$ sent in clear. This is does not provide authentication either, and succumbs to trivial variants of the above.


Nonmembership witness in universal accumulator

In accumulators based on groups of unknown order (such as RSA or class groups) or accumulators based on bilinear pairings, both membership and non-membership proofs are constant-sized (i.e. independent of the size of the set and the size of the subset you are proving membership/non-membership for).


Encrypting using "Cryptography.HMACSHA1", how to decrypt (VBA)

HMAC is a message authentication code (MAC). MACs produce "tags" that can can be used to prevent a message from being tampered with (sort of like a digital signature). There's no way to "decrypt" an HMAC tag to get back the original message, so it sounds like HMAC is not what you're looking for.

I would suggest using AES-GCM instead, since it's designed to be used for encryption. I'm not sure how to use AES-GCM from VBA: I suggest asking that on StackOverflow (that question would be off-topic here).


AES-CTR is not considered as a CSPRNG, why?

I don't know why this was given as a negative.
AES-CTR can certainly used to generate a pseudo random stream of values. If that alone makes it a CSPRNG is up for debate if you ask me. For instance, the DRBG's specified by NIST all provide a reseeding operation, which is missing from AES-CTR. Although they do provide a counter based operation as well, AES-CTR clearly doesn't qualify.

Is it unsecure to use it when a password is hashed with Argon2id to produce the seed to generate all random data needed for an end-to-end encyption system such as keys and IVs.

It is probably not insecure, but it seems to me that you are not in need of a CSPRNG. It seems to me that you need a key derivation method. Now Argon2id is already that, so if you just need more data then you can just ask Argon2 for it. It can generate up to over 4 billion bytes ($2^{32}$), which should be plenty.
If you need multiple keys derived by sequence, I'd recommend to use a Key Based Key Derivation Function such as HKDF afterwards, using a label or indeed counter to generate multiple keys. Or you could use a ratchet or similar methods of key derivation.

A practical reason not to specify to use a CSPRNG is that the output of CSPRNG is generally just not precisely defined. The output must be pseudo-random of course, but slight changes in the implementation will generate random but different output even for the same seed. It is often not entirely clear if and when a reseed happens either. In that sense the output of a stream cipher such as AES-CTR is probably better defined in practice.


Signal protocol: when, and why, is X3DH run again between the same two users?

it is unclear to me why X3DH needs to be run more than once

They don't. X3DH is only used to initialise the session between Alice amd Bob. Once Root key is derived, X3DH is no longer required until one of them reinstalls the app or changes device.

Together with Diffie Hellman ratchet,  using KDF

Root key derives Chain key and Root key is updated.
Chain key derives Message key and Chain key is updated.

Message key is the one which encrypts the message. For every subsequent message, Chain key is updated to derive new Message key.

The process looks something like this:

A1 and B1 are Message keys.

Even though the session is not reinitialised periodically, Signal documentation actually recommends this but currently it is not used in practice by either WhatsApp or Signalapp.

  4.2. Session expiration
  It may be desirable for devices to periodically replace old sessions with new sessions, for security purposes.

However, long-term keys of the prekey bundle are still rotated but are not reinitialised with the current recipients.

// Time before rotation of signed prekeys (measured in seconds)
//
// Currently we rotate signed prekeys every 2 days (48 hours).
// We generate 100 one-time prekeys at a time.  We should
replenish
// whenever ~2/3 of them have been consumed.

Source

Identity key is kept same unless the app is reinstalled or the device is changed.

As @Natanael, Signal has an option to restart secure session which reintialises X3DH. There is also a multi-device support in Signal which reintialises X3DH between the recepient and the device. It only happens once with each new device until the app is reinstalled.


Why do we need password in a server which uses TLS?

So that the server knows who you are.

After all, TLS protects the communication; however anyone can initiate a TLS connection to the server (unless the server insists that client authentication must be used; they rarely do).

So, if the server needs to make any decision based on who the client is, it needs to find that out itself; TLS usually won't provide client credentials.


flaw in perfect secrecy of shift cipher?

What you're referring to with "using a shift of 2" is in fact called a Caesar cipher and is not secure. You correctly pointed out, that it can easily be broken if you brute force the 26 possibilities.

But what the author is referring to is a so-called one-time pad (as described on page 78). It has the property of information-theoretic security.

The caesar-cipher can easily be brute forced to the original message, but on the other hand, OTP can be decrypted to any message of the same length. If we don't know any information about the message space then all keys are probable.


Can quantum computer find the period of any given function efficiently? Are there any requirements towards the function?

Well, the function has to be periodic; that is, we have, for some $c > 0$, $f(x) = f(x+c)$, for all $x$ [1].
For both factoring and discrete log, we have such a function; and we know how finding the period of that function will give us the answer.
However, postquantum algorithms, we don't have such a way.  For code-based schemes, no periodicity is apparent.  For lattice-based schemes, there is (periodicity is inherent in the idea of a lattice), however we don't know how to convert finding such a periodicity into (say) an answer to the shortest vector problem.

[1]: Actually, I believe Shor's algorithm will work even if the above relation holds for most $x$; however for the functions of interest, true periodicity holds...


Cost of multiplication when e is randomly selected. RSA

Since this is schoolbook multiplication and homework, I'll give some hints.

Note that, your question is missing an important part, which algorithm we use in the modular exponentiation?

We don't have just multiplications due to the exponentiation operation. We also need the modular reduction. See Modular Exponentiation for general detail.

$$ m^e = c \bmod n$$

You may apply either taking the exponentiation than modular reduction, which will cause huge intermediate values, or you can use apply multiple and reduction paradigm. For this in general, Exponentiating by Squaring  algorithm is used.
Now, reduction, in this case, requires modular reduction that. You may or may not add this into your calculations.
for the second part, hint; when using the Exponentiating by Squaring we use the bits of the exponent.


Can I use ECC for encryption/decryption, just like RSA?

This has indeed been answered previously and I'd be comfortable with it being closed as a redirect to prior answers. But just in case:
No, but yes. These are signature schemes, they cannot be used like RSA. The specific thing you're proposing (directly encrypting a tiny amount of data without a hybrid encryption scheme) is not done. Notice that because key sizes for ECC are much smaller than RSA the "tiny amount of data" could only be a few bytes anyway.
However, the thing you'd actually want to do (encrypting arbitrary data) is possible using ECIES, here's a Wikipedia link about this approach.
https://en.wikipedia.org/wiki/Integrated_Encryption_Scheme
Also, if you're serious about using RSA to encrypt data, please stop. Safely doing this is hard in the general case, plus you've got this arbitrary limit on how much data you can encrypt. Use a hybrid scheme (like ECIES) if you want encryption.


Double DES meet in the middle attack: probability that wrong key pair remains

Yes your argument is correct, to an excellent approximation.

The reason I say approximation is that the second search in the sample space should really be conducted in the restricted set of DES permuataions that already map $P$ to $C$ (sampling without replacement) but for such a huge sample space the inaccuracy due to not doing this is likely much much less than the modelling step of assuming DES is a pseudorandom permutation.


How does a Padding Oracle Attack work in practice?

Here's a real-world example: A captcha service behaves as follows. First, it generates a distorted image of some known text $t$. It sends then image to a web browser, and waits for a response. It compares the response to $t$ to decide whether the captcha is successful.

In a stateful solution, the captcha service itself would have to store $t$ while the web browser would keep some sort of identifier. This leads to all sorts of bookkeeping by the captcha service.

A better approach is to make the captcha service stateless. To do this, you must store the correct solution $t$ to the captcha puzzle in the web browser client! Obviously this solution should be encrypted. The idea is to give the client an image and a ciphertext that encrypts the solution (under a key known only to the captcha service). The client presents the claimed solution along with the ciphertext, and the service just needs to decrypt in order to verify.

But nothing prevents the client from presenting some other ciphertext! This fact (along with poor choice of unauthenticated encryption and error messages leaking padding validity) has led to padding oracle attacks against captcha services. With a standard padding oracle attack you can actually systematically decrypt ciphertexts, hence obtain the captcha solution. Here is a video (loud annoying music) demonstrating a proof-of-concept on a real captcha service.


Apparently, Schnorr was quite adamant, at that time, about the applicability of his patent to DSS. See this message and that one. These are from 1998, but the controversy had begun earlier; see for instance this bulletin from NIST, from late 1994, where references to it can be found in the "Patent Issues" section. Interestingly, NIST not only tried to avoid Schnorr's patent, but they also filed their own patent. Also, see this message for another analysis.

It must be recalled that when NIST began pushing standards for asymmetric cryptography, RSA was already taking the lion's share of the market; what really deserves an explanation is not why NIST preferred DSA over Schnorr signatures, but why they used the DH/DSA pair instead of RSA. IP issues are a very plausible explanation; as the references above show, there indeed was some bitter strife in those years.

As for ElGamal signatures: that scheme is more expensive. ElGamal signatures work modulo a prime $p$ and require one modular exponentiation (for generation) or two (for verification) with exponents as big as $p$; and the signature is two integers modulo $p$. This contrasts with DSA and Schnorr, which both work in a subgroup, traditionally a 160-bit subgroup for a 1024-bit modulus. DSA and Schnorr are 6 times faster than ElGamal, and produce signatures which are 6 times smaller. This difference in performances is enough to explain not choosing ElGamal. Indeed, the short size of DSA and Schnorr signatures has long been the selling point for these algorithms when compared to RSA.


Known Plaintext Attack on Block Cipher in ECB and CBC Modes of Operations

Let me proceed by giving the answers, some of which are probably considered wrong by the book:

(i) One. If you have two ciphertext blocks that are identical you leak information about the message itself, so the cipher would be broken. A message may well consist of multiple blocks with repeated plaintext after all. You'd need $m$ messages of a single block (max) before they start to repeat in the worst case, assuming non-random padding. Here $m$ is the number of messages in the message space, with $m \leq 2^n$ - so $2^n$ is the maximum  of the maximum.

(ii) One. You can verify the correctness of the key with high probability using the a single known block as $n > k$. Even if this is not the case the message may occupy multiple blocks. You'll never be completely certain though. The maximum time for an exhaustive key search is of course $2^k$ (this one is probably correct by the book).

(iii) Still one, because you can simply consider any blocks after the first block.

(iv) Yes, generally it is considered more difficult. ECB is insecure and exhaustive key search is often not practically possible for high enough $k$.

2 You just consider the next blocks as you know the first (known) ciphertext block. The plaintext and thus ciphertext needs to consist of more than one block for this, but only if the IV is random instead of just "unknown"; the more bits you know of each message the better.

As indicated, horrible questions. I would presume I would have quite a few wrong, if just out of sheer unwillingness to understand.


Why is RSA encryption key based on modulo $\varphi(n)$ rather than modulo $n$?

Firstly, a number theory textbook might well help here. I own An Introduction to the theory of numbers which will give you a grounding in this and many other number theory topics which crop up in crypto. It's not my favourite book notation-wise, but in terms of topics covered it is very thorough.

Now, on to what you need help with. There exists a theorem called the division theorem that says any number $n = pq + r$, with the constraints that $n > q > r \geq 0$. In plain words, any number $n$ may be represented by a quotient $q$ (possibly multiplied by a number $p$) and a remainder $r$. An example would be to say that $13 = 7 + 6$ - you recognise this in that $13/7$ could be written as "$1$ remainder $6$".

Modular arithmetic is related - let's start off with $13 \equiv 6 \mod 7$. Intuitively, modular arithmetic is often explained as "you take the remainder and that is the result" which isn't far from the truth - what we actually say is that $7$ and $13$ are part of the same congruence class - that is, $q$ and $r$ ($7$ and $6$) remain the same and the congruence class is made up of all the $n$ for all the $p$ possible. So for $p=2$, $n = 2*7 + 5 = 19$. So $19\equiv 5 \mod 7$ (feel free to check it!).

So, you're concerned with the use of $\mod \phi(n)$ in RSA - well the expression usually given is $de = 1 \mod \phi(n)$. We can re-write that in division-theorem form as $de = k\phi(n) + 1$ - where $k$ is $p$ from the previous example, but renamed so as not to be confused with the prime $p$ that forms $n$.

Now observe what you may have learnt about exponents - that $x^{a+b} = x^ax^b$ and that $x^{ab} = (x^a)^b)$ If you're not convinced, pick numeric examples. Now, a message $m$ raised to the power $de$ is $m^{de}$ - but we have a different expression for $de$ already - that is - $m^{de} = m^{k\phi(n) + 1}$. This can then be written as $(m^{\phi(n)})^k \times m^1$.

There is a very good reason for this form being desirable - namely the Euler-Fermat generalisation to Fermat's Little Theorem, which states that:

$$a^{\phi(n)} = 1 \mod n$$.

Hopefully you should see that our manipulating the algebra to get $m^{\phi(n)}$ in it is not an accident at all - since under $\mod n$, $(m^{\phi(n)})^k \times m^1$ becomes $1^k \times m^1 = m$. This is what makes RSA work the way it does.

I'd also like to address the point fgrieu has raised in his comment, since it is important. The requirement is for the private key is such that $de = 1 \mod \phi(n)$ - or $de = 1 + k\phi(n)$. Clearly, $k$ can be any number we like - any congruence class for which this relation holds will work.

The lowest common multiple of two numbers is the smallest possible number such that both these numbers divide it - for example, the lowest common multiple of $4$ and $6$ is $12$. n this case we observe $4$ divides $12$, as does $6$. Now, the lowest common multiple of $p-1, q-1$ is a number such that both $p-1$ and $q-1$ divide it - well $\phi(n)$ is one such number, for starters! However, (thanks to Poncho), we can say that it is not the smallest possible number. To explain this, consider that $p$ is an odd number and that odd numbers can all be written of the form $2k+1$ for some $k$. If we subtract one, we are left with an even number which will have at least one factor of $2$. Therefore, since $p-1$ and $q-1$ are both even and both have a factor of two, their product ($\phi(pq)$) will have two factors of $2$ at the least, which is 2x what is necessary (at the minimum). More generally, the definition of a lowest common multiple uses the fundamental theorem of arithmetic to demonstrate that the lcm is in fact equal to the product of the maximum power each prime is raised to in each number's prime expansion - eurgh, yes? Well, let's look at that. I chose $4$ and $6$ before - now the prime expansions are $4 = 2^2$ and $6=2\times 3$. Taking the maximum exponentiation of each prime, $2^2 \times 3 = 12$. However, if we did $4\times6 = 2^2 \times 2 \times 3 = 2^3 \times 3$ we see we have gained an extra, unnecessary factor of $2$.

It turns out the Euler-Fermat generalisation can be generalised again - to the Carmichael theorem which states that:

$$a^{\lambda(n)} = 1 \mod n$$

Where $\lambda(n)$ is the smallest such integer where this expression is true. A slight detour - $\phi(pq)=\phi(p)\phi(q)$ and since $\phi(p) = p-1$ that is how we end up with our definition of $\phi(pq)=(p-1)(q-1)$. Now, in the general case, it turns out that $\lambda(pq) = lcm(\lambda(p), \lambda(q)) = lcm(p-1, q-1)$.  By the same reasoning as the case with $\phi(pq)$, $de = 1 \mod \lambda(pq)$ allows us to invert $m^e$ back to $m$ under $\mod n$.

fgrieu has used the term "Rings" - if you're interested in those, I highly recommend Rings, Fields and Groups which is possibly the best Maths textbook I have ever read. It's about (abstract) algebra and also covers some of the number theoretic points, but not as many as a pure number-theory textbook does.


How to find the type of symmetric cipher?

No, OpenSSL is a cryptographic API and TLS implementation with command line interface. It doesn't do crypt-analysis or algorithm detection.

You can try algorithms, probably starting with the most used ones. The size of the plaintext, ciphertext and key may also give hints - keysize and blocksize could point to specific ciphers for instance.

I'm not sure if there are open source or commercial analysis tools out there. You could ask the NSA, I would be hugely surprised if they would not have such a tool.

There is a list mentioned on ReverseEngineering but to me it doesn't give me much hope of finding an actual result.


Costs of operations in elliptic curves explanation

Per poncho's comment: the values given in the linked table are the number of multiplication or squaring operations in the finite field on which the Elliptic Curve is defined (which could for example be $\mathbb Z_p$ for some prime $p$); the cost of other operations in this field is either ignored as marginal (addition, subtraction, multiplication by a small integer constant) or absent (field inversion, which if present would account for 100).

The units are not in second, because counting field operations allows independence from both the speed of the hardware used, and the size parameter of the field (like $p$), which would influence the result in second. Know the duration of multiplication in your field using your device, multiply by the integer in the table, and you have some approximation of the duration for a sequential implementation.

ADD usually has more operations than DBL, because point addition on an Elliptic Curve usually turns out to be more computationally intensive than point doubling (as pointed by CurveEnthusiast in comment, that's not absolute): the later can be viewed as a special case of the former where the two inputs are equal, which allows a shortcut (or rather, requires it). As a crude analogy, it is slightly harder to compute $124865+138747$ than it is to compute $2\cdot124865$; for a start, there's more input.


The reason that salts are used is that people tend to choose the same passwords, and not at all randomly. Many used passwords out there are short real words, to make it easy to remember, but this also enables for an attack.

As you may know, passwords are generally not stored in cleartext, but rather hashed. If you are unsure of the purpose of a hash-function, please read up on that first.

Now, what the attackers can do is to simply generate a list of common passwords and their corresponding hashes. Comparing the hashes that a site has stored with the table will, if common passwords are being used, reveal the passwords to the attacker.

A salt is simply added to make a password hash output unique even for users adopting common passwords. Its purpose is to make pre-computation based attacks unhelpful. If your password is stored with a unique salt then any pre-computed password-hash table targeting unsalted password hashes or targeting an account with a different salt will not aid in cracking your account's password. A long randomly generated salt (using /dev/urandom) is expected to be globally unique. Thus salts can be used to make pre-computation attacks totally ineffective.

The simplest way to combine the salt and the password is to simply concatenate them, i.e. the stored hash value is Hash(salt||password). The common password password1 now magically becomes, e.g., 6$dK,3gCA%Jpassword1 which is unlikely to be found in a password cracker's table.

The salt can be stored completely in the clear in the database, next to the hashed value. Once the attacker has the database and wants to find the passwords, he needs to generate the pre-calculated table for each salt individually, a costly operation.

Another way to help defend against offline password cracking is to perform password stretching, ie. making a password hash slower to compute for any person, including the log-in service and password crackers. One method used to stretch passwords is achieved by iterating the hash-function many times, i.e. storing Hash(Hash(Hash(Hash…(Hash(salt||password)))…).

Another common idea related to salting is called a pepper. That is, another random value concatenated to the password, such that the stored value is Hash(pepper||salt||password). The pepper is then not stored at all. Both the login server and password cracker need to brute force the unknown pepper value, slowing password hash comparisons for both parties.

From 2013 to 2015 a password hashing competition was held to search for a better password-stretching algorithm. The winner was the Argon2 algorithm. Programmers are recommended to use Argon2 instead of implementing their own algorithm.


Difference between strongly universal and $\delta$ univeral hash functions

There are two orthogonal question axes here:

Universal vs. strongly universal.
A universal hash family has bounded collision probability: for any inputs $x \ne y$, the probability that they collide under a random hash function $H$ is bounded by $1/t$, where $t$ is the number of possible hash values: $$\Pr[H(x) = H(y)] \leq 1/t.$$  (If hash values are $m$-bit strings, then $t = 2^m$.)  However, although the probability of collision may be bounded by $1/t$, knowledge of $H(x)$ may inform you about $H(y)$ for certain pairs of $x$ and $y$.

In a strongly universal hash family, sometimes called pairwise independent, this does not happen because the hash values of any two inputs $x \ne y$ are independent uniform random variables: $$\Pr[H(x) = u, H(y) = v] = \Pr[H(x) = u] \cdot \Pr[H(y) = v] = 1/t^2,$$ for any hash values $u$ and $v$.  This is called pairwise independent because it may be limited to any two variables—for any positive integer $k$, there's a corresponding notion of $k$-wise independence.

Obviously any pairwise-independent hash family is universal (proof: exercise), but the converse does not hold.  For example, fix a prime $p$, and define $H_1(x) = a x$ on $\mathbb Z/p\mathbb Z$ for uniform random $a \in \mathbb Z/p\mathbb Z$.  Then $H_1(x) = H_1(y)$ means $ax = ay$, an event which, for $x \ne y$, happens if and only if $a = 0$, so $$\Pr[H_1(x) = H_1(y)] = \Pr[a = 0] = 1/p.$$  But if $H_1(x) = a x = u$, there is only one possible value of $H_1(y) = a y = v$, namely $v = y u/x$, so

\begin{equation*}
     \Pr[H_1(x) = u, H_1(y) = v]
     = \begin{cases}
         1, & \text{if $x v = y u$;} \\
         0, & \text{otherwise.}
       \end{cases}
   \end{equation*}

Hence $H_1$ is not pairwise independent, because for certain values of $x$, $y$, $u$, and $v$, $\Pr[H_1(x) = u, H_1(y) = v] = 1$ is far above the bound of $1/p^2$.  That is, if you know $x$ and $y$, and you learn $u = H_1(x)$, you can perfectly predict what $v$ will be even if you didn't know a priori what the secret hash key $a$ was.
Universal vs. $\delta$-universal.
This is just a generalization of the concept: you replace the bound $1/t$, for a hash family taking on $t$ possible hash values, by the bound $\delta$, which is usually a small multiple of $1/t$.  There is a corresponding notion of a $\delta^2$-strongly-universal hash family.  A $1/t$-universal hash family is just universal.  A $1/t^2$-strongly-universal hash family is just strongly universal.

For example, fix a prime $p$, say $2^{130} - 5$, and let $r \in \mathbb Z/p\mathbb Z$ be uniform random.  For a polynomial $f$ over $\mathbb Z/p\mathbb Z$ of degree at most $\ell$, define $H_2(f) = f(r)$.  We can encode a message as the coefficients of the polynomial $f$.  If $H_2(f) = H_2(g)$ for polynomials $f \ne g$, then clearly $f(r) = g(r)$, so $r$ is a root of the polynomial $f - g$.  But there are only at most $\ell$ such roots.  Since every $r$ has probability $1/p$, we have

\begin{equation*}
     \Pr[H_2(f) = H_2(g)]
     = \Pr[r \mathrel{\text{is a root of}} f - g]
     \leq \ell/p.
   \end{equation*}

Thus, $H_2$ is $\ell/p$-universal.  Here $\delta = \ell/p$ is a small multiple of the number $1/p$ of distinct outputs from $H_2$.  This hash family $H_2$ is noteworthy in cryptography because it is the basis of the Poly1305 message authentication code, which is a contender (along with GHASH) for the most popular MAC in the world.  (Some background on the history and role of universal hashing in message authentication codes in cryptography.)


How to decrypt file on one machine which is encrypted on other machine?

You are using an asymmetric encryption algorithm. By design of this, only the party that has the private key can decipher, and in your case that's the first machine only, because you exported the public key; this explains why you fail to decipher on the second machine.

There are at least two good options to fix this:

Encipher on the second machine, and decipher on the first machine; but you must somewhat manage that the public key is not altered during transfer to the second machine (which is not implied by "send the blob to the second machine over the network").
Generate the key (pair) on the second machine, export the public key and send it to the first machine, with similar requirements that it is not altered in transfer.

If your use case is to encipher (that is, protect the confidentiality of a message) on the machine that generated the key, then it is pointless that this key is for an asymmetric cryptosystem like RSA (a symmetric cryptosystem like AES will do), and you must somewhat manage to move the deciphering key to the deciphering machine in a way that protects that key's confidentiality (which is not implied by "send the blob to the second machine over the network", and typically is harder to achieve that ensuring that the key is not altered).

If your use case is to sign (that is, demonstrate origin and integrity of a message, in such a way that the check requires no confidential material), then generating the key pair on the machine that signs the message and exporting the public key is correct, but you still must somewhat manage that the public key is not altered during transfer to the second machine.


All the properties discussed in the question are for strong primes $p$ in the context of using $p$ as a secret factor of a large composite $n$ which factorization should be intractable; these properties are given in the landmark RSA paper (1978), without justification. Properties thought for (often public) primes used in other cryptosystems can be different.

The first property

  $p-1$ has large prime factors. That is, $p = a_1 q_1 + 1$ for some integer $a_1$ and large prime $q_1$.

is intended to make factorization of $n$ using Polard's p-1 algorithm hard; this is relevant to some degree because this algorithm has a component of its cost proportional to the highest factor of $p-1$, where $p$ is the factor of $n$ exhibited by the algorithm.

Similarly, the third property

  $p+1$ has large prime factors. That is, $p = a_3 q_3 - 1$ for some integer $a_3$ and large prime $q_3$.

is intended to make factorization of $n$ using Williams' p+1 algorithm hard; this is relevant to some degree because this algorithm has a component of its cost proportional to the highest factor of $p+1$, where $p$ is the factor of $n$ exhibited by the algorithm.

One standard that considers the above is FIPS 186-4 (appendix B.3), with $q_1$ and $q_3$ required to be larger than 100 bits when $p$ is 512 bits (and optionally: $q_1$ and $q_3$ larger than 140 or 170 bits when $p$ is 1024 or 1536 bits). It is hard to tell quantitatively when it makes actual sense taking precautions regarding such properties  (beyond conformance to standards): it is pointless when generating a few two-factors RSA keys of at least 1024 bits; it might be useful when extremely many RSA moduli with relatively small factors (e.g. in multi-prime RSA) are generated, and an adversary would benefit finding the factorization of any modulus (rather than of a particular modulus); see this question and its answers.

The second property

  $q_1-1$ has large prime factors. That is, $q_1 = a_2 q_2 + 1$ for some integer $a_2$ and large prime $q_2$.

has to do with reducing the odds that an RSA cycling attack succeeds; see this answer. I fail to find a quantitative assessment of how big $q_2$ should be, or any modern standard with this requirement. I accept the consensus that RSA cycling attacks have negligible success odds for practical key sizes (but would very much appreciate a quantitative argument!).

The standard ways to generate a large strong prime $p$ with the first and third properties (perhaps the second if required) is to choose the auxiliary primes $q_2$ (if required) then $q_1$, and $q_3$, then generate $p$; rather than choosing $p$, then trying to exhibit $q_1$ (then $q_2$ if required) and $q_3$. The later approach would be very computationally intensive: if $p$ is a random 512-bit prime, it requires the factorization of a $(p-1)/2$ and $(p+1)/2$, which are mostly random 511-bit integers, and that's typically a hard job. The former approach (used in practice) introduce significant complexity, but relatively little computational burden; several such methods are detailed in the aforementioned FIPS 186-4 appendix B.3.


Key recovery after AES-ECB encryption of two blocks with some known plaintext/ciphertext

With the encryption of the Temporary Data with 64 bits of plaintext known, does this allow an attacker to brute force the password and know when they got a plausible password because the decryption of the Temporary Data with AES and the derived key they are currently trying will result in 64 bits in the middle being zero which is statistically unlikely?

Yes. The attacker tries plausible passwords starting from most likely (1234, test), runs each thru the password KDF to get the corresponding Password Derived Key, use that to decipher the temporary data, and check that the appropriate 64 bits are zero. If that's the case, the right password has likely been found. This is selective enough that for a fair quality password (says 48-bit, more than XKCD propose), probability of false positive are low ($\approx2^{48-64}<1/65000$). Because there is no salt, the cost of the password KDF (if sizable entropy stretching is used) is incurred only once per password, regardless of the number of users (each user targeted add obly one AES decryption and test).

  Does this mean they could use that recovered Password Derived Key to decrypt the Master Key?

Yes, and from that the "data on the service".

With what we know, I see no other attack, and it is unclear what's the baseline for "more easily" and "less effort" in the question. Forget about brute-forcing AES-128. If there was known plaintext or redundancy in "data on the service", that could help (e.g. to confirm the password), but won't change the overall attack cost, which depends mostly on the password KDF and its parametrization; and the user choosing a hard-to-guess password.


How can I retrieve data embedded in an image with steganography?

In general, you can't.

The reason is this: the data might be encrypted on a way what makes it indistinguishable from random noise. Actually, any good quality encryption does it so.

Thus, if you try to separate any possibly steganographically hidden data, you have no way to know, if it is really random noise, or it is encrypted, but worthy content.

It might be possible if the hidden data is not encrypted on some reason (for example, for better data safety).


Is there a simple zero knowledge proof of $x$ for $b=x^x\pmod p$?

The original question was:

Alice knows: $a,b$ and $x$ such that $a^{(x\cdot x)} = b$
Bob knows: $a,b$

and DrLecter referenced this paper (fixed the link), which covers the question.
Now, the question was changed to

Alice knows: $b$ and $x$ such that $x^x=b$;
Bob knows: $b$.

The given structure was:

... multiplicative group $G$ which is a subgroup of  $(\mathbb{Z}/n\mathbb{Z})$

And a sub-question in the comments was, if this is easy if $n$ is prime. The answer in this case is: "It depends".
As poncho pointed out, if $x>n$ is allowed, you can find a $x$, if you consider the exponent and the base independently (let's call the modulus $p$ for being prime):

$x=b$ mod $p$
$x=1$ mod $p-1$
Since $p$ is prime, we can apply the Chinese Remainder Theorem to get $x= p^2 - bp + b$.

So for $x$ without restrictions, there is no need for a ZKP, because it is easy to calculate the solution from $b$ and $p$ alone.
Now the tricky part: What if $x$ is limited to $x<p$?

In general, there is no solution, because there is no structure which would be preserved by a function $x\rightarrow x^x$. I can't even think of a way to check if for a given $y$ there exists a $x$, s.t. $x^x=y$.

But what we can prove is that there can be no such zero knowledge proof:

Bob knows $b$.
If $b=1$, the solution is $x=p-1$ or $x=1$, this means $x<p-1$.
If the modulus is prime, he can check if $b$ is a quadratic residue.
$x$ has a factorization in $\mathbb{Z}$, and for every prime factor $x_1$ of $x$, we know that $x^{(x/x_i)}$ has to exist, because $x^a$ is well-defined for every $0\leq a\leq x$, if $0<x<p$.
If $b$ is a quadratic nonresidue, then there exists no quare root, and we know that $x$ does not contain a factor $2$ (in $\mathbb{Z}$).

A similar approach can be made for every prime factor of $p-1$, because the according exponentiation with this factor is a non-injective function.
This is a contradiction to ZK already, because knowledge of $b$ reveals already some information about $x$.


how do we calculate set intersection using homomorphic encryption?

I'm not sure where Bloom filters necessarily come in.
The "standard" way to use additively homomorphic encryption (that's what Paillier is) for set intersection is the oblivious polynomial evaluation (OPE) technique.
It works like this:

Alice generates a polynomial whose roots are the items in her set: $p(x) = \prod_{a \in A} (x-a)$. She encrypts the coefficients of $p$ using an additively homomorphic scheme, under her own key. She sends the result $E_k(p)$ to Bob.
For each $b \in B$, Bob chooses a random value $r_b$ and uses the homomorphic property of the encryption scheme to evaluate $E_k\Big( r_b \cdot p(b) + b \Big)$. This requires only additive homomorphism since $b$ and $r_b$ are known to Bob. Note that: if $b \in A$ then $p(b) =0$ so the result is $E_k(b)$; otherwise the result is the encryption of a uniformly random value. Bob sends all of these ciphertexts back to Alice.
Alice decrypts the ciphertexts and computes the plaintext intersection with $A$.

This technique dates back to:

  Efficient Private Matching and Set Intersection by Michael Freedman, Kobbi Nissim, Benny Pinkas (see Sec 4.1)


Is AES ECB good enough for key spreading?

I then want both to spread the key byte values across the entire key length

Neither is useful. AES is secure without such "spreading" (not a standard term). The method discussed does that fine.

However it is missed a step critical for security of any password-based encryption: key stretching. The idea is to transform the password into the key for AES (as done by the question's method), in a purposely slow manner. This is necessary to avoid a password search attack.

To derive of a key from a password you need a password based key derivation function or PBKDF. A key derivation function based on a password is also called a password hash for short; it is also commonly used for password verification. Known PBKDF's are bcrypt, scrypt, PBKDF2 and the much newer Argon2 (in various forms). These all perform key stretching.


A hash can be computed for any input, even for an empty input.

Some tools may display the output of some hash function, other tools may not.

If the file is large, it may take some time to compute, so tools may not display the hash immediately, only on-demand.

So this is more a question about specific software than cryptography.


What will happen to existing cyphertext when today's encryption is broken?

For me it is absolutely not certain at all that many cryptographic primitives will become broken. This was certainly true - to some extend - for older algorithms. But modern cryptography is a different beast than the classical ciphers. We know a lot more about various attack vectors and semantic security. So your initial premise is very speculative.

Symmetric algorithms are already thought to be relative secure against quantum analysis, only halving the key strength (in bits) at best. There are a lot of asymmetric primitives that could be broken using a full fledged quantum computer, but there are certainly post quantum algorithms available. They may not be completely stable or standardized yet, but they are there.

Now you start to talk of an "event" that would happen in the future. Now I speculate that this "event" will never happen. Even if the algorithms we use today get broken, they won't get broken all at once. There are different levels of being "broken" as well, even MD5 - a known broken hash - is still secure in many protocols (password hashing, key derivation, HMAC, you name it).

If ciphertext gets broken it will not happen all at once either. And the impact of the plaintext becoming available will depend completely on the contents of the plaintext. This could be huge for state secrets. However, for the majority of the plaintext: the ciphertext will either not be available to persons that want to abuse the information or the plaintext will have completely lost the importance it once had.

Huge data leaks are happening right now, and the world moves on. We don't need any magic cryptographic breakthrough for that. If you want to know the impact you only need to study what is happening today.


Can an ephemeral RSA key give forward secrecy?

Yes and yes and it already (almost) does.

Forward secrecy is defined with regards to the notion of "long-term secret". The idea is that any secret that is stored for a long time is potentially amenable to ulterior theft. Forward secrecy is obtained when stealing long-term secrets does not allow breaking past communications, and the easiest way to achieve such secrecy is to use ephemeral keys: if a key is not stored anywhere, then it cannot be stolen afterwards.

In older days, SSL/TLS implemented some "export" cipher suites that were meant to comply with the then-strict US export regulation on cryptographic software. When using an "RSA_EXPORT" cipher suite (like TLS_RSA_EXPORT_WITH_DES40_CBC_SHA), the server would have a long-term RSA private key; if that long-term RSA key was longer than 512-bits, then the server would generate a 512-bit ephemeral key pair, sending the public part as a ServerKeyExchange message, signed with the long-term RSA Key. This mechanism was, ironically, meant to support the opposite of forward secrecy, in that the goal was to allow the encryption to be broken through even in cases where the long-term secret was not stolen. However, it demonstrates the mechanism just well: server sends an ephemeral public key for the key exchange, and that public key may be of type RSA.

Some noteworthy details:

Though the server sends a RSA public key in a ServerKeyExchange message that it signs itself, and thus can potentially generate an ephemeral key pair, nothing forces the server not to reuse or even store that key pair. In fact, since generating a RSA key pair is a relatively expensive operation, most servers were reusing such key pairs for long period of times; possibly, the 512-bit key pair was stored in a file, or generated upon process startup and reused for weeks. This allows an attacker some time to break the key (512-bit RSA can be broken with relatively little computing power) and use that knowledge in some Man-in-the-Middle attack. This has been dubbed the FREAK attack.
Though the "ephemeral RSA" mechanism was defined, it was not updated to longer key lengths, because implementing it was felt to be too clunky and expensive. When SSL/TLS implementations use ephemeral keys, they do so with Diffie-Hellman (DHE cipher suites) or an elliptic-curve variant thereof (ECDHE cipher suites). Diffie-Hellman allows for very efficient generation of a new key pair, contrary to RSA. Moreover, ECDH tends to be a lot more efficient than RSA, both in terms of CPU (less work) and bandwidth (public elements are smaller).

Using ephemeral RSA key pairs would make sense in the very specific context of an very small, powerless client talking to a big server. On the client side, this would entail only public RSA operations (signature verification, asymmetric encryption) that can be made very fast by using a very small public exponent (e.g. $e = 3$). Clients that are so small that they cannot perform an ECDHE key exchange in reasonable time also have a hard time running a full-fledged SSL/TLS protocol, because of network issues (bandwidth, latency because of the two round-trips...) and lack of readily available implementations that comply to the server constraints of such platforms (code size, very little RAM...).


Why do the discriminant and primality of the group order of an elliptic curve affect security?

$y^2 = x^3 + ax + b\bmod p$ is the Short Weierstrass equation. The theory behind it is here

Using Bezout’s Theorem, it can be shown that every irreducible cubic has a flex (a point where the tangent intersects the curve with multiplicity three) or a singular point (a point where there is no tangent because both partial derivatives are zero). [Reducible cubics consist of a line and a conic, which are easy to study.]
An irreducible cubic with a flex can be affinely transformed into a Weierstrass equation:
$$Y^2 + a_1 XY + a_3 Y = X^3 + a_2 X^2 + a_4 X + a_6$$

And this can be converted into a short Weierstrass equation if $p$ is larger than $3$. The transformation can be achieved by
Change $y\longrightarrow y-(a_1x+a_3)/2$, now the new equation has of the form $$y^2=x^3+Ax^2+Bx+C.$$
And now change $x\longrightarrow x-A/3$, now  the new equation has of the form $$y^2=x^3+ax+b.$$
The reason for $p \neq 2,3$ can be seen from the divisions. Also one should note that the two changes of variables are invertible, therefore their composition, too. This concludes that the rational points on both equations are in bijective correspondence.
For $p=2$ and $p=3$ there are other short forms. In Cryptography we work in either binary extension fields ($\mathbb{F}_{2^m}$) which no more secure and large prime fields ($\mathbb{F}_{p}$) and on their extensions ($\mathbb{F}_{p^m}$).

If the discriminant is not different than zero ($\Delta = 0$) then the curve is singular then the DLP is easy. Geometrically, this means that the graph has cusps, self-intersections (node), or isolated points.
Cusp;  when $\Delta=0$ and $a=0$ ( $y^2 = x^3$);

Intersection or Node;  when $\Delta=0$ and $a\neq 0$ ( $y^2 = x^3 +3x +1$);

Acnode (isolated point); $y^2 + x^3 + x^2$, at $(0,0)$

Note these draws are not in the finite fields where we cannot see such figures to see those. A curve with the finite field just points when we draw on the plane as below and we cannot see the above singular points, however, we can still calculate them.

The above is the point of the curve over $\operatorname{GF}(307)$  with the curve equation $ y^2 = x^3 + x^2 + x$ and this curve group is isomorphic to $ Z/160 + Z/2$

And, Wolfram has a nice page about those singular points.

This is not completely true. Some curves have prime order ( i.e. $\#E(\mathbb F_p)$ is a prime) and all of the elements other than the identity can be a generator ( see the blow theorem).
Some curves don't have prime order, like the Curve25519, it has a co-factor $h=8$ i.e. $h = \frac{\#E(\mathbb F_p)}{n}$ where $n$ is the order of the generator point $G$. In this case, we chose the largest prime and select a generator for it.

There is also twist security related to the order that one must consider. Although the NIST P-224 has co-factor 1 ( i.e. it has prime order), it doesn't have the twisted security.

Theorem: Let $E$ ben elliptic curve group over the finite field $\mathbb{F_q}$. Then $$E(\mathbb{F_q}) \simeq \mathbb{Z_p} \text{ or } \mathbb{Z_{n_1}} \oplus \mathbb{Z_{n_2}}$$ for some integer $n \geq 1$, or for some integers $n_1,n_2 \geq 1$ with $n_1|n_2$.
If the order of the curve is prime then it must be $E(\mathbb{F_q}) \simeq \mathbb{Z_p}$.


Can block ciphers encrypt messages larger than the key length?

A block cipher like AES itself cannot be used to encrypt large files. One needs to use some mode of operation to chain a sequence of blocks. The length of this whole "chain", which essentially is the product of the block size and number of blocks, is the length that you can encrypt files with. The key size of the block cipher basically tells you what security level you can get from a "chain" of block ciphers (or a single block cipher of course).


Encoding a message to a point of curve y^2=x^3+7 and Bitcoin Core

In ECDSA, the message is never encoded as a point in the elliptic curve. Signing in ECDSA loosely works like this:

$$
\begin{align*}
k &= \text{random}(0, n) \\
(x, \_) &= k \cdot G \\
r &= x \bmod n \\
s &= k^{-1}(H(m) + r \alpha) \bmod n
\end{align*}
$$

$r$ and $s$ are the signature, and as you can see $H(m)$ is only ever used as an element of the integers modulo $n$, the order of the generator point $G$ (and $\alpha$ is the private key). Therefore, $H(m)$ is never treated as a point, and thus never needs to be encoded into one.


Dividing elements in $R_q$ by $z$ in Grag-Gentry-Halevi (GGH) Graded Encoding Scheme

I believe $R_q$ is not field

Yes, it is not a field in general. $R_q$ is a field if, and only if, $q$ is a prime and $X^n+1$ is irreducible over $\mathbb{Z}_q[X]$.

However, you are not forced to pick $q$ as a power of two. As section 4.2 of the original paper explains, the only restriction over $q$ is

$$q \ge 2^{8\kappa \lambda}n^{o(\kappa)}$$

In particular, you can let $q$ to be prime (as it is supposed to be in Lemma 5).

And even if you don't select $q$ as a prime, you just have to check that $z$ has an inverse in $R_q$ and that the order of $z^{-1}$ is bigger than $\kappa$. If this is the case, then you are fine, if not, then sample another $z$.


Storing passwords in a publicly available database

It's generally not a good idea to store passwords of any kind in a database that's not secure, let alone a database that's intended to be publicly available.

  Is it secure?

If you don't care about tampering and wrong entries in the database then I guess this setup is okay.

Bcrypt already incorporates a salt to prevent rainbow attacks, so all passwords should have a different hash. Since you then encrypt the hash with the public key of an asymmetric encryption algorithm it should actually be secure. To try and brute-force a password in the database you would first have to brute-force the asymmetric encryption, which is infeasible on any time-scale.

  Is there a simpler way?

Yes, implement security-conventions (secure database, etc.), no need to reinvent the wheel.


Is the beaufort cipher just as secure as the Vigenere cipher?

Yes, it is.  The Beaufort cipher is identical to the Vigenère cipher except that, in effect, the plaintext alphabet is reversed (i.e. mapped A → Z, B → Y, etc.) before encryption (and after decryption).  The reversal adds no appreciable security, but it also cannot make the cipher less secure.


How do we find the subkey out of a differential cryptanalysis?

The key does not effect the cipher' differentials threw the equation (x+k)+(x'+k)=x+x' (the + sign means xor)

How you can yes the key is X1+k=x2
And threw the xor k=X1 +x2

X1 is the value beffor the xor with the key value k. X2 is the output of X1+k

To make this attack work beffor you must find a differential for the two input pairs threw a chosen plaintext attack x'+x= D1 (differential 1)
Then the corresponding cipher text outputs y'+y=d2 then you follow the differential path that you have made. (Threw this attack you can drop one round as once you found 1 key then the other key must also follow suit to be able to get the cipher text wanted)

To lower the probability of the correct key you repeat this process with a new path and a new chosen plaintext. If keys match between the two keys found then the probability goes up.

If this doesn't help try http://www.theamazingking.com/crypto-diff.php

And
http://www.cs.cmu.edu/~hannes/diffLinAES.pdf

Some defenses against DC is adding more rounds or by trying to get differential uniformity for the s-box.


OpenSSL aes-128-cfb does not produce expected size

Because CFB doesn't require padding similar to CTR and OFB mode of operation. These modes create cipher blocks and one uses the necessary amount from them.

In the case of openssl enc -K -iv the IV is not written to the output file output.txt. Therefore it has the same size as the plaintext in bytes; 61 bytes each for my file. In this case, you must handle the IV. Since you are also providing the IV, make sure that it is not used again. Otherwise, a crib-dragging can occur in the CTR mode or OTP's key re-use.

In the case of -k/-kfile/-pass, The IV and Key are derived from the key derivation method by using the user's password and the 8-byte random salt.
OpenSSL first writes file magic of Salted__ then 8-byte salt then the ciphertext into the file. Now the output size is your magic size + salt size + data-size. In my system, 8+8+61 = 77 bytes.

If ECB mode is used
openssl enc -aes-128-ecb -in cleartext.txt -k -pass -out output.txt

then the size is 80 bytes due to the padding. Of course, ECB doesn't use the IV and one should forget this mode!

CBC mode has similar results with ECB.

The derived IV size can change according to used encryption algoritm like 8-byte block cipher TDES and Blowfish requires 8-byte IV and 16-byte block ciphers like AES and Twofish requires 16-byte IV.

When using the password one might be careful about the entropy of the password and the used key derivation method. Using a Diceware password is recommended and at least PBKDF2 for the key derivation. OpenSSL provides various method for key derivation


Why RSA-KEM is more secure than Textbook-RSA?

Why is this not a problem?

Because for two different encryptions the random integers are drawn independently and uniformly at random over the whole range of the multipicative group $\mathbb Z_N^*$ (in practice this is usually approximated as $[1,n)$). The RSA assumption now literally states that it's difficult to recover the random value from its textbook RSA encryption if it is sampled in this way.

  if A and B again perform two key exchanges and it happens that $r_2 = 6943 r_1$ an attacker may be able to notice this and eventually even find out the random integers

Actually this won't happen because both $r_1,r_2$ are independently random, so is their group combination $r_1/r_2$ which has a chance of $2^{b-n}$ to be smaller than $2^b$ for $n$-bit RSA moduli, so for a really generous estimate suppose you are betting on $r_1/r_2$ to be guessable small, say smaller than $2^{60}$ and using weak 1024-bit RSA encryption, then you have a chance of $2^{60-1024}\approx 2^{-940}$ of the quotient being sufficiently small. This is a really negligible probability and likely won't ever be observed.


Salts are generally stored in the database with the password.

They shouldn't be timestamps, salts should be random values of 128 bits or more (though this may vary depending on the hashing scheme used.)

Salts improve security by making brute force attempts single-use: a password of "password" is likely going to be used many, many times. If it's hashed without a salt, then an attacker will instantly know which users used "password" as their password when they hash it. By hashing it with a per-user random salt an attacker will need to try at least one guess for each user, and hopefully several guesses. So salts help protect users who reuse passwords (there aren't that many hashing schemes) and users who choose bad passwords (attackers have to try all the bad passwords with each salt, instead of just trying them once.)


Node.js/OpenSSL crypto library equivalent of a Rijndael implementation

AES is Rijndael, but only for blocksize 128 and keysizes 128, 192, 256.
Rijndael also supports blocks of size 256 e.g. and other (intermediate) keysizes.
But AES is the official  standard and this standard only called for one block size 128 and those three keysizes.
The S-boxes are the same and quite fixed, yes.
Any goood Rijndael implementation shoudl be compatible with AES, with the right parameters.

aes-128-ecb should be standard AES for 128 bit keys. Others are modes with iv's as well, ecb is just "encrypt a block at the time", no mixing between blocks. ditto for other keysizes 192 and 256. I suppose aes128 should be the same as aes-128-ecb? I don't know Node.js at all, so maybe not.


What is SHAKE?

SHAKE is defined in FIPS 202 (PDF), it is a combination of SHA and KEccak (the original name of the candidate) by naming. What it does is that you give it an (arbitrarily long) input string and it returns you an (arbitrarily long) output string that has the usual properties of a hash (ie pseudo-randomness, collision-resistance, preimage-resistance, ...) while having a highly tunable length parameter which is useful in some applications.

  Is it like a SHA hash?

It basically is SHA-3 (slightly different actually) but without the fixed length restrictions on the output.

  Is there an algorithm that is used to make hashes? Or are hashes made
  some other way?

Technically speaking, you can use any hash algorithm to get hashes. Common choices include SHA3 and SHA-256 if you want something that is fast or Argon2, scrypt, bcrypt or PBKDF2 (in that order) if you want something that is slow.

As I can see from your question, you want to hash passwords. For this application, you really want to use slow hashes to slow an attacker down from trying all the passwords of your users quickly because they probably contain low uncertainity.


Note the first paragraph of the page:

  In public-key cryptography, the Station-to-Station (STS) protocol is a cryptographic key agreement scheme. The protocol is based on classic Diffie–Hellman, and provides mutual key and entity authentication. Unlike the classic Diffie–Hellman, which is not secure against a man-in-the-middle attack, this protocol assumes that the parties have signature keys, which are used to sign messages, thereby providing security against man-in-the-middle attacks.

It's worth mentioning that this is to be expected --- the notion of "identity" in cryptography is different than in real life, and is probably best thought of as "knows the private key corresponding to some public key".
Given this, users must have a way to share public keys free from adversarial behavior (otherwise an attack like you describe can easily go through).
This is the purpose of Certificate Authorities in the modern web, and while they're a cryptographically inelegant solution (they're explicitly a trusted third party, where much of cryptography can be phrased as removing trusted third parties), removing them seems difficult.

Note that this protocol explicitly mentions authentication, while DH doesn't.
This is what enables you to MiTM DH.
Of course, in practice people use a separate digital signature scheme with DH key exchange for authentication --- so what's the difference?

Something that should become fairly clear rather early in cryptography is that how you combine primitives matters.
ECB mode can use secure primitives but still be insecure.
Just like that, DH can use a secure signature scheme and still be insecure.
This was the basis of the Logjam attack in 2015, where you could MiTM TLS 1.2 via (among other things) taking advantage of poor use of signing in the DH key exchange.


Can an encrypted nonce be used for authentication?

No. Whether your presumption is true depends on the properties of the encryption scheme you are using. In a block cipher's CTR mode, or virtually any other stream cipher, an attacker can arbitrarily flip any bit so desired, and those bit flips only affect the bits in question.  For block ciphers in CBC mode, a bit flip garbles the plaintext block in which the bit was flipped, but introduces another bit flip in the same position in the next plaintext block.

As you can see, errors do not necessarily propagate, unless the encryption scheme was designed for such, nor are they necessarily easy to catch. As such, I would recommend against the scheme you suggested.

Instead of generating a nonce, why not use that space to append a proper MAC, perhaps HMAC. Note that if you go with this approach, you should use a separate, independent key for the MAC.

Alternatively, use one of the authenticated block cipher modes. I'd recommend GCM, personally, but for more details, see Matthew Green's "How to choose an Authenticated Encryption mode". I recommend this approach, as it is quite difficult to mess up.


If you just want to sign the shares like you said, then you don't need the shares to be in $Z_n^*$. You can just share over $F_p$ as usual. To sign a message, usually the message is hashed first and then the hash value is fed in the signing/verification algorithms. Therefore the fact that the shares are in $F_p$ will not affect signature generation and verification.

Shamir's secret sharing cannot be over $Z_n^*$ because $Z_n^*$ is not closed under $+$. But there are other secret sharing schemes over $Z_n^*$. As an example, the simplest one is this:

to share a secret $s \in Z_n^*$, choose $r_1,\ldots,r_{t-1}$ uniformly at random from $Z_n^*$.Compute $r_0 = s\cdot \frac{1}{\prod_{i=1}^{t-1} r_i}$.
Now you have $t$ shares $r_0,\ldots,r_{t-1}$, and you can distribute them to $t$ parties.
To reconstruct the secret, multiply all shares together and you get the secret $s=\prod_{i=0}^{t-1} r_i$.


Combining two almost universal hash functions

Under what circumstances is $g(f(m)) = g(f(m'))$ for any $m \ne m'$?  With what probability do these circumstances happen?

(Hint: Write $x = f(m)$ and $x' = f(m')$ and consider the probability of $g(x) = g(x')$.)


I invented SIDH. $E_0[\ell_A^{e_A}]$ has cardinality $(\ell_A^{e_A})^2$. Each of $P_A$, $Q_A$, and $R$ has order $\ell_A^{e_A}$ and they all generate different subgroups. This is possible because $E_0[\ell_A^{e_A}]$ is a non-cyclic group.


Calculating RSA Public Modulus from Private Exponent and Public Exponent

Summary: finding $n$ from $(e,d)$ is computationally feasible with fair probability, or even certainty, for a small but observable fraction of RSA keys of practical interest, including with a modulus much too large to be factored.
I'll assume

unknown $n=p\,q$ with $p$ and $q$ unknown distinct large primes of comparable order of magnitude, say $\max(p,q)<2\min(p,q)$.
given $(e,d)$ with small $e$ (e.g. one of the 5 Fermat primes).
a known one of $d=e^{-1}\bmod\varphi(n)$ (as often in textbook RSA) or $d=e^{-1}\bmod\lambda(n)$ (as in FIPS 186-4) holds.

It follows from their respective definition that $\varphi(n)=(p-1)(q-1)$ and $\lambda(n)=\varphi(n)/g$, with $g=\gcd(p-1,q-1)$.
It holds $h\,(p-1)(q-1)=(e\,d-1)$ or $h\,(p-1)(q-1)=g\,(e\,d-1)$ for some unknown $h<e$, and a $g$ that can be found by enumeration, for it is a small even integer, often $2$ (always in some key generation strategies), rarely above $10$.
In the cases where we can fully factor $e\,d-1$, that will leave an enumerable number of options for re-arranging its factors into $p-1$, $q-1$ and $h$. Given the size and primality constraints on $p$ and $q$, few possibilities will remain, often a single one. $n$ follows.
That can sometime work in cases where the best factorization obtained for $e\,d-1$ is partial, but we are lucky enough that the remaining large composite has all its factors in a single of $p-1$ or $q-1$. This is possible only if that remaining composite is less than $\max(p,q)$, and then only with low probability.
The proportion of keys where the methods works depends on the modulus size, on how hard we are willing to try to factor $e\,d-1$, and on how the primes $p$ and $q$ have been generated (in particular: at random, or with a large known prime factor in $p-1$ and $q-1$ in consideration of Pollard's p-1 factorization. In the later case, the magnitude of that factor will be important. If high (e.g. 60% of the bit size of the primes), the task will be hard; but typical parametrization is lower).
The factorization strategy could be similar to that for arbitrary integers:

pull the small factors of $e\,d-1$ by trial division.
pull more small factors by Pollard's rho
optionally but somewhat advantageously, some Pollard's p-1.
optionally but still somewhat advantageously, some William's p+1.
a lot of ECM, where most of the effort should be when we get barely enough $(e,d)$ pairs to hope find one allowing success.
perhaps, if a large composite remains that needs to be factored, MPQS or GNFS.

Illustration, based on the the 829-bit RSA-250 recently factored.
We get $e=65537$ and the following 828-bit $d$ known to be $d=e^{-1}\bmod\varphi(n)$.
1219002363472329316632678572665837077877528004905520939230037996503041169769564562618818603930146413036298872224725717654149810234132887053185714832075764978825457518728410705223332728199047961645304133836997233492855592278022423674340390891560261753

We compute the 844-bit $m=e\,d-1$, and pull out its smalls factor $2^3\times3\times5\times13\times6221\times6213239\times440117350342384303$ (that's seconds), leaving a 740-bit $m_1$ to factor.
The command¹ ecm -pm1 1e7 <m1 found a 73-bit factor $8015381692860102796237$ in <3s, leaving a 667-bit $m_2$ to factor.
The command ecm -pp1 1e7 <m2 found a 67-bit factor $101910617047160921359$ in <7s, leaving a 600-bit $m_3$ to factor.
The command ecm -pp1 1e8 <m3 found a 72-bit factor $4597395223158209096147$ in <77s, leaving a 528-bit $m_4$ to factor.
We need to factor that $m_4$, because it is still too large to be a divisor of $p-1$ or $q-1$. The command ecm -pm1 3e8 <m4 failed after ≈85s. The command ecm -pp1 1e8 <m4 failed after ≈69s. The command ecm 1e8 <m4 launched repeatedly on multiple cores repeatedly failed after ≈272s. We would have been very lucky if that had worked.
I did not really factor $m_4$ with GNFS², but that's well within reach. The factors of $m_4$ are  276-bit and 253-bit (the first two in the list below)
$p-1$ and $q-1$ are even, thus we have these 12 factors to split between $(p-1)/2$, $(q-1)/2$ and $h$:
72769022935390028131583224155323574786067394416649454368282707661426220155269516297
11015842872223957032465527015746975907581857223611379316467045416408679146689
8015381692860102796237
4597395223158209096147
101910617047160921359
440117350342384303
6213239
6221
13
5
3
2

There are a mere $3^{10}<2^{16}$ possibilities to explore after we assigned the first two entries to $(p-1)/2$ and $(q-1)/2$. We want to explore those with $\max(p,q)<2\min(p,q)$ and $h<e$. Pruning this tree requires only addition of approximate logarithms. That's a near-trivial knapsack problem. I've not coded it, but I'd be surprised if there was a solution yielding $p$ and $q$ prime other than $h=2\times3\times6221$, and these $p$ and $q$ which immediately yields $n=p\,q$, here RSA-250.
33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711
64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367

¹ GMP-ECM implements carefully optimized Pollard's p-1, William's p+1, and ECM. I let it use a random seed, thus some of the results may take a few runs to reproduce.
² I'm hearing a lot of good of the implementation in CADO-NFS.


Provably Secure Post-Processing of a True Noise RNG?

If your entropy extraction algorithm is well written and satisfies the relationship (entropy in) > (entropy out), there is no issue with recovery.  A lot of TRNGs do not even use cryptographic hash functions for extraction. A simple matrix multiplication acting as a compression function will do (as long as its compression window is wider than any length of auto correlation).

You can't recover the raw data if my above relationship holds true due to the pigeon hole principle, but even if you did it would be pointless.  That entropy has been used up and will never again be used. The TRNG will then create more entropy for the next set of random numbers. So as long as you're using a true random number generator with a good entropy extraction technique your concern is moot, quantum attack computer or otherwise.


Are one time pads still secure when using randomly generated words as the pad?

Do those look like English words to you?

WHTVI AUCFU RETFK OMSAL
MYMNE ZIEGP UKVTF WZHOK

(Quoted from the page.)

When they say ‘5-letter words’, they don't mean words chosen from an English dictionary.  They mean that they rolled a d26 five times independently and strung the resulting letters together, with spaces between every five letters and line breaks between every four ‘words’ for legibility.  This method is just as secure as using a d2 (i.e., flipping a coin) to choose the bits of a binary one-time pad; it just uses a different alphabet.


A few things have gone wrong:

You've reversed the initial state, but continued to shift from left to right. If you do reverse then the shift is from right to left.
You've confused the output bit (the oldest bit in the register) with the feedback bit (the new value that is introduced after shifting)
The feedback rule for the polynomial $x^4+x^3+1$ is $s_{i+4}=s_{i+3}\oplus s_{i}$ and so in your notation would be $s_4$ xor $s_1$

With this borne in mind the first two rows of you table should read as follows:
s1  s2  s3  s4  feedback bit (s4 xor s1)  output bit (s1)
1   0   1   1   0                         1
0   1   1   0   0                         0...

and so on


Is hybrid encryption required to use Attribute based Encryption to encrypt messages?

No, this is not required by Attribute Based Encryption (ABE) itself.

However it is a common practice to use so-called "hybrid encryption" when you want to encrypt data using public-key encryption, for multiple reasons:

it sometimes avoids the need for padding of the message: if your ABE scheme works on messages that are of size 256 bits, for instance, then using a AES key of 256 bits fits naturally in that message space. (Although in practice you often have some rejection sampling to do because the whole 256-bit space is not necessarily the universe of the messages.)
it allows to ignore the limits of the public-key encryption scheme you are using, that is the converse of the previous point: if you can only work with 256 bits messages but want to encrypt more than 256 bits, then you have a problem, whereas AES (with a good mode of operation) (or the underlying stream cipher of your choice) is not limited in the size of the data you can encrypt.
probably one of the most important reasons: the performance! ABE (and more generally public-key cryptography) schemes are super slow in practice, while AES is super fast, so in order to have decent performance it makes sense to use as little public-key cryptography as possible.

So in the end, most practical instantiations of ABE (not that I'm aware of any) would be probably better off using ABE as a way to broadcast keys to access symmetrically encrypted data, à la Attribute Based Broadcast, rather than encrypted messages directly, excepted if the messages are really short!

As it wouldn't better to use hybrid encryption on message of the same size as the keys of the underlying symmetric cipher.

But to sum it up, in the end, there is nothing that restricts you and says you have to use hybrid encryption when using ABE.
As long as the ABE scheme you are using is okay encrypting messages of the size you need to encrypt, then you could use ABE directly on the messages and it would not reduce the security of the ABE scheme when compared to a construct where you'd use hybrid encryption to first encrypt the message with a symmetric cipher with a randomly generated key, say AES, and then use your ABE scheme to encrypt the random symmetric key for the set of attributes that are allowed to access that message.

And yet you should use it in practice!

Hybrid encryption schemes are actually a good thing in practice, because they have many nice features.
Firstly, notice that when doing hybrid encryption, we have two main components:

a Key Encapsulation Mechanism to protect the key, in this case the ABE scheme
a Data Encapsulation Mechanism to protect the data, in this case AES

And the encryption works by generating at random a key $\mathcal{K}$ that is used to encrypt the data $M$ using the DEM algorithm $DEM_\mathcal{K}(M)$, and then that key $\mathcal{K}$  is encrypted using the KEM algorithm for the public key $P_k$ of your choice  $KEM_{P_k}(\mathcal{K})$, and the resulting ciphertext is the tuple $\left(KEM_{P_k}\left(\mathcal{K}\right), DEM_\mathcal{K}\left(M\right)\right)$.

A really nice property of the KEM-DEM construct is that if the DEM and the KEM are both "CCA2-secure" (secure against adaptative chosen ciphertext attacks), then the resulting hybrid encryption scheme is also CCA2-secure.

Whereas, for instance, if you were to encrypt a longer message than what your public-key algorithm allows, and decided to do so by "chunking" the message into "blocks" of the right size, and then encrypt using ABE each block of your message and send all the blocks together as you ciphertext, your scheme would trivially not pass the "CCA game" as we commonly use it, whereas if you were to use a CCA2 ABE scheme as a KEM and AES-GCM (or any other IND-CCA2 stream cipher) as a DEM, then you would still pass it.

For more details, including a proof of the former, I refer you to this paper by Cramer & Shoup, section 7.3.

It is also interesting to see what are the necessary conditions on the security of your DEM and KEM in order to have secure scheme. This online paper by Herranz et al. (or the published one) has a good coverage of the question.

The other good thing with a KEM-DEM scheme is the fact that such schemes are significantly more efficient than pure public-key schemes, as soon as the message would require more than one public key operation invocation.


Note the relation between $r_1$ and $r_2$
Infer the relationship internal variables need to have because of this
Write down the equations to calculate $(r_1,s_1),(r_2,s_2)$ and use the above relationship
Pretend the equations would be over $\mathbb R$ and solve the above system of equations for $a$
Now plug-in the values and actually perform the modular arithmetic
You now should have recovered the private key


Hardware Gaussian random numbers for lattice-based cryptography

You are confusing discrete Gaussian sampling with Gaussian sampling.
A discrete Gaussian of parameters $\mu, \sigma$ is a random variable supported on $\mathbb{Z}$ with pmf:
$$\Pr[X = k]\propto \exp(-\pi \|x-\mu\|^2/\sigma^2)$$
A continuous Gaussian of parameters $\mu, \sigma$ is a random variable supported on $\mathbb{R}$ with pdf:
$$\Pr[X = r] \propto\exp(-\pi \|x - \mu\|^2/\sigma^2)$$
One natural hope would be that discrete Gaussians are simply "Continuous Gaussians rounded to the nearest integer". This is not the case (one is left with two distributions which, while similar, are not identical.
One particular difference is that I don't believe the sum of two rounded Gaussians is rounded Gaussian, but under suitable restrictions this holds for discrete Gaussians). That being said one can adapt certain proofs to use "rounded Gaussians", which this paper by Hulsing et al. does.

Note that the discrete Gaussian distribution is much harder to sample from than continuous Gaussians.
While (under suitable restrictions) it still satisfies a "convolution theorem" that sums of discrete Gaussians are discrete Gaussians, one needs certain restrictions which don't exist in the continuous case.
Another example of a difference is that no analogue of the Box-Muller Transform exists for discrete Gaussians, which is a fairly efficient way to generate continuous Gaussians from a uniformly random source.

Sometimes one can even use a random variable which seems less connected to Discrete Gaussians, namely Binomial random variables (which are quite efficient to sample from in constant time). See page 14 of the Kyber paper (a current NIST PQC round 2 KEM candidate) for some discussion of this. Dilithium (a NIST PQC round 2 signature candidate) uses uniform noise due to concerns with implementing discrete Gaussian sampling efficiently in constant time.

As for a good introduction to the literature, there has been some work before about hardware implementations (here, although I don't know enough about hardware to evaluate the work.
Beyond this Micciancio has some links to recent work, although it is missing some papers from the last year (which are essentially updates to current NIST PQC candidate's samplers).

I generically like Michael Walter's exposition of existing methods (see for example section 6 in this paper or section 3 of this paper). If one starts there, and then additionally looks at recent work on NIST PQC round 2 candidates (in particular the lattice based signature schemes Falcon and qTESLA) that'd be a very good start.


split up sha256 hash and compare indiv block results

No, if the crypto accelerator can do a straight SHA256 computation of up to 4MB messages, and nothing else, well, you're rather stuck; there's no way to combine independent sha256 hashes into a larger hash.

On the other hand, perhaps the designer of the accelerator provided some additional hooks.  One thing that they might have provided is an 'incremental' hash; where you give the messages in pieces (and they save the intermediate state between requests).

Alternatively, if they have a mode where:

You provide the IV (rather than using the fixed IV that SHA256 uses)
They don't do the final SHA256 padding; instead, they take an integral number of blocks, and output the intermediate state.

If so, then you can do the incremental processing yourself.  You would start with the SHA256 starting IV, and send the first 4MB (or smaller, as long as it is a multiple of 64 bytes), ask to do hashing with this mode, and give you the intermediate state.  Then, you use the intermediate state as the IV, and send it the next 4MB, and get that intermediate state.  For the final block, you would apply the SHA256 padding yourself (unless the hardware will do that for you; it's not the standard padding of the final block, because the message length will need to include the entire message) and the 'intermediate state' of that is the SHA256 of the combined message.


Fiat Shamir transformation of zero knowledge proof

You are correct about the attack, given the way you have defined the Fiat-Shamir-transformed protocol.

Since Fiat-Shamir is subtle for multi-round protocols, the standard way to resolve this is to use parallel instead of sequential composition. Start with a protocol that has soundness error 1/2, and run it $k$ times in parallel (not in sequence) to amplify its soundness error to $1/2^k$.

Then apply Fiat-Shamir to the resulting protocol, which just has one round. All the challenge bits are generated from a single call to $H$ as $c_1 \cdots c_k = H(a_1 \cdots a_k)$. Note that if the prover is proving a false statement, then for any first protocol message $a_1 \cdots a_k$ there is at most one $c_1 \cdots c_k$ for which she can generate a totally convincing response. With $q$ queries to $H$, an adversary can find such a valid first message with probability only $q/2^k$.


It would be good if you revisited the definition of perfect secrecy in the book. What you are proving for the first candidate scheme is a correctness property, not a security property (in general), and not perfect secrecy in particular.

Informally, what you are proving is that encrypting and then decrypting will preserve the original message. What you need to prove is that guessing $m$ knowing $c$ (where $c=Enc_k(m)$) the is as hard as guessing $m$ without seeing $c$.

As a general strategy, a good way to prove something secure is to base your proof on similar, already proven constructions. Scheme 1 is very similar to one-time pad, so the proof should be adaptable.

For proving something insecure, it's often simpler to describe a specific attack or even a counterexample. Scheme 2 for example is not perfectly secret. Since you are given small, concrete values, you can try and work out some example encryptions using pen & paper to see if something's wrong.


How to find the time complexity of modular multiplication?

Hello, welcome to crypto.SE.

This is not cryptography, but I will answer it with a simplified example to give you the intuition. Lets consider $123 \times 456$.

    123
  x 456
  -----
    738
   615
+ 492
-------
  56088

Right ?

How did you get $738$? Obviously you did $6 \times 3 + 6 \times 20 + 6 \times 1$. Therefore you made 3 multiplications.
Should the first number be $m$ long, you would have had $m$ multiplications.
Because the second number is also $m$ long, you would have to do this $m$ times hence the $O(m^2)$.

From the Handbook of APPLIED CRYPTOGRAPHY, page 71

  Let $n$ be q positive integer. As before, the elements of $Z_n$
  will be represented by the integers $\{0,1,2 ..., n-1 \}$.

  Observe that if $a,b \in Z_n$, then
  $$(a+b)\mod n = \begin{cases}a+b, &\text{if}\ a + b < n\\
a+b-n &\text{if}\ a + b \ge n\\ \end{cases}$$

Note that in term of bit complexity we are in $log(n)$

  Hence modular addition (and subtraction) can be performed without the need of a long division. Modular multiplication of $a$ and $b$ may be accomplished by simply multiplying $a$ and $b$ as integers, and then taking the remainder of the result after division by $n$.

Without any optimizations, note that taking the reminder is just applying at most $m$ subtraction of $m$.
Hence a modular multiplication is at most $2 \times m^2$ operations therefore $O(m^2)$ (and bitwise complexity $O(log^2(m))$).


Common Crypto C api: Why both CCCryptorUpdate() and CCCryptorFinal()?

Re-phrasing the comments into an answer as the question changed during comments:

CCCryptorFinal is necessary when CCCryptorUpdate is being used and padding is specified in order to know when the last block is being encrypted so the padding can be added.

The advantage to splitting up the process might be to use smaller buffers, etc, Consider encrypting a multi-GB file.

Additionally there are encryption modes that are not supported by the one-shot CCCrypt which only supports ECB and CBC modes.


How many bytes of data does AES 256 encrypt at one time?

AES has always 128-bit block size with 128,192 and 256-bit keyspaces.  Therefore, you can encrypt 16-byte at a time if you are using ECB and CBC modes. By using CTR mode you can encrypt 1-bit to 128-bit.

Some people confuse AES with Rijndael where AES is a variant of the Rijndael. Some old libraries use the Rijndael (see RijndaelManaged). Rijndael can have 128, 160, 192, 224, and 256-bit block size. Note that these are not standardized, see FIPS 197.


How is HMAC hashed message decrypted on the receiver side

Actually the HMAC value is not decrypted at all. The recipient takes all the needed input and she computes the HMAC on her own side and check if the result she got it is equal to the value on the message she got.

You can roughly see the HMAC algorithm as an symmetric key signature. You cannot decrypt an HMAC, you only check that the value is correct.