Two possible plaintext's using OTP decryption

Which of the plaintexts is more likely to be the original plaintext and why?

A very literal and devious answer to the question (at least as you have posed it) is that 'ATTACK AT DAWN' is more likely to be the original plaintext because it can be independently established that attacks at dawn are more common than attacks at noon.

Which means there's a subtle flaw in the question: what cryptanalysis is supposed to accomplish is to use the ciphertext as evidence that favors some candidate plaintexts over others. The point isn't really which plaintext is more likely, it's whether an analysis of the ciphertext can rationally demand that you change your mind about their relative likelihood. Like, you go into it thinking that 'ATTACK AT DAWN' is twice as likely as 'ATTACK AT NOON', but analysis of the ciphertext compels you to conclude some other proportion.

The point of all this is the often-missed nuance that the famous perfect secrecy of one-time pads is not that the attacker cannot figure out what candidate plaintext is more likely, but rather that analyzing the ciphertext is of no use in achieving that end.


If $x=y \mod \phi(p)$, then $H(x)= H(y)$. Then it doesn't seem collision resistant.
For the same reason not second preimage attacks. $H(x + \phi(p))= H(y)$.
(If $p$ is prime $\phi(p)=p-1$, thus it's easy to compute it).
About the preimage attack, it's completely equivalent to discrete logarithm in $\mathbb{Z}^{\star}_p$, then you have to be carrefull about the choice of $p$ (basically $p-1$ should have a huge factor).


Yes, the principle to use a common password and a unique salt per file with a key derivation function is a good and acceptable practice, as you generate the salt randomly and with the right size. The uniqueness of the salt guarantees a different password per file (actually one password per salt, so: do not reuse a salt, use a csprng).

You forgot to mention (or to design) how you're are going to protect the cipher integrity. XTS mode does not provide this property, you should add a message authentication code (MAC) as HMAC.

It would be probably better and simpler to switch to another mode which provides confidentiality and integrity as GCM or OCB. The second reason for switching from XTS that is that mode is designed to be used in Full Disk Encryption context and encrypt disk sectors and not a whole file. some other reasons.

Don't forget to store the salt with the ciphertext and protect its integrity, too.


Are there any Truth Table to Boolean expression converters?

It depends on what you are interested in, when building your expression. If you want to optimize for speed and/or expression size, then the problem is hard, and no good solution is known. You can either try to enumerate all expressions, looking for a match with your table (this is exponential in the size of the expression, so it becomes prohibitive real fast); or you can start with a generic expression as a tree of multiplexers then try to find local shortcuts.

You can often work with the "fake multiplexer": for inputs $a$ and $b$, and control $c$, output $a \oplus (b \wedge c)$: in this way, the bit $c$ selects between values $a$ (if $c = 0$) and $a \oplus b$ (if $c = 1$). For a function $f : n \rightarrow 1$ ($n$ input bits, $1$ output bit), you work recursively:

An expression with no input is either $0$ or $1$ (it is a constant).
You define $f_0 : n - 1 \rightarrow 1$ such that $f_0(x_1, x_2,... x_{n-1}) = f(x_1, x_2,... x_{n-1}, 0)$ (that's the function $f$ when the last bit is $0$).
You define $f_1 : n - 1 \rightarrow 1$ such that $f_1(x_1, x_2,... x_{n-1}) = f(x_1, x_2,... x_{n-1}, 1)$ (that's the function $f$ when the last bit is $1$).
You compute the boolean expression $e_0$ for $f_0$, and the boolean expression $e_1$ for $f_0 \oplus f_1$.
The expression for $f$ is now $e_0 \oplus (x_n \wedge e_1)$.

There has been such efforts for some table-based operators used in cryptographic algorithms, e.g. DES S-boxes. See also this article.

(Note: if you have only bitwise AND, OR and XOR, and not access to constants, then you cannot build all functions; in particular, you won't be able to make a $1$ out of an all-$0$ input. If you really don't want a NOT or the equivalent "$\oplus 1$", and the output of your function for an all-zero input is $1$, then there is no solution. On the other hand, if the function output for an all-zero input is $0$, then you can make a serviceable $1$ by ORing all input bits together.)

(Note 2: if you want to optimize for speed on software platforms, be aware that not all processor architectures offer the same set of operations. On some processors you have elementary XORNOT or NOTXOR. This can change the achievable speed quite a lot.)


Prime Factorization in RSA always leads to the product of two primes?

By construction, RSA moduli are the product of two large primes.


Why does image size increase after steganography?

I'll assume the question really is: when I perform low-order-bit steganography on an uncompressed image (inserting 6 bits encoding a character into the low-order bit of 6 bytes coding the R, G and B channels of 2 pixels), I find that compressing the resulting image gives a bigger file than compressing the original image for a given setting of the program used to compress.

The reason likely is that the process which made the original image is such that the low-order bits are very correlated with the other bits (for example this could be because of characteristics of a sensor; or because the original image has been compressed by some lossy algorithm, then decompressed); and that correlation is lost by replacing the low-order bits.

The observed effect will depend on the nature of the compression technique used, and will tend to be be most perceivable for lossless compression techniques (GIF, PNG, lossless JPEG), which are the only ones which allow correct decoding of the hidden message.

If the low-order bits of the original image where random, the observed effect would likely vanish, or even perhaps be inverted (assuming the enciphered message has redundancy).


Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?

There is a reduction from DL to RSA if the DL oracle accepts composite modulus. For prime modulus, a reduction is not known. I copied the following from this wikipedia page with minor edits.

Let $n = p\,q$ be an RSA modulus.

Generate random integer $a$ co-prime to $n$ and a random integer $x$ taken in an interval much larger than $n$, say $[1,1000n]$.
Compute $b = a^x \bmod n$ but don't tell $x$ to the 'discrete log oracle'.
Instead ask it to find the discrete log of $b \bmod n$ (to base $a$). Let the value returned by the oracle be $y$.
If $y$ is a solution, then so is $y\pm\varphi(n)$ where $\varphi$ is Euler's totient function, and $0<\varphi(n)<n$. It follows there are at least $1000$ solutions $y$ that lie in the interval of $1000\,n$ integers from which we picked $x$ uniformly at random, thus the oracle has probability $\le\frac1{1000}$ of finding $x$. There is thus a high probability that $y\neq x$. If so, $|x-y|$ will be a multiple of the order of $a$, which can easily be used to factor $n$. I will not go to the details of factoring once (a multiple of) the order of $a$ is known (since this is a well known method, also used in Shor's algorithm). If we are unlucky and $x=y$, then we start over.


Actually, it does not matter if Bobs number is greater or less than Alices number. In either case Bob can compute $n_A$ (here I denote by $n_A$ and $n_B$ the private numbers of Alice and Bob respectively). Bob could simply note the number of boxes with one pebbles in them and the number of boxes with two pebbles in them, lets call these numbers $p_1$ and $p_2$ respectively. Also lets by $N$ denote the total number of boxes. If $p_2 = 0$ then $p_1 = N - (n_A - 1) + 1$, and if $p_2 = 1$ then $p_1 = N - (n_A - 1) - 1$ . In general we can write this as $p_1 = N - (n_A - 1) + (1 -2p_2)$. If we rewrite this we get $n_A = N + 2(1 - p_2) - p_1$. So you see, regardless of the relation between $n_A$ and $n_B$ Bob can compute $n_A$.

You could solve this by simply not letting Bob shake any boxes, so that he never learns $p_1$ or $p_2$. I.e., in the last step instead of Alice and Bob shaking every box, you should just send Alice into the room to shake all the boxes. She will then learn the result, and can tell the result to Bob. In fact, in this case Alice does not have to shuffle the boxes, only Bob needs to do that.

You could argue that in this case Alice may cheat and tell Bob an incorrect result. However, you are already trusting Alice to follow the protocol in the previous steps, so this shouldn't be a problem.

Note, that if a box contains two pebbles it means that $n_A \leq n_B$, not $n_A < n_B$ as you state.


Is there a standard notation for a message concatenated with its signature?

In formal papers, the standard way would be to either cleverly shorten it or to omit arguments.

For example you could write something like $M:=...$ (but please replace the dots with the actual message composition) at the end of your algorithm:
$$\operatorname{Output} (M||\sigma_K(M))$$

The alternative to this (a shortened version of your approach) would be to say that $\sigma$ is the signature in the text or define $\sigma$ somewhere and then use it as a simple variable. (outputting $(M||\sigma)$).

If you want to write a formal specification there are also ways to express a signed construct such as TLS' digitally-signed.


Secure symmetric encryption algorithm for any-size base62 data

If you define your encryption to be $C=E_{62}(E_k(D_{62}(P)))$ and your decryption to be $P=E_{62}(D_k(D_{62}({C})))$ where $P$ is your encoded URL then you've brought back your problem to finding an encryption function for $l$ bits, where $l$ is the size of $D_{62}(P)$. After that you can "just" look for a Format Preserving Encryption primitive for those $l$ bits. If the encrypted URL is allowed to be larger than the unencrypted URL then you could use CTR mode with a nonce of 8 random bytes.


How to deal with a cipher with addition and XORs combined together?

Note that, for the least significant bit, addition mod $2^n$ and xor are the same.  So if the cipher doesn't include rotation then you can set up a linear equation in the least significant bits of the plaintext, ciphertext, and round keys that holds with probability 1 (if the cipher breaks the state up into two or more distinct parts, like a Feistel cipher, then you need to consider the least significant bits of each part).  That means with a single known plaintext you can extract a single bit of information about the least significant bits of the round keys.

This single bit of information narrows down the possibilities for the least significant carry bits, which enables you to gain one more bit of information about the LSBs of the round keys by observing what happens to the least 2 significant bits of the plaintext and ciphertext.  That narrows down the possibilities for the LSB carry bits even further, enabling you to gain another bit by looking at the least 3 significant bits of the plaintext and ciphertext, and so on.  By progressively narrowing down the possibilities for the round key LSBs, you can gain complete knowledge of those bits (so long as the number of rounds does not exceed the 'part' size of the cipher), and then you can attack the 2nd LSBs using the same techniques.

To illustrate, take this very simple example cipher: $E(x) = ((((x + R_0) \oplus R_1) + R_2) \oplus R_3)$, where the cipher operates on blocks of $n$ bits, "+" is addition over $2^n$, $\oplus$ is xor, and each 'round' key $R_i$ is an $n$-bit independently selected random string.  From this, if $X^j$ denotes the $j$th bit of a given word (zero being the least significant bit) and $P$ and $C$ denote the plaintext and ciphertext respectively, given a single known plaintext the following equation gives you a single bit of information about the four round keys:
$$P^0 \oplus C^0 = R_0^0 \oplus R_1^0 \oplus R_2^0 \oplus R_3^0.$$
Let us suppose that the result is zero.  That means either all four least significant bits of the round keys are zero, or two of them are zero, or none of them are zero - there are eight possible arrangements in total.  If you get two known/chosen plaintexts where $P^1$ is fixed to some value and $P^0$ varies, and look at the resulting $C^0$ and $C^1$, you can narrow those 8 possibilities for the LSBs of the round keys down to 4 possibilities.  In a similar fashion those four can then be narrowed down to two, and then to one, using a few more known/chosen plaintexts.

With the influence of the least significant carry bits known, you can apply the same technique to determine the four $R^1$ bits.  That way you can progressively reveal almost all the bits of the round keys, using relatively few known/chosen plaintexts.

Because of this sort of vulnerability in using only addition and xor, ARX ciphers include rotation (that's the 'R' part of the name).


Decrypting a small Message using RSA with a Private Key

In step 9, you decrypted the ciphertext, 128, to the original message, 2. That's it. You're done with the toy example of naive RSA encryption/decryption.

Using RSA in real life, you would apply padding, such as OAEP (also known as PKCS#1v2), to your message before raising it to the e power modulo n.

If the plaintext you're trying to encrypt is quite short, say less than half as long as the RSA modulus, you might agree with the recipient to apply RSA directly to the message.

Normally the plaintext isn't that short. What you do is encrypt and MAC the plaintext with a symmetric cipher and MAC algorithm that you agree on with the recipient, using a randomly selected key for the symmetric cipher and a randomly selected key for the MAC. Then you use RSA with a 'message' consisting of the key to the symmetric cipher and the MAC key. You send your recipient all of (A) the RSA ciphertext, (B) the ciphertext from the symmetric cipher, and (C) the MAC. The recipient decrypts the RSA ciphertext (A), unpads it and obtains the keys for the symmetric cipher and the MAC. With those in hand, verifies the MAC (C) of the ciphertext (B) and finally decrypts the symmetric ciphertext (B) to obtain the plaintext.


What is the difference between a sealed box and a normal box in libsodium?

The premise of boxes is that Alice and Bob know each other and write to each other.  Alice can use a box to send a message to Bob.  On receipt of the box, Bob knows (a) it came from Alice, and (b) nobody else could have read or tampered with it.

The premise of sealed boxes is that Bob has an anonymous dropbox.  Alice can use a sealed box to send a message to Bob.  On receipt of the box, Bob knows nobody but the sender could have read or tampered with it.  But he knows nothing about who the sender was—it could have been Alice, or Charlie, or Dominique.

The nonce is only required to be distinct for each message Alice sends to Bob, and vice versa.  For example, Alice might count the number of messages she has sent so far, and use that number as a nonce.  If the nonce is large enough, say ≥192, as it is in crypto_box_curve25519xsalsa20poly1305 (but not crypto_box_nistp256aes256gcm where it is 96), it can safely be chosen uniformly at random for each message and affixed to the ciphertext.  The nonce need not be secret.

Neither boxes nor sealed boxes enables a third party to verify the authenticity of a message.  For that, you need digital signatures.

If Bob's private key is ever compromised, whether for boxes or for sealed boxes, or if Alice's private key for boxes is ever compromised, then any message Alice has sent to Bob can be decrypted.  To avoid this, protocols like Signal (a) regularly generate new keys and promptly erase the old keys for things like boxes,* and (b) use long-term key pairs only for digital signatures to assert what the user's current box public key is, so that compromising the long-term private keys doesn't enable retroactive decryption.

* A protocol that prescribes when to promptly erase keys is sometimes said to have ‘forward secrecy’, a term I prefer to avoid because in its glibness it obscures when the keys can be erased—which obscurity may serve to conceal lurking vulnerabilities like TLS session resumption even in sessions that use ‘forward secrecy’ cipher suites with ephemeral Diffie–Hellman key agreement.


Do both client and server need to implement OpenSSL protections to protect from CBC attacks

Yes, both the client and the server must have this mechanism enabled to get full protection from BEAST and similar attacks.

In particular, if the client is a browser with scripting capabilities, it is the client side implementation that must send empty packets before each content packet. Enabling this feature server side only, just means that the server will send such empty packets. This will provide no protection from script based attacks against browsers.


Extracting secret image from cover image

The EMD method is a little outdated. The state of the art are Syndrome Tellis Codes. Please, check:

http://dde.binghamton.edu/filler/pdf/Fill10tifs-stc.pdf

In the EMD method, n pixels are used to carry one secret digit. Therefore, to extract this digit you need to use the same n pixels. The receiver needs to know what pixels are used by the sender.


Technical term for hash value being uncorrelated to input message?

That a small change to the input message will produce a massive
  unpredictable and seemingly uncorrelated change to the output hash
  value?

It sounds like you're looking for the avalanche effect.


Properties of a single-message protocol using AES

Non repudiation : No, as the sender can claim that the other person sent himself the message
Data Integrity : No, as the cipher text can be corrupted in the midway
Authentication : Yes, the message is indeed sent by other sender as the key is known only to sender and receiver
Confidentiality: Yes, as the key is only known to receiver and sender

Hope this helps


Is AES/CBC/NoPadding vulnerable to padding oracle?

If there is no padding then the cipher is not vulnerable to padding oracle attacks that originate from the cipher implementation. The cipher expects full blocks of ciphertext and simply decrypts them to whatever information, even if that seems random.
However, padding oracle attacks are part of a larger set of attacks called plaintext oracles. Plaintext oracles react to information that is released by an implementation when the plaintext is altered. As CBC doesn't provide message integrity the attacker can perform any kind of change.
The most simple example is if the code itself pads / unpads the message using e.g. PKCS#7 padding. In that case, the padding oracle is not present in the cipher, but present in the code surrounding the cipher. It would be just as bad as a padding oracle attack that was created by using the cipher implementation.
Another, less obvious examples of plaintext oracles are the attacks on the XML-encryption standard. Those are at least as efficient as padding oracle attacks.

Of course, as always, the plaintext oracle must need to be present; for instance, local file encryption may not expose an online oracle. And as always, plaintext oracles are best avoided by adding a message authentication tag for message integrity (such as a HMAC calculation over the IV and  message, or by using an authenticated / AEAD cipher such as GCM).


Steam ciphers work by encrypting the counter / nonce with the master key (generated from a cryptographically secure psuedo-random number generator).

For example with AES in CTR mode, you would run the usual AES Encryption algorithm, but instead of inputting a message you input the counter/ nonce.

This creates a stream. A portion of the stream equal to the length of the message you want to encrypt is XORed with the message, and sent to the recipient.

As for the psuedo-random generator, a stream cipher can be used as a PRG, but there isn't a PRG in the stream cipher itself, as both parties have to be able to construct the key and encrypt / decrypt the message.


PBKDF2 is deliberately slow (and gets slower and safer with more iterations, so you want to make it as slow as you practically can).  Because of this, you should generally avoid running it more times than you absolutely need to.

Using the same key and a different IV for each encrypted document is indeed OK — that's what the IV exists for.  Most encryption schemes do have limitations on how much data and/or how many distinct messages you can safely encrypt with a single key, and you should check the documentation for the scheme you're using to make sure you're not at risk of exceeding these limits.  But usually they're fairly generous, and if you limit yourself to, say, $2^{32}$ distinct documents per key, of up to $2^{32}$ cipher blocks each, you're probably fine.  (In fact, you might need to worry more about message length limits than about message count limits, depending on which encryption mode you're using, especially if some of the documents you're encrypting might be larger than 64 GB.)

Alternatively, if you'd prefer to use a distinct key for each document, you can achieve that efficiently in (at least) two ways.  One is to first derive a single master key from the password using PBKDF2 (with a high iteration count), and then derive the document keys from the master key using a faster KDF such as HKDF-Expand, with a distinct salt/info value for each document.  The other method is to generate a random key for each document, encrypt that key using the master key (derived from the password using PBKDF2, as in the first method), and store it alongside the encrypted document.

Ps. Your question seemed familiar to me, so I checked to see if I might have answered something similar here before.  While I didn't find any exact duplicates of your question, I did locate a couple of related questions that you might find useful, such as these:

Is a PBKDF2-derived master key easier cracked if very many Data Protection Keys are derived from it?
Suggestions for improving encrypt-then-mac flow
What is the correct way to implement PBKDF2 + AES CBC + HMAC?


Is it possible to determine a PGP public key from encrypted data?

From this answer:

  The key ID of the recipient is included in plain-text in the encrypted file. Other possibly interesting information "hidden in plain sight" is just the size of the file, or the name of the encrypted file (if someone just sends it without alteration of course.)

  What you might not realise is that the recipient Key ID is effectively an optional field. ...

and

  You can encrypt using the -R (or --hidden-recipient) flag with gpg to avoid revealing the recipient's public key in an encrypted message.

and

  ... However, also see this answer for ways to differentiate between recipients if the attacker has access to a large number of messages.

  A practical aside -- secondary clues may be in various logs. For instance, an attacker who obtains such a message might also be able to access (say) a .bash_history file with the recipient's address, or a web-server log with IP addresses that provide clues to who POST'ed or GETs the file, etc.


Can Shor's algorithm compromise RSA when both the public and private key are secret?

Actually, if RSA is being used in a deterministic way (and the public exponent $e$ is relatively small), someone could recover the value $N$.

We know that $P^e = C \bmod N$; that's equivalent to $P^e - C = kN$ for some integer $k$; if $e$ is small, then Shor's algorithm might be able to factor $P^e - C$; allowing you to recover $N$.  Alternatively, if you have two plaintexts/ciphertexts from the same key, then all you need to do is $\gcd(P_1^e - C_1, P_2^e - C_2)$, which can be done on a conventional computer.

Now, for public key encryption, we never use determanistic encryption.  However, for generating signatures, we sometimes do; this might actually be applicable there.

I would also second Maarten's comment that if you really intend to keep the public key secret, then there are symmetric algorithms that are far more practical (not to mention Quantum-Resistant).


Use large key size for RC4 to avoid RC4 bias

Will such a large key size possibly solve any of the bias of the initial bits of the key stream produced by RC4?

There is a bias in the RC4 output at small multiples of the key size; hence a 16 byte key will have biases at offsets 16, 32, 48, etc (with the bias rapidly growing smaller as the offset grows).  This bias happens less often with larger key sizes.

Other than that specific bias, no, increasing the key size doesn't help.

  Is there any reason for keys larger than 256 bits

Actually, I'm not sure if there's any reason to use RC4 at all...


The paper on which the question is based describes Rebalanced RSA-CRT with $d_p=d_q\bmod(p-1)$ as stated in the question's step 2, but is wrong in doing so. Notice that when $s<n/2$, that condition implies $d_p=d_q$, and that goes squarely against generate two $s$-bits random numbers $d_p$ and $d_q$ also in step 2 (further step 3 can become $d=d_p$, ans $d$ is $s$-bit only).

That's confirmed by looking at the paper's source: M. J. Wiener's Cryptanalysis of RSA with short secret exponents (IEEE ToIT, 1990), which section 8 open problems states [emphasis added]:

  A useful technique for reducing the secret key exponentiation time is
  to take advantage of the knowledge of $p$ and $q$ (rather than just the product $pq$). Using this technique, two half-sized exponentiations are performed. The first exponentiation gives the result modulo $p$ using exponent $d_p=d\bmod(p-1)$, and the second gives the result modulo $q$ using exponent $d_q=d\bmod(q-1)$. These two results can be combined easily using the Chinese Remainder Theorem to obtain the final result modulo $pq$. One could reduce the secret key exponentiation time further by choosing $d$ so that $d_p$ and $d_q$ are short. An interesting open problem is whether there is an attack on RSA when $d_p$ and $d_q$ are short, but not equal.

Wiener clearly knew that short $d_p=d_q$ would be unsafe (his paper conclusively proves it when $s\le 0.125n$).

I thus suggest that the key generation procedure for Rebalanced RSA-CRT should be:

Generate two random $n/2$-bit primes $p$ and $q$ (that are nearly certainly distinct for sensible choice of $n$), optionally such that $\gcd(p-1,q-1)=2$ ;
calculate $N=p\cdot q$ (which will be $n$-bit or one bit less).
Generate two $s$-bits random integers $d_p$ and $d_q$ (that are nearly certainly distinct for sensible choice of $s$), such that $\gcd(d_p, p-1)=1$ and $\gcd(d_q, q-1)=1$.
Calculate (using the CRT) one $e$ (possibly: the lowest) such that $e\equiv d_p^{-1}\pmod{p-1}$, $e\equiv d_q^{-1}\pmod{q-1}$, and $0<e<(p-1)(q-1)$.
[or we could explicitly compute $d$ then deduce $e$ as in the question]
Public key = $(N,e)$,
Private key = $(p,q,d_p,d_q)$.

but I caution against using it:

We know that it would be insecure to use $s<0.146n$, thanks to D. Boneh and G. Durfee's Cryptanalysis of RSA with private key $d$ less than $N^{0.292}$ (first version in proceedings of Eurocrypt 1999)
These authors caution the bound could further be improved to $d<N^{0.5}$, thus $s<0.25n$; so we should probably stick to prudently larger $s$, and a conservative Rebalanced RSA-CRT is thus bound to a speed improvement smaller than a factor of two.
Further, when using RSA-CRT (rebalanced or not) to compute $x\to x^d\bmod N=y$ , it is customary and useful to check that $y^e\bmod N=x$ in order to guard against fault injection; in which case having a large $e$ (as in Rebalanced RSA-CRT) much more than offsets any speed gain achievable by lowering $d_p$ and $d_q$.

Example with $n=40$, $s=13$ (which are too small to be sensible choices)

$p=768941$, $q=825443$, $N=634716965863$
$d_p=4231$, $d_q=6779$
$d_p^{-1}\bmod(p-1)=634271$, $d_q^{-1}\bmod(q-1)=670801$
$e=303057573891$.


Why are co-factors 4 and 8 so popular when co-factor is more than one?

Having a cofactor $h > 1$ does not inherently provide an advantage; in addition, it has these small disadvantages:

It reduces the expected effort of an attacker to solve the ECDLog problem by a factor of $\sqrt{h}$ (over a curve with approximately same size group order, and $h=1$)
We then have to worry about "what if the adversary passes us a point that's not in the prime-order subgroup" (and how much of a concern that is depends on where we're using the curve).

Both of these are actually fairly minor; however if we're using the standard Weierstrass curve addition routines, there's no reason to put up with them at all - he can just as easily pick a curve that has $h=1$, and avoid these minor issues.

So, why do we use curves with $h>1$?  Well, that's mostly because we want to use curves from more limited curve families (such as Montgomery and Edwards) and use that point addition logic associated with those equations - both Edwards curves and Montgomery curves always have $h$ a multiple of 4 (as they always has a point of order 4); the advantages of the Edwards  and Montgomery point addition logic is seen to be a good trade-off (compared to the rather minor disadvantages of having $h>1$).

  Have we studied ECC for curves which produce cofactor = 3 for example?

Do you know of a family of elliptic curves that always include a point of order 3?  Do those curves have some advantage over other elliptic curves?


In step 2 for Alice, what is the purpose of including Bob's public key in the hash? you can include a timestamp to prevent replay attacks instead.

In step 2 for Bob, there is a typo - should use Alice's public key instead of her private key.

Actually your protocol is similar to PGP, and I dont think it provides deniability because if Bob can prove that the public key belongs to Alice then the owner of the private key is most likely Alice.


It is safe, in the case that you have MACs which are independently keyed (or at the very least, the cryptographically secure MAC is independently keyed from all the other ones).  This can be seen not by an argument from randomness, but from a simple observation that it were not true, then an attacker could attack the secure MAC by generating the insecure MACs on his own, exclusive-or those MACs into the MAC he did observe, and then attack the combined MAC; any weakness there could be translated into a weakness in the original secure MAC.

If you have MACs which are not independently keyed, or you have hashes, you can construct cases where the XOR is not secure.  Here is one such example:

Our secure hash is SHA256 (which for the purposes of this example we will assume is secure).
We have 256 insecure hashes, $X_0$ through $X_{255}$.  $X_i$ is defined this way; all bits of $X_i(M)$ are 0, except for bit $i$; bit $i$ will be the same as bit $i$ of $SHA256(M)$.

We can see that every $X_i$ is extremely insecure (as each "hash" has only two possible values).

And, we can trivially see that the exclusive or $SHA256(M) \oplus X_0(M) \oplus X_1(M) \oplus ... \oplus X_{255}(M)$ is also insecure (because it is always zero).


What is the difference between, and security of $Z_p$ and $F_p$?

You should read the Wikipedia article on finite fields. For each prime $p$ and for each $n >0$, there is a unique field of order $p^n$ (up to isomorphism). This field is usually denoted $F_{p^n}$.
Now, for $n = 1$, the field $F_p$ can be identified with the set $\mathbf{Z}/p\mathbf{Z}$ of  integers modulo $p$, which is also sometimes denoted $\mathbf{Z}_p$. However, the notation $\mathbf{Z}_p$ is also used in number theory to denote the ring of $p$-adic integers and this may create a potential confusion.

The multiplicative group of every finite field is cyclic, that is, is generated by a single element. This multiplicative group is often used in cryptography.


A modified question of Hazay & Lindell's Efficient Secure Two-Party protocols Book

Promoting my comment to an answer: Encryption hides information from someone who doesn't know the decryption key. In your case, $P_2$ knows the decryption key, and can therefore learn $x$. This is really no different than sending $x$ in the clear to $P_2$.

Note that this is the strange example from the book that is secure in the malicious setting but not in the semi-honest setting. Adding the encryption step doesn't change that. Your modified protocol leaks $x$ to a semi-honest $P_2$ even when its input is $y=0$, so the protocol is not semi-honest secure. But your modified protocol is secure against malicious $P_2$ since malicious $P_2$ always learns $x$ in the ideal world without loss of generality.


Would the Fiat Shamir identification scheme be more secure if I design it with an exponents higher than 2?

No, it wouldn't.

Very simply put: If you can compute square roots wrt. a composite modulus, then you can calculate other fixed roots, too. This is based on the fact, that being able to compute square roots allows you to factor the modulus:

Choose random $x$.
Compute $x^2$.
apply your square root algorithm to $x^2$.
The result $y$ will be a different square root than $x$ with probability 3 out of 4. And 2 out of 4 will allow you to directly factor the modulus.

When  you know the factorization, calculating any arbitrary root higher than 2 is easy.

The other way around is not known: When you can calculate roots for any degree with injective functions, then you can break the RSA assumption. But it is unknown, if that allows you to factorize the modulus or allow the computation of square roots.


Could RSA keypairs be used for cryptocurrency addresses?

You could do this, but you'd have to replace 32-byte public keys by 256-byte public keys and 64-byte signatures by >=256-byte signatures in the storage format, assuming you used 2048-bit RSA moduli.  There are techniques for compressing RSA signatures, but I've never heard of anyone implementing them, so you might be on your own to write the code, and they won't beat 32-byte keys and 64-byte signatures at a remotely comparable security level.  And, unlike ECDSA, RSA key generation is sloooooooooooooooooow.

Alternatively, you could use a Schnorr-style signature scheme, such as Ed25519, with size and computational cost comparable to the ECDSA over secp256k1 as used by Bitcoin, and then reuse the key pairs for ECDH/ECIES, like XEdDSA does.  There is no shortage of ways to shoot yourself in the foot designing and implementing a bespoke cryptosystem, but the combination of EC-Schnorr and ECDH with the same key pairs does not necessarily seem to hurt security in itself.

(Whether you can do this with ECDSA, I leave this as an exercise for the reader to study.  I'm not aware of literature on it; if you find any, please answer fgrieu's question on the subject!  But your time is probably better spent just using XEd25519 than fussing with ECDSA.)


Does SRP reduce to DH key exchange when shared password is not secret?

The SRP paper has this point in its list of security properties:

    6. If the user's password itself is compromised, it should not allow the intruder to determine the session key K for past sessions and decrypt them. Even present sessions should at least be protected from passive eavesdropping.

The following section is titled Reduction to Diffie-Hellman and shows that, given an algorithm which retrieves the session key from the transmitted values and the password, you can also solve the computational Diffie-Hellman problem.

So yes, SRP is as secure as Diffie-Hellman for key exchange if the password is known to the attacker (and the other parameters are chosen properly, i.e. uniform random in their respective domains).

On the other hand, SRP with a non-secret password has the same problem as the pure Diffie-Hellman key exchange, when facing an active attack, i.e. a man-in-the-middle or an attacker who impersonates only one of the two parties.

  I would like to do key exchange under the assumption that I've already
  done mutual authentication (through some out of band user intervention).

Sorry, this rings alarm bells. Depending on how this out of band user intervention looks like, it could prove nothing at all about your actual communication going on, or about the non-existence of a man-in-the-middle attack.

Your "out of band authentication" should at least verify some value derived from the negotiated secret $K$, or (if you want it to go on beforehand) negotiate some (real) secret which then goes into the process as a part of the "password", so the attacker actually doesn't know the password, and can't mount a man-in-the-middle attack.

Also, as mentioned by CodesInChaos in a comment, SRP (as DH) does a lot of exponentiating of values by secret exponents. This is prone to timing and power analysis attacks if done naively, so your "default" JavaScript BigInteger implementation will have problems here.

If you want to run this in a Web browser (what JavaScript leads to believe), also take note that this will not more secure than the connection by which the browser got the code (hopefully at least an HTTPS connection), and good random numbers are a critical problem there. Also, side channel attacks are even easier if run on an untrusted platform like a web browser. More details in the article Javascript Cryptography Considered Harmful.


Bouncy jdk 1.51 Serpent KAT tests vs Nessie vectors

Bouncy Castle seems to be using a reversed byte order for inputs and outputs when compared to NESSIE test vectors.

In order to replicate the NESSIE vector in Bouncy Castle, the order of all inputs and outputs needs to be flipped at the byte level, therefore the following results are given from a NESSIE compliant implementation (Set 1, Vector 120):

key =    00000000000000000000000000000080
plain =  00000000000000000000000000000000
cipher = DDD26B98A5FFD82C05345A9DADBFAF49

Note the first key byte is now in the final position, and the ciphertext when reversed matches BC vector 10. Additionally if we perform a Monte Carlo test, the results should be similar:

Serpent Encryption, ECB Mode, 128-bit key

COUNT =      0
KEY =        d692af3ea36f5ef30de8c5eb79a8fb31
PLAINTEXT =  14f63ff537a39296008945f7125ea070
CIPHERTEXT = 2d74412f3d89016083c93b4d0fa553fc

These results match vector 14 in reverse byte order, using a 100 block loop test, the BC test does not seem to perform an outer key loop like other Monte Carlo test implementations, such as NIST CAVP. The CAVP MCT performs 100 outer key loops with 1000 inner block loops for testing AES implementations. If continued, next iteration in the key loop would be as follows:

COUNT =      1
KEY =        fbe6ee119ee65f938e21fea6760da8cd
PLAINTEXT =  2d74412f3d89016083c93b4d0fa553fc
CIPHERTEXT = 4597017beb21a4c6c75acb85ac4645f7


Why cant Public Key Encryption be perfectly secure?

The threshold for a perfectly secure system is that a computationally unbounded adversary cannot conclude anything about the plaintext from the ciphertext. With a public-key system, the attacker can try to encrypt messages with the real public key; this is not possible with one-time pads. What the attacker can do, quite simply, is to try all one-bit messages, then all two-bit messages, then all three-bit messages, etc., looking for a matching ciphertext.

Now, a public-key encryption algorithm may involve some randomness. The way to handle this is to try all possible outputs of the random number generator. You can make an algorithm $\textsf{Check(c,k,m,r)}$, where $c$ is the known ciphertext, $k$ the known public key, $m$ the guessed message, and $r$ is a string of bits. This runs the public-key algorithm with key $k$ on message $m$. Where the algorithm needs a random bit, it takes the first unused bit of $r$ (so it starts with the first bit, then the second, etc.), so the algorithm becomes deterministic. If all the bits of $r$ have been used and it needs another random bit, or if the encryption completes and the generated ciphertext does not match $c$, it returns False; if the encryption completes and the ciphertext matches $c$, it returns True. You can then run $\textsf{Check}$ with 1-bit $m$ and 1-bit $r$, then 1-bit $m$ and 2-bit $r$, then 2-bit $m$ and 1-bit $r$, then 3 and 1, then 2 and 2, then 1 and 3, etc. (i.e. the sum of the lengths of $m$ and $r$ is two, then three, then four, etc.) This will terminate with $\textsf{Check}$ returning True; when it does, you know what $m$ is.


Is it possible to pick your Ed25519 public key?

If you can store the private key with some pre-computed work, then you can pick almost any public key you want. So in a way, it depends on the implementation.

Here's a diagram of how Ed25519 works, note how keys are generated:

(Image source.)

A more detailed description (that is simpler than the actual paper) of the process is in these slides (slides 9 - 11).

To recap the image and slides: The secret is hashed and public key is derived from the "left half" of the hash. The left half is manipulated to be value $a$, which is a bit string with a few conditions. Then $a$ is applied to a curve point $B$ to produce the public key $A$.

The critical thing to note is that the seed's hash output is used in key generation. Apparently implementations differ on what they store as the private key, but the algorithm itself does not need the original secret, only the hash from it. This means that if you control the implementation you use, you can just make up any hash that suits your purposes and you don't need to care what the corresponding secret would be. (This prevents the need to finding any sort of SHA-512 pre-image.) We can use this by working backwards from the desired public key value and deciding what hash value we want.

The goal of this attack is to choose the value of $A$, or to at least choose something very similar to it. Call the new target public key we're trying to build $A'$, then if $A'$ is a valid public key there is an $a'$ such that $a'B = A'$. This reduces to finding the inverse on the elliptic curve, $a' = AB^{-1}$, which is actually the Discrete Logarithm problem and certainly non-trivial to calculate. But if you could find a valid $a'$, you would have everything you need.

As an important side-note, not all values of $a$ are valid in the scheme. See the Ed25519 paper for all restrictions for $a$ (I believe they are all listed on pg 6). There aren't very many restrictions, I think the most restrictive one is that $a$ be divisible by 8 (ie, the low three bits are 0). Assuming you can can calculate the $a'$ from a chosen $A'$, you could just pick random $A'$s until you find one that produces a valid $a'$. This step would prevent you from explicitly choosing your public key, because you have no guarantee that the desired value for $A'$ is valid. You can probably find a valid $A'$ after only a few tries, so just flip a bit here and there in the desired $A'$ and you should be able to find one that works and has a small Hamming distance from the original desired $A'$, which is probably good enough to produce keys that look alike.

If you have $a'$ then you have the public key and you can create a corresponding private key. You can make up a random "right-side" of the SHA-512 hash value and incorporate the new $a'$ to construct the private key.

This all assumes you can control the implementation and solve the necessary discrete logarithm. Regarding the implementation, the NaCl project has a high-speed performance-oriented implementation of Ed25519, and as such it stores as much pre-computed data as possible in the private key. It would allow you to perform this sort of manual crafting of the keys. But in general, with other implementations, you may have no such luck. I would think that for most attacks, the attacker should be assumed to be able to choose the implementation they use.

(Hopefully this is all correct, I hadn't looked at Ed25519 before this.)


No usually the shorter message doesn't get padded, you can just not decrypt or at least analyse the last part of the longer message. If the key is not even the same size as the message then you are dealing with a variation of the Vigenere cipher, not with a one-time-pad.

What happens in practice is of course dependent on the situation. But if the key is reused of an OTP then the security is lost, and usually in a rather catastrophic way.


Suppose $A$ knows $a$ and $B$ knows $b$, is it possible to efficiently compute $g^{ab}$ without leaking $g^a$ and $g^b$ to each other?

It's not possible because if $B$ knows $b$ and $g^{ab}$, then she can compute $\left(g^{ab}\right)^{b^{-1} \bmod N} = g^a$ (where $N$ is the order of $g$, which is normally prime so that $b^{-1} \bmod N$ exists).

EDIT: As noted by poncho in the comments, this assumes we are in a typical discrete logarithm setting, where the order of the group is prime to avoid attacks on the discrete logarithm by Pohlig-Hellman. In other settings such as RSA it may not be feasible to compute $N$ in the first place, but on the other hand having a group of non-prime order makes the discrete logarithm easier to attack...


proof of correctness Ring-LWE cryptosystem

I think your proof of correctness may be hampered by the fact that you are setting the ciphertext to $(c_0, c_1) = (a, as + 2e + m)$ when in fact the paper you cite sets the ciphertext to $(c_0, c_1) = (as + 2e + m, -a)$. You correctly state that decryption is then computed as $c_0 + c_1s \text{ (mod } 2)$. This reduces to $(as + 2e + m) + (-a)s \text{ (mod } 2)$, and you can then eliminate some terms ($as$ and $-as$) to get $2e + m \text{ (mod } 2)$. We note that $2e \equiv 0 \text{ (mod } 2)$ hence we are left with $m \text{ (mod } 2)$ and since $m \in R_2$ we have $m \text{ (mod } 2) = m$.


ECIES: key derivation function and symmetric encryption scheme

What you are describing is a stream cipher created from a generic PRNG. However, an actual stream cipher should be used instead. PRNG's are dangerous in the sense that they are sometimes pre-seeded or re-seeded by the system. If there is no mandated algorithm then the underlying implementation may change as well. Otherwise: yes, a stream cipher can of course be used to obtain confidentiality of the messages if used correctly.

AES in CTR (counter) mode is a pretty safe bet.

You seem to be using encrypt-then-sign. Usually sign-then-encrypt is used. The issue with encrypt-then-sign is that somebody can re-sign the ciphertext and claim ownership of it. The other aspect is that after decryption the signature is lost.

Therefore, usually sign-then-encrypt is used for asymmetric primitives such as ECIES and ECDSA. This may not be a problem in your specific protocol however; you could just want to allow only signatures from one specific private / public key and you could be fine with protecting the ciphertext in transit.

Once you have established a key and authenticated the exchange then you could also use AES-GCM or another authenticated cipher to send messages providing integrity, authenticity and of course confidentiality of the messages.

Note that there is a lot to do if you want to create a transport protocol. In place encryption is a bit easier wrt to possible attack vectors. If the system is secure in the end depends if the possible threats to the system are thwarted.

We can therefore not tell you if your approach is safe; we can tell if it is unsafe though :)


How can a user-input password be used to generate a natural-like dictionary corpus?

If I had such problem, I would operate as follows:

Obtain a list of 8192 different words. Then the $x$-th word of this list is denoted by L[x] (where $x$ is a natural number in decimal).
Given any bitstring (hash of the password), split it into 13-bit parts. Denote an $i$-th part by N_i.
The sequence of words is L[N_1] L[N_2] L[N_3] ....

For example, SHA3-512 online web app shows that SHA-3-512("MyPassword") starts with the following bytes:

35 c6 36 f4 40 b7 d7 40 7a ...

Converting this hash to a binary form (byte after byte) and splitting into 13-bit parts yields the sequence

0011010111000 1100011011011 1101000100000 ...

Converting each part from binary to decimal yields

L[1720] L[6363] L[6688] ...

If the list is taken from Wiktionary:Frequency_lists/PG/2006/04/1-10000, the resulting sequence of English words would be

admit billion lists ...

if we assume that 13 zero bits correspond to the last word of the list. If we assume that 13 zero bits correspond to the first word of the list and 13 set bits correspond to the last word of the list, then the resulting sequence of English words would be

supply shorter gallop ...


Present cipher is bit based permutation cipher. The branch number is calculated based on the minimum number of hamming weight sum of input and output  in the difference distribution table(DDT) or linearity approximation table (LAT) of the sbox. in case of present cipher the 4-bit sbox , the differential branch number (BR) is 3.

to apply the differential BR on the whole present cipher , I advice you to apply mixed integer linear programming. this link contains the MILP model of different ciphers including present in sage, you can start from here.


AES sbox security issue - power analysis attack?

I was wondering about whether the usage of a precomputed sbox (kind of a lookup table) could be a serious security issue when using AES.

Well, that rather depends on the type of side channel attacks you are interested in protected against.

You specifically mention Power Analysis (SPA and DPA) type attacks; the first obvious question would be: could those attacks actually be performed by the type of adversary you are trying to protect?  After all, to perform those attacks, the attacker needs to make extremely precise (and extremely high resolution) measurements of the current drawn by the circuit; is this a realistic scenario?

Sometimes it isn't.  If we're talking about crypto that'll be used in a Web server in a physically secure location, there's no way an attacker could get physical access (and if he could, there are far more damaging attacks an attacker could do).  On the other hand, if we're talking about crypto on a Smart Card (where the power is externally supplied, potentially by the attacker), then power analysis attacks are quite realistic.

And, if we really do need to protect against such invasive attacks, we need to worry about a lot more than just how the sbox is computed.  If you're running on a general CPU, then what an attacker with that level of access might be able to do is directly monitor the memory bus (and just read the keys are they are being read from memory); to prevent that level of attack, we generally need the entire crypto circuit be in a special enclave that the attacker can't break in (for example, epoxy-encapsulated).

And, power analysis attacks can allow the attacker to deduce the settings of various gates; in the standard AES implementation, the first thing you do is xor the plaintext with 128 bits of the key; if the attacker can read those first 128 bits, he gets 128 bits of the key (and with AES-128, that's all of it).  Because of this, when we do a DPA-resistant implementation, we implement a blinded or threshold implementation (where we stir in some randomness at the start of the operation; this randomness doesn't affect the final result, however it does affect how the intermediate values are represented, where each logical bit is spread over several physical bits (so that the setting of any internal bit, or any set of k bits, are uncorrelated to the logical operation being performed).  Now, this doesn't actually stop all DPA attacks; we hope it makes it sufficiently difficult that the attacker won't be able to collect enough data samples (e.g. encryptions based on the same key) to actually deduce anything.

Now, table lookups don't work well in this blinded/threshold scenario, and so (to answer the question you originally asked) we tend to compute things on the fly.


Encryption that does not allow the encrypting party to decrypt

Yes, you're misunderstanding how public key encryption (such as RSA) works.  Indeed, the entire point of public-key encryption schemes is that the public key can be used to encrypt data, but not to decrypt it; for decryption, the private key is required.

However, there's a catch that you should be aware of: the public-key encryption schemes we currently know of are generally not suitable for directly encrypting large amounts of data, because:

they're really slow, especially when compared to symmetric encryption schemes like AES; and
they tend to produce ciphertext that is larger than the encrypted plaintext, often significantly so.

The usual solution to these problems is to use hybrid encryption.  Basically, what programs like PGP / GnuPG do to "encrypt a file with RSA" is that they generate a random "message key" for a fast symmetric cipher like AES, encrypt the file with that AES key, then encrypt the AES key (which is short, only 16 to 32 bytes) with RSA, and finally join the two ciphertexts together (along with various kinds of metadata) as the encrypted output file.

As long as the intermediate AES key used to encrypt the data is safely discarded, the only way to decrypt the encrypted file is to first extract the encrypted AES key from the encrypted file, decrypt it with the RSA private key, and then decrypt the actual data with the decrypted AES key.  But in principle, a malicious encryptor could save a copy of the AES key (or simply generate it according to some deterministic pseudorandom algorithm that they can later repeat), and thereby retain "back door" access to the encrypted files.

Of course, in principle a malicious encryptor could also simply save a copy of the unencrypted data before encrypting it, so in that sense, the problem is unavoidable.  However, a bunch of 32-byte AES keys is a lot easier to conceal than several mega/giga/terabytes of audio recordings (and an "accidental bug" in the AES key generation code that makes it at least partially repeatable could be even easier to hide, and to explain away if found).

In practice, giving your telephony provider an RSA public key and your lawyer the corresponding private key (or, better yet, asking your lawyer to generate an RSA keypair and to send you and your provider the public key), and having the provider encrypt the audio files with that key using standard off-the-shelf software like PGP / GnuPG is probably good enough.

While it would be theoretically possible for the provider to modify the software to insert a backdoor into it, that would take some non-trivial effort and programming / crypto knowledge, and would risk being caught in an audit (since any such modified software would stand out if compared to the standard version of the same program).  And in any case, they'd have to do that before encrypting the files they want to be able to decrypt; as long as they're initially honest, they won't be able to later decrypt any honestly encrypted files even if they later turn malicious (and/or are compromised by someone else).


How to get the order of a group generator in DH?

To extend kelalaka's answer, if $p$ is a safe prime (that is, if $p = 2q+1$ with $q$ prime), then:

If $p \equiv 7 \pmod 8$, then the order of $g=2$ will be $q$

If $p \equiv 3 \pmod 8$, then the order of $g=2$ will be $2q$

If $p = 5$ (the only other possibility), then the order of $g=2$ is 4 (that is, $2q$)


How to exctract ECDH parameters from an OpenSSL-generated $G$?


Decrypting RSA encrypted messages with repeated use of p,q

The assignment, or at least the part of it that you've quoted, seems somewhat ambiguous, but I'm going to assume that it means that among the RSA moduli there are pairs $(n_A, n_B)$ that share a common prime factor $p$ (i.e. $n_A = p \cdot q_A$, $n_B = p \cdot q_B$, with $q_A \ne q_B$).

In that case, you can trivially find the shared prime factor by calculating the greatest common divisor of the two moduli $n_A$ and $n_B$, e.g. using the Euclidean algorithm.  Even if you don't know in advance which moduli share a common factor, you can simply test each pair of moduli: the GCD of any two numbers is always, by definition, a divisor of both of them, so if you find any two RSA moduli whose GCD isn't 1, you've just factored both of them.

Note that this is not just an artificial exercise, but a practical attack against poor quality RSA key generation implementations found in the wild.  For a demonstration of this attack (and more details on how to efficiently carry it out in practice), see e.g. the paper "Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices" by Heninger, Durumeric, Wustrow and Halderman (2012).

Ps. See also this related question from a few years ago.


Shamir Scheme: Whats the problem of not using random x-coordinates?

i would like to know why there is a problem of not using random x-coordinates in shamir secret sharing schemes.

There is no such problem.

The only requirements on the $x$-coordinates are:

They're all in the range $(1, p-1)$ (or $p^k - 1$ if you're using the extension field $GF(p^k)$; you can't use 0 as a coordinate (as $f(0)$ is the secret), and you can't you values outside the range.
They're distinct (if they're not, then the two shares with the same $x$ coordinate are the same share).

ANy arbitrary set of $x$-coordinates that meet these two requirements work just fine.

  So, why i always find in some literature that it is a problem using not random x coordinates?

I suspect that you are misinterpreting the literature.  For the coefficients of the secret polynomial $f(x)$, it is necessary that the non-constant terms be random; if they are not, then it is possible for a small group to recover the secret.

There is no corresponding requirement on the $x$; they can be any values you find convenient (as long as they meet the above two requirement)


Is it safe to operate over the prime sub-group of Curve25519?

Theoretically, yes you can do that. The idea you have is correct: we can simply choose an integer $k\in[1,p_1-1]$ to determine our public key $Q=[k]P$. The effective hardness in solving the discrete logarithm comes from the large prime order subgroup, so in that case we lose nothing.

However, it is not true that small sub-group attacks are not possible. We are still working over a curve $E$ which contains points of small order, let's say $P_2$ is a point of order 2. Now I engage in a Diffie-Hellman key exchange by sending over my (malicious) "public key" $P_2$. In turn I receive back $[k]P_2$, given that your secret key is $k$. Then
$$k\equiv0\bmod{2}\iff [k]P_2=\mathcal{O}.$$
Hence I have learnt $k\bmod{2}$.

How should we prevent this? In the obvious way: before computing $[k]P_2$, we first check $8P_2\neq\mathcal{O}$. As poncho notes, this prevents only this specific attack. The more generalized attack, where we send $P_s=[k']P+Q_s$, for $Q_s$ a point of small order, still works and can instead be prevented by checking that $[p_1]P_s=\mathcal{O}$. As mentioned, this is quite expensive.

What we can do instead, is only allow our scalars to be $0\bmod{8}$ (i.e. the three lsb's all zero), so that there is nothing to be learnt in the first place. Therefore we have an inherent resistance against small sub-group attacks, which is not true if $k$ were prime. This is exactly what happens for Curve25519.


Is Elliptic Curve Diffie-Hellman (ECDH) still secure if I use the public key more than one time?

Is the algorithm still secure if public key Pb is used more than once? Or are there any requirements to use use a public key more than once in a secure way?

I'll amend the question to what I think you mean ("is ECDH secure if we reuse our private value across multiple exchanges"), and answer it, "yes, it can be done securely, but (under some scenarios) you MUST perform validity checking on the value you receive from the peer".

The biggest thing you need to check is "is the value you receive a point on the curve?".  After all, you take the values $x_b, y_b$ that you received, and plug them into the EC point multiplication routine, and perform a series of point additions/doublings.  These routines generally assume the point they're given is already on the curve; if not, they'll assume a curve that the point is on.  That is, you are performing the operations on a curve which may be $y^2 = x^3 + ax + c'$, for a $c'$ that the attacker selected.  The attacker can select such a curve to have an order with a small factor $r$, give you a point of order $r$, and so the shared secret would be one of $r$ values (and which one would indicate the value $N_a \bmod r$.  By doing this several times with different curves (and different values of $r$), he can deduce the value $N_a$.

Now, one variant of ECDH is for both sides exchange only the $x$ values (and have the shared secret depend only on $x$); this largely avoids this problem (but not entirely, unless you have a curve with "twist security"), and is done by (for example) Curve25519 .  However, it is not universal; sometimes you are implementing an existing protocol that insists on exchanging $x, y$ values.

If you must exchange both $x$ and $y$ values, the fix is actually pretty easy: just plug the values you receive into the curve equation and see if it satifies it; that is, if $y_b^2 = x_b^3 + ax_b + c$; if not, abort the key exchange.

There is also a second (far less serious) issue; suppose that you receive a public value that's a valid point on the curve (and so passes the above check), is not the point at infinity (you do check for that, don't you?), but isn't in the prime order subgroup that $G$ is in.  We normally do ECDH in a curve of order $hq$, where $h$ is a small integer, and $q$ is a large prime (and is the order of $G$).  By giving us a point that's in the larger curve, the attacker can potentially learn $N_a \bmod h$.  This isn't nearly as serious (as the attacker can't try different values of $h$), however it is still a leakage.

Things we can do about this:

Use a prime order curve; that is, one where $h=1$.  In that case, the attacker learns nothing (as any point on the curve he gives us is also within the subgroup)
Do "cofactor DH" instead; this modifies the secret derivation to $k = (hN_a)P_b = (hN_b)P_a$; by including $h$ in the final computation, this attack would give the attacker the value $hN_a \bmod h$, but that's always 0, independent of what $N_a$ is.  Of course, this may not be an option if you're implementing an existing protocol.
Verify that $qN_b = 0$ (that point at infinity); this works, but this is a fairly expensive computation; no cheaper than selecting a fresh ECDH private value each time.
Just live with it; even if $h>1$, it is typically a small value, such as 4 or 8; giving the attacker a few bits of the private value doesn't help him that much


Basically $M = 9$ is a challenge. Alice will have to sign it (compute $M^d \pmod {21})$, because only she knows $d$.
As $(M^e)^d = (M^d)^e = M \pmod{21}$, it should be clear what Bob should do to verify that the reply indeed equals $M^d$, which only Alice could have produced...


Is it secure to compute the exponentiation and the LWE operation?

For the second question, it depends on whether we can trust Bob to generate $a$ uniformly at random and without any “hidden structure.” If we can trust him, then this is secure assuming RLWE is hard; what Bob gets is merely one properly distributed RLWE sample.
However, if Bob may choose $a$ in a malicious or “sneaky” way, then there can be attacks. For example, Bob can choose $a$ as an NTRU public key, as $a=f \cdot g^{-1} \pmod{q}$ for “short” polynomials $f,g$ of a certain form that constitute the secret key. Then, giving Bob $s \cdot a + e$ for short $s,e$ is essentially just NTRU encryption, and Bob can use $f,g$ to recover $s,e$. Moreover, such an $a$ doesn’t even seem to “look suspicious,” since it’s commonly conjectured that NTRU keys constructed in this way are indistinguishable from uniformly random. So Alice can’t even hope to catch Bob being sneaky in this way.
If Bob doesn’t care about “acting suspiciously,” then there is an even simpler attack: Bob can choose $a=p$ for some small scalar integer $p$ that will be slightly bigger than the coefficients of $e$. Then, giving Bob $b =s \cdot a + e = ps + e$ makes it easy for Bob to recover $e$ (just reduce $b$ modulo $p$) and then $s$.


Understanding generation of IV in CBC encryption

The next plaintext block is 16 bytes, the current ciphertext is, say,
  120 bytes

No. With CBC you consider a block cipher which transforms a plaintext block (say of size 16  bytes) to a ciphertext block (of the exact same size). So a 120 bytes ciphertext block for a 16 byte block is nonsense.

This also follows from the formula of CBC, which is
$$C_0=IV,C_i=E_K(P_i\oplus C_{i-1})$$
As you can see, each ciphertext is an output of a block cipher and thus must have exactly the same size as the input.

  What is the advantage of XORing the next plaintext block with current
  ciphertext over XORing the next plaintext block with the current XORed
  plaintext block?

So this would be $P_0=IV,C_i=E_K(P_i\oplus P_{i-1})$. Indeed, this mode doesn't hide patterns, and as such this mode is not secure against a chosen plaintext attack as you can distinguish $m=(m_1\parallel m_2 \parallel m_3 \parallel m_4)$ from $m'=(m_1\parallel m_1 \parallel m_2 \parallel m_2)$ because the latter has the same ciphertext blocks at position 2 and 4 (because the plaintexts cancel each other out) whereas the former does not.

Also see "Plaintext block chaining, bad idea why?".


Encryption algorithm with shortest ciphertext for long strings

The general method for shortest ciphertext goes

Compress [but see cautionary note], perhaps using a general-purpose lossless compression such as (among many) Deflate or LZFSE; or some context-aware compression.
Encrypt, using authenticated encryption such as (among many) AES(-256)-GCM-SIV.
If the context requires, reformat to fit requirement, e.g. as Base64.

Decryption undoes each layer in reverse order. It is critical to use authenticated encryption or (much preferably, and) a robust de-compressor to avoid all kind of attacks, or crashes when deciphering an invalid ciphertext or decryption key.
For “a list of data URIs (that) are thousands of characters in length”, compression in step 1 will I guess reduce size by more than 1/4. It can outweigh the (small, constant) expansion in 2, and the ≈1/3 expansion of Base64 in step 3.
CAUTION: with compression, the size of ciphertext will reveal something about the size and compressibility of the plaintext, when normally encryption reveals only the size. This is known to be an issue in some contexts (including, digitized voice). Knowledge about the nature of the URI and what's confidential in them would be required to determine if that's an issue . If in doubt, don't compress.
Note: if size is paramount, and it is not an issue (or perhaps, if it is desired) that encryption of the same data with the same key always yields the same ciphertext, then it is safe to use a constant (e.g. all-zero and implicit) Initialization Vector in an authenticated encryption with the aforementioned AES-GCM-SIV.


In ISO/IEC 9796-2 (signature with message recovery), why are some message representatives bigger than the modulus?

ISO/IEC 9796-2 is a digital signature scheme giving message recovery. That is: able to embed some of the message in the signature, thus lowering communication or/and storage requirements. There are a lot of options:

Total recovery is when the message is fully embedded in the fixed-size signature; this limits the message size to a certain capacity. This opposes to Partial recovery were the message size exceeds the capacity: the recoverable part $M_1$ of the message (up to capacity) is embedded in the signature, and the (non-empty) non-recoverable part $M_2$ must somewhat be made available to the verifier independently from the signature (often: along).
There are 3 schemes:

#1 is the original, simplest, but is at least theoretically broken in a chosen-messages setup. It is used in in EMV, Passport, and Digital Tachograph.
#2 is inspired by RSASSA-PSS, and uses random salt and MGF1.
#3 is simply #2 with no salt.

The hash used for signature. A common choice for 1024-bit modulus would have been SHA-1, but both are obsolete. A modern choice is SHA-256.
If that hash is assumed known by the parties (Trailer field option 1) or encoded in the message representative trailer (rare: the motivation for ISO/IEC 9796-2 is compact signed messages, so the overhead of explicitly encoding the hash is unwelcome, plus that's not a good idea from security and simplicity standpoints).
For schemes #2 and #3: which hash is used for MFG1. Two popular choices are SHA-1, and the same hash as in as the signature.
Salt size for scheme #2. The more salt, the simpler/stronger the security argument, but the lesser the capacity.
Odd or even public verification exponent $v$, that is RSA or Rabin. $v=2$ provides the fastest standardized signature verification around.
Use of "Alternative" signature (RSASP1 and RSAVP1 in PKCS#1, basically big-endian textbook RSA with left-padding with zeroes up to a fixed size), or non-alternative which saves one bit in the signature (I have only seen that with even public exponent, and in test vectors).
Modulus size: many implementations restrict to modulus a multiple of 8 bits, or a larger power of two.
Message alignment: the standard supports any size, but many implementations restrict to bytes.

When using byte-aligned message, $k$-bit modulus (multiple of 8), $L_h$-bit hash (multiple of 8), salt size $L_s$ (multiple of 8, possibly 0), Trailer field option 1, the capacity is $k-L_h-L_s-16$ bits.

There are variations in usage:

How the data to be signed is split in recoverable and non-recoverable parts of the message: the standard defines that the recoverable part of the message is at the beginning, but sometime it is desirable that the start of the payload data is readable before signature verification (e.g. because it includes a key index), therefore the recoverable part of the message sometime is gathered from the end of the payload data.
Signature before or after the non-recoverable message in signed data.
Tolerating use of partial message recovery mode when the message size is exactly the capacity.
Perhaps, tolerating a recoverable message $M_1$ shorter than the capacity including with a non-empty non-recoverable message $M_2$.

  It turns out that, for some inputs, the resulting message representative is bigger than the modulus when converted to a number.

That's a clear indication that the message representative is not computed correctly.

  To generate the message representative ($F$ in the standard), I just call PKCS1_MGF1() and then XOR that to the data to be signed, excluding the hash and the trailer, as the standard says.

Based on that oversimplified description, the problem likely is that the output of MFG1 is considered to be bytes, when the standard wants it one bit less than a multiple of 8 (when everything is byte-aligned). You want to zero the first/left bit of what MFG1 produces before the XOR, or equivalently zero the high-order bit of the message representative after the XOR. That won't lose message data, since that bit is part (or on the left of) the header.

  I can use the "alternative signature production function"

Yes. That's by far the most common when public exponent is odd.


… SHA3 (Bouncycastle) constrains me …

Bouncycastle offers the NIST approved, fixed, and standardized output lengths of the keccak sponge function.

See, when talking about SHA-3, you're talking about those NIST standards. This was built upon the proposed and accepted keccak sponge function.

NIST standardized SHA-3 to those lengths (which libs like Bouncycastle cover) to match up with the SHA-2 output standard perfectly, so that SHA-3 can be used as an immediate drop-in replacement in case SHA-2 (let's just say) "goes down" one day.

Yet… just because NIST created/fixed those standard output lengths it doesn't mean that the underlying sponge function couldn't be used to create other output lengths.

In the end, the only thing you are missing is the fact that many programming libraries (including Bouncycastle) focus on providing functionality that adheres to standards, not custom functionality.

  … is there a specific way to generate "arbitrary length" using bouncy castle implementation …

Well yes, if you look at the BC lightweight API you’ll discover the option to use SHAKE128 and SHAKE256 – which does exactly that. (hint: SHAKEDigest class)

If you think the SHAKE128/256 functions don’t fit your needs (they actually should), that's where programming comes in. If you want something special (read: non-standard), you'll have to grab the core sponge functionality and create your own corresponding functionality you think you need. Libraries like Bouncycastle will hardly be of much use here.

But it's not as if there aren't projects and sourcecode pieces out there on the web that already offer what you are looking for. Simply use your favorite search engine to find them for whatever programming language you deem suitable and fitting your needs.

  … standardized version of Keccak is different from the original one that was submitted to NIST …

Yes, you are also correct related to SHA-3 and Keccak being different. They are both sponge functions… but SHA-3 was built upon Keccak, with a small tweak introduced by NIST. This small difference within the sponge functionalities of SHA-3 and Keccak makes them produce different outputs for the same output length.

Practically, both are considered cryptographically secure. So, when wanting arbitrary length of output, you'll have to decide what sponge function you want to use. Looking at Gimli, I'ld like to note that there are other sponge functions out there which are suitable for cryptographic purposes too. Depending on what exactly you need or expect, you have diverse choices.


M.O.Rabin answered the question in 1981, named it oblivious transfer.


CBC encryption + CBC MAC reusing key in MAC-then-Encrypt

Why is the comment needed that encrypted MAC part is constant?

With the scheme in the question, in a cryptogram with the correct MAC, the last block of the encrypted message is a constant. Importantly, that goes both ways: if the last block of the encrypted message is that constant, then the MAC is correct and whatever plaintext is deciphered will pass the MAC test.

This allows forgery: an adversary can observe one encrypted message, get that constant, and from then on forge encrypted messages that will pass the MAC check after decryption. That goes against the purpose of ensuring integrity of the (deciphered) message.

We combined a secure encryption, and a secure MAC (for constant message length), and got an insecure combination (w.r.t. the goal of the MAC) because we did not obey the principle: a key shall only serve one purpose (or: one usage, one key).

In the context, it gets worse than letting garbage pass the MAC check: CBC encryption is malleable enough that the adversaries can partially choose the deciphered plaintext. For example, with a long known plaintext, they can copy/paste large segments of ciphertext, cutting at block boundaries, and that does the same for deciphered plaintext, albeit with one block of garbage after each cut. Other example (that can combine): an adversary can put an arbitrary chosen value one block wide in the deciphered plaintext, by putting it in a ciphertext block followed by a copy of the last block $E_k(0)$.


Baek and Zheng’s Threshold Cryptosystem - limit on threshold?

The problem (thanks for the prompt Ido) was the use of PBC's element_mul_si instead of element_mul. This caused the polynomial calculation to loose precision(by rolling over I think) on larger values of t.

I now use element_mul during polynomial calculation in this commit and it works perfectly. Python Charm does not use element_mul_si hence the issue does not show up in the HoneyBadger implementation of TCG.


Breaking a modified version of Diffie Hellmann Protocol

Yes, there's an easy way to recover $g$:

$$g = y^{x^{-1} \bmod p-1} \bmod p$$

This works because the multiplicative group $\mathbb{Z}_p^*$ has order $p-1$, and hence $g = g^{x \cdot x^{-1}} = (g^x)^{x^{-1}} = y^{x^{-1}}$


How does using a really small block size reduce the key space?

How does a small block size reduce the key space?

Let $b$ be the block bit size of a block cipher. There are $2^b$ possible block values, for a plaintext, and for a ciphertext. For a fixed key, there is a single ciphertext corresponding to any given plaintext, and vice-versa. A key and the block cipher thus implement a bijection on the set of $n=2^b$ possible block values. Given a set of $n$ elements, there are $n!$ bijections on this set. Thus there are at most $(2^b)!$ possible plaintext-to-ciphertext correspondences/bijections for our block cipher.
No matter how large a key for our block cipher is, it is bound to generate one of these $(2^b)!$ correspondences/bijections. A $k$-bit key can take $v=2^k$ values, thus for $v$ values we need $k=\log_2(v)$ bits of key. Thus the effective key space is limited to $k=\log_2((2^b)!)$ bits.
$$\begin{array}{r|rr}
b&1&2&3&4&5&6&7&8&9&10\\
\hline
k&1&4.6&15.3&44.3&117.7&296.0&716.2&1684.0&3875.2&8769.0
\end{array}$$
For example, with $b=3$, there are $2^3=8$ possible block values, thus $8!=40320$ possible plaintext-to-ciphertext correspondences, corresponding to a key somewhere between $15$ and $16$ bits (giving $2^{15}=32768$ and $2^{16}=65536$ keys).
Thus for REALLY small block size (less than about 6 bits), the block size indeed limits the key space.

But the quote¹ in the question is about something else: the risk of reuse of a block value, without consideration about the keyspace. For a random distribution of block values, there's >39% chance that a value gets reused after $2^{b/2}$ blocks (see this). This is a concern for less small blocks.
For $b=64$ (as in TDES), $2^{b/2}$ blocks is a mere 32GiB of data. If we have two 32GiB files TDES-CBC-encrypted with the same key, and the first file is known, there is >63% chance we can decipher at least 8 bytes of the second file, because a block in the second file matches one in the first file.

¹ That quote does not say that we moved to larger blocks like 128-bit because smaller blocks dangerously reduce the key space, which would be wrong. It says small blocks harm security, much like small key space does, and that is correct (even if the justification given is rather vague).


Is AES in OFB mode with same IV more robust than ECB mode?

OFB with an IV re-use is a different kind of completely broken than ECB.

In ECB mode, the problem is the fact that you can recognize blocks. That is if the same block appears twice you will notice that and know the underlying message-blocks were the same.

In OFB mode, the problem is the re-use of the key-stream. That is for any two ciphertexts under the same IV/key pair, you can compute the XOR of the underlying messages. Note that if you know (parts of) either message this allows you to recover (parts of) the other message.

So with ECB mode it's hard to actually infer the precise contents of the message but you can detect patterns in the ciphertext, whereas OFB hides patterns in a single ciphertexts, but leaks a lot of information with two ciphertexts.


Public-key format for ECDSA as in FIPS 186-4?

As said in comment, I believe you might find answers in the SEC1v2 document, which is used in many implementations (OpenSSL, Go, mbedTLS etc.) as a reference regarding that matter and which spares you the pain of reading all the many RFCs on that topic.

Now regarding the actual facts, if I generate a private key with OpenSSL:

openssl ecparam -genkey -out testsk.pem -name prime256v1

And then print its public details:

openssl ec -in testsk.pem -pubout -text

I get the following:

read EC key
Private-Key: (256 bit)
priv:
    00:ca:4e:db:94:a6:e5:a4:5f:3b:9e:f6:34:cf:22:
    5e:10:eb:7f:60:8d:56:d6:2a:e9:1c:08:4e:ee:c0:
    38:21:bd
pub:
    04:f3:13:94:7a:db:02:6b:c1:1f:3a:50:c4:04:07:
    d1:12:12:6a:b2:90:e8:c8:48:7a:4b:3c:f6:8a:7e:
    3b:4e:fe:67:e7:69:bd:74:b6:32:3c:26:ea:66:43:
    81:e6:74:d2:aa:db:1c:a6:44:03:fc:7a:72:90:28:
    20:bf:1d:3d:89
ASN1 OID: prime256v1
NIST CURVE: P-256
writing EC key
-----BEGIN PUBLIC KEY-----
MFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAE8xOUetsCa8EfOlDEBAfREhJqspDo
yEh6Szz2in47Tv5n52m9dLYyPCbqZkOB5nTSqtscpkQD/HpykCggvx09iQ==
-----END PUBLIC KEY-----

Which, once decoded from ASN1 corresponds to:

SEQUENCE(2 elem)
    SEQUENCE(2 elem)
        OBJECT IDENTIFIER1.2.840.10045.2.1ecPublicKey(ANSI X9.62 public key type)
        OBJECT IDENTIFIER1.2.840.10045.3.1.7prime256v1(ANSI X9.62 named elliptic curve)
    BIT STRING(520 bit) 000001...1000

So my public key is actually a sequence of two tags:

firstly, another sequence, which is constituted of the details of my object, which is an ecPublicKey and is made for the curve prime256v1 (aka P-256) as per their "decoration" (aka OID).
secondly, the bit string corresponding to the EC public key point at hand, which is either compressed or not (this can be determined depending on its length, here as you can see we have $\frac{520}{8}=65= 2\cdot \frac{\log_2(q)}{8}+1 $, so no compression).

And as you pointed in comment, those points are encoded as explained in SEC1v2 section 2.3.3, and the exercise of converting the bit string into actual coordinates is explained in section 2.3.4


Making PRNG cryptographically secure thru shuffling?

I assume what you are asking is if I take a non-cryptographic random generation, is it enough to shuffle and then hash to get something cryptographically secure. In general, the answer is most certainly no. To start with, a non-cryptographic random call typically has very low entropy. I assume that random.shuffle() is also a non-cryptographic function, and so you are adding low-entropy randomness to low-entropy randomness; the result still has very low entropy and can be brute forced. At the end, you hash the result. I am assuming here you want to use a cryptographic hash function. In such a case, under reasonable modeling, if the input to the hash function has high enough entropy then you are fine; otherwise you are not. I assume here you are not.

In any case, as with all cryptography, it is very very very hard to get this right and you should not try to invent it yourself until you are an expert.


Other advantages of CTR are:

easier to decrypt from a certain offset within the ciphertext
no randomness requirements for the nonce

nonce can be calculated, e.g. be a simple counter
nonce can be a message identifier

$E = D$: encryption is the same as decryption, which means

only encryption or decryption required from the block cipher
less logic required

no padding overhead or mechanism required
key stream can be pre-calculated (latency advantages)

Draws:

sequential speed the same (about the same number of ciphertext blocks)
cryptographic security (when used properly)

Disadvantages:

nonce reuse is catastrophic, confidentiality is completely lost
leaks somewhat more information about the size of the plaintext
multiple, slightly different schemes with regards to IV creation and the method that the nonce is used
still less common in libraries or known by (starting) developers

Another questionable disadvantage is that CTR has no error propagation, but that should probably be considered an advantage by now; if you want integrity, use an authentication tag (MAC or signature).

You can attack CBC and CTR using different methods, with different consequences. If CBC mode has problems in a certain protocol, then switching to another mode has its advantages of course. See the answer of Thor for good reason to switch to CTR for OpenSSH specifically.

That's probably a better reason to disable CBC than the reasons given above. If you want to know for sure, you should ask the OpenSSH developers though (or the person that disabled CBC-mode, anyway).


Is this authentication system insecure or not

It is vulnerable to replay attacks since the attacker knows the plaintext and its corresponding ciphertext. To mitigate against this you might want to include some information in the message like a timestamp so that assuming time keeping isn't compromised for the server and client, outdated messages, i.e messages marked by a timestamp earlier than a certain timeframe can be invalidated.


ipsec, esp: Which key is used to generate the HMAC

Are the keys for the ICV calculation and the encryption the same in IPSEC/ESP? Or do there exist two keys in the SA?

No, the keys are not the same.  Yes, there do exist two keys in the SA (at least, for SAs that have separate encryption and integrity transforms - not all do).

You do derive both the encryption and the HMAC key at the same time, from the same secret, but they are not the same (that'd be bad key hygene).  Instead they are derived from the same secret (and also you generate the keys for the SA protecting traffic flowing in the opposite direction at the same time).

That is, IKE generates a long random-looking string (which it refers to as KEYMAT); if the encryption key is n bits and the integrity (ICV) key is m bits (and AH is not being used), then at least 2n+2m bits of KEYMAT are generated, and then:

The first n bits is used as the initiator-to-responder encryption key (that is, used to protect traffic flowing from the initiator to the responder)
The next m bits is used as the initiator-to-responder integrity key
The next n bits is used as the responder-to-initiator encryption key
The next m bits is used as the responder-to-initiator integrity key

To see the text of the standard, see section 2.17 of RFC7296:

  In any case, keying material
     for each Child SA MUST be taken from the expanded KEYMAT using the
     following rules:

  All keys for SAs carrying data from the initiator to the responder
        are taken before SAs going from the responder to the initiator.

  If multiple IPsec protocols are negotiated, keying material for
        each Child SA is taken in the order in which the protocol headers
        will appear in the encapsulated packet.

  If an IPsec protocol requires multiple keys, the order in which
       they are taken from the SA's keying material needs to be described
       in the protocol's specification.  For ESP and AH, [IPSECARCH]
       defines the order, namely: the encryption key (if any) MUST be
       taken from the first bits and the integrity key (if any) MUST be
       taken from the remaining bits.

The HMAC key is the 'integrity key'


The answer is correct, you don't need to unpad the message.
When/if you verify the signature, simply check that $(\text{signature})^e == \text{pad}(\text{message})$

Regarding the padding scheme, you can just use a full domain hash.

Here's how you implement a full domain hash:
$$ \mathrm{cycles} = \frac{\text{(RSA key length)}}{\text{(SHA digest length)} \times 8} + 1$$
(e.g., RSA key length = 1024bits and SHA digest length = 20bytes)
$$ \mathrm{FDH}(M) = \mathrm{SHA1}(M || 0) \mathbin\Vert \mathrm{SHA1}(M || 1) \mathbin\Vert \ldots \mathbin\Vert \mathrm{SHA1}(M || \mathrm{cycles}-1)$$

where $||$ denotes concatenation


Is it safe to use cipher block sizing instead of padding?

Yes, this is fine.

There is a practical disadvantage in space used, if you don't otherwise need to store the size in plaintext. A size field will usually take 32 or 64 bits, whereas typical padding adds one byte on average. Also, if you use encrypt-then-MAC you need to include the length as part of the authenticated data.


Elliptic curve scalar point multiplication

For adding, subtracting, and multiplying modulo 29, you can just do the operation in the integers and take it modulo 29 (as you're already doing). To find $a/b$, however, you need to use the extended Euclidean algorithm to find the inverse of $b$ modulo 29, then compute $a \cdot b^{-1}$. This StackOverflow post has pseudocode for the extended Euclidean algorithm. Your mistake is trying to use ordinary division to compute temp.

Multiply $3x^2 + a$ by the inverse of $2y$ to compute temp in your code and you should be good, at least if your goal is to multiply $P$ by 2. If you want to add distinct points, you need to compute $\lambda$ with a different formula, but the rest is the same; if you want to multiply by something other than 2, you should implement something akin to exponentiation by squaring.


(Open)PGP is a hybrid encryption system, it uses both public/private and symmetric key encryption. Public/private key encryption is very inefficient for any kind of data but very small one, so when encrypting for some private key, usually you're only encrypting some block cipher which is then used to actually encrypt the data.

For generating this key, a random number generator is used.


Hint: you can notice that $n! > 2^n$ (except for very small $n$).


DSA signatures with related k and unknown payloads

If the messages are unknown, there are no two messages $m_i, m_j$ such that $m_i = m_j$ and the messages have sufficiently high entropy (which might be shared across several messages, if the hash function is a CSOWF and the messages e.g. have low entropy unique sub strings or are made unique in some other way), and the underlying hash function is secure in a random oracle model and has an output bit length equal to or greater than $2n$ such that $q \lt 2^n$ (see below), then this scheme is secure in this hypothetical scenario.

Firstly, note that

$s_i \equiv h(m_i)/(k+i) + xr_i/(k+i) \pmod q$

Case #1 - large untruncated hashes (non-DSA compliant)

Suppose we give the adversary oracle access to the first term of the right hand expression

$h^\prime_i = h(m_i)(k+i)^{-1} \mod q$

Define the adversary $A_h$ such that $i$ is fixed, and that $A_h$ might submit any $j \ne i$ to the oracle and get the corresponding $h^\prime_j$ value. Then $A_h$ submits $i$ and gets either $h^\prime_i$ or $z \leftarrow_{uniform} \mathbb Z_q$. $A_h$ might continue to submit any queries to the oracle subject to the first constraint that $j \ne i $. If the function $h(m)$ and the $m_i$ messages have the assumed properties, $A_h$ will have but negligible probability of succeeding.

As noted, the assumption about the uniformity of $h(m)$ is problematic if the underlying implementation conforms to FIPS 186-3 with the only exception of the way the randomizer values are generated. Since FIPS 186-3 prescribes that the left most $n = |q|$ bits of $h(m)$ are used, we will get a clear bias with $h(m) < 2^n-q$ being twice as probable than $2^n-q \le h(m) < q$. However, if the hash output is at least $cn$ and is not truncated before being reduced $\mod q$ this bias will be at most $2^{-n(c-1)}$

Secondly, note that we now have

$s_i = h^\prime_i + xr_i(k + i)^{-1} \mod q$

Define the adversary $A_s$ such that $A_s$ might adaptively submit any $j$ subject to the same conditions as above. When $A_s$ submits $j = i$, the oracle returns either $s_i$ or $w \leftarrow_{uniform} \mathbb Z_q$. $A_s$ might then continue to submit queries as above.

Now, note that for any $w$ and $i$ there exists a value $z_{w,i}$ such that

$w = z_{w,i} + xr_i(k + i)^{-1} \mod q$

Hence, if the adversary $A_s$ is able to tell if the $s$-oracle returned $w$ or $s_i$, we have a distinguisher for $A_h$ as well, by noting that $A_s$ is able to tell $z_{w,i}$ from $h^\prime_i$.

Case #2 - truncated or equisized hashes (DSA compliant)

If the hash output is exactly $n$ bits in length, there will be a significant bias in $h(m) \pmod q$ as noted above. Given the other assumptions regarding the messages and the hash function, we might assume this is the only bias we have to consider. However, presuming $q$ is a uniform prime in the range $2^{n-1} \lt q \lt 2^n$, multiplication by $(k+i)^{-1} \mod q$ will mask this bias to some extent. Given that both terms of the right hand expression share this factor, the above proof is not valid in this case. Intuitively, though, the combined (and theoretically detectable) bias of $h(m_i) + xr_i$ ought to be masked to some reasonable extent by the $(k+1)^{-1}$ factor sequence, as long as the total number of signatures is not large enough.


For RSA cryptography, how long does it take to factor out P -1024 if given Q - 1024 and N - 2048?

You seem to be under the impression that factorizing (finding P and Q) means to try many primes and hope to find the right one, aka the "brute force" solution. This is not the case, it would take forever. Eg. 1024bit means

  179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216

possible numbers. Even with the best computers, it would take far longer than the universe exists. And to start with, 1024 is in the past, nowadays 4096 is common.
...point is, there are better (and more complicated) factoring methods, and with quantum computers it gets much better again (sad for cryptographers :/).

Anyways, to answer your direct question: "Neither".
"Finding" a prime number actually means

  Take any number and run some checks if it could be prime. If the check says
  "could be" often enough, then let's say it is a prime.

Why? Because getting hard evidence that a 4096bit number is prime is very slow too.

So, finding a prime means running checks. Checking if the second number (after division) is prime means running the same checks. There is no difference other than the division.


How to determine if padding has been used while encrypting a message with RSA?

Given the public key and a single encrypted file, the only way to check is to take the integer $e$th root of the ciphertext and see if the resulting value "makes sense" (where whether or not it makes sense is very context specific to the application at hand).

If you have access to additional information you can figure it out.

Access to an encryption oracle
For example, if you have access to an encryption oracle, i.e., something that will encrypt whatever you send it. Since you know the exponent is $3$, just send it the plaintext $2$, if it returns $8$, you know it is unpadded.

More generally, you could have it encrypt the same plaintext twice and see if they are equivalent. This would work especially well if the plaintexts must be of a specific, but understood format where something like $2$ would be rejected.

Access to executable code
If you have access to the source code doing the encryption, you can reverse engineer it to figure out what it is doing.

Access to decryption oracle
Ask it to decrypt your ciphertext and see what the answer is. Then encrypt the resulting plaintext yourself with no padding.


Are there any methods for constructing a password that can be reconstructed if forgotten and is as secure as randomly generated ones?

What you're asking for is if we can describe for you a process that would allow you to generate a password such that you can later guess it without knowledge of its outcome. But the problem is you have to explain what would stop an attacker from carrying out the same recovery process to guess your password:

If the recovery process used only public information, the attacker would just be able to do it themselves;
So it has to use some secret information, but if that secret is as strong as a random password then that doesn't gain you anything;
And if the recovery secret is weak then the password it reconstructs cannot be strong, because guessing the recovery secret is sufficient to reconstruct the supposedly "strong" password.

The simplest practical solution I can think of to forgetting a strong password is fundamentally low-tech: write the random password down and store in in a location that physically secure and/or guarded by parties you trust. This is not at all a fanciful or hypothetical recommendation; for example, 1Password (who I'm in no way affiliated with) provide a printable PDF "Emergency Kit" for users who wish to write down their master password and put it for example in a bank safe deposit box.
I can think of a more complicated elaboration of this: using secret sharing to split the secret into multiple "shares" so that a minimum number of them need to be brought together, and distributing them to different parties and/or locations and so on. But in this case you'd still be relying on a mix of physical security and trust; it's just a more elaborate version of writing down the password.


You don't need to know $m$. You know $m^3$ modulo each modulus, which is sufficient. You want to find:

$$c \equiv m^3 \pmod{n_b}$$

$$c \equiv m^3 \pmod{n_c}$$

$$c \equiv m^3 \pmod{n_d}$$

Because $n_b$, $n_c$, $n_d$ are pairwise coprime (assume they have no common factors) a solution must exist.

The Wikipedia page has a nice explanation of the algorithm to find $c$. The actual expression is:

$$c = c_b (n_c \cdot n_d) [ (n_c \cdot n_d)^{-1} ]_{n_b} + c_c (n_b \cdot n_d) [ (n_b \cdot n_d)^{-1} ]_{n_c} + c_d (n_b \cdot n_c) [ (n_b \cdot n_c)^{-1} ]_{n_d}$$

Where $[a^{-1}]_b$ is the multiplicative inverse of $a$ modulo $b$. Note $\gcd{(a, b)} = 1$ is always satisfied. Also, I used the notation $c_b = m^3 ~ \text{mod} ~ n_b$, $c_c = m^3 ~ \text{mod} ~ n_c$, $c_d = m^3 ~ \text{mod} ~ n_d$.

Let's try with some numbers. Suppose someone sends the message $m = 102$ to three different people with textbook RSA, with moduli $n_b = 377$, $n_c = 391$ and $n_d = 589$. So:

$$c_b = 102^3 ~ \text{mod} ~ 377 = 330$$
$$c_c = 102^3 ~ \text{mod} ~ 391 = 34$$
$$c_d = 102^3 ~ \text{mod} ~ 589 = 419$$

So the attacker wants to solve the following system of congruences:

$$c \equiv 330 \pmod{377}$$

$$c \equiv 34 \pmod{391}$$

$$c \equiv 419 \pmod{589}$$

Using the equation above, we obtain (compute each term separately for clarity):

$$t_b = c_b (n_c \cdot n_d) [ (n_c \cdot n_d)^{-1} ]_{n_b} = 330 (391 \times 589) [ (391 \times 589)^{-1}]_{377} = 24471571740$$

$$t_c = c_c (n_b \cdot n_d) [ (n_b \cdot n_d)^{-1} ]_{n_c} = 34 (377 \times 589) [ (377 \times 589)^{-1}]_{391} = 505836734$$

$$t_d = c_d (n_b \cdot n_c) [ (n_b \cdot n_c)^{-1} ]_{n_d} = 419 (377 \times 391) [ (377 \times 391)^{-1}]_{589} = 35452267942$$

$$\therefore c = t_b + t_c + t_d ~ \text{mod} ~ (n_b \cdot n_c \cdot n_d) = 1061208$$

And we get $m = \sqrt[3]{c} = \sqrt[3]{1061208} = 102 = m$.

Note this attack on textbook RSA would work on any exponent given a sufficiently large number of people, of course $e = 3$ is the most realistic setting (and easiest to demonstrate, for obvious reasons).

The idea, of course, being to use these relations with the CRT to manufacture a relation of the form $m^3 \equiv x \pmod{n'}$ where $n'$ is on the order of $n^3$ (and, more crucially, where $1 < m < n$) such that $m^3$ is not reduced (and so you can just take cube roots).