Could eVoting on the bitcoin blockchain be done?

Yes, it could be done. However, it would work a little different from what you imagine.

The government can create a new blockchain operating under zerocoin rules. The government could then distribute one satoshi per citizen. This distribution could happen for example by letting each citizen visit a government office to present their passport and receive their satoshi. This satoshi on the particular blockchain constitutes permission to vote for this election.

After distributing the satoshis, the government would then announce the candidate parties in the form of zerocoin addresses. Each citizen could then vote for the party of their liking by transferring their satoshi to the account of the party they are voting for.

Finally, when the elections are over, the blockchain can be frozen at a particular block number and each party can reveal their received amount. These amounts can then be compared to elect a winner or counted to receive seats in a parliament.

This scheme satisfies both your stated properties of double-spending prevention and vote secrecy.

However, this is not a good voting scheme, as it has many problems. One important problem is coercion; a citizen can be forced to give away their vote at gunpoint.


Forgeries can be made against this algorithm; here's how:

If the attacker gets the MAC with the two messages M0||M2 and M1||M3 as follows:

MAC(M0||M2) = Fk(0||M0) || Fk(1||M2)
MAC(M1||M3) = Fk(0||M1) || Fk(1||M3)

then, the attacker knows the values of Fk(0||M1) and Fk(1||M2), and thus can deduce the MAC of the message M1||M2 as:

MAC(M1||M2) = Fk(0||M1) || Fk(1||M2)

BTW: is this a homework assignment?


Can we assume that a hash function with high collision resistance also means a highly uniform distribution?

Define $H(x) = \operatorname{SHA-256}(x) \mathbin\| 1$; that is, append a single 1 bit to SHA-256.  Can you find a collision under $H$?  Does $H$ have anything resembling uniform distribution?

This counterexample is not merely pathological; designs like Rumba20 and VSH provide collision resistance but neither preimage resistance nor uniformity.

That said, typical ‘cryptographic hash functions’ like SHA-256, BLAKE2b, and SHAKE128 are designed for collision resistance and preimage resistance, and more broadly for random oracle modeling (barring length extension attacks on SHA-256), meaning that the outputs on distinct inputs can reasonably be modeled as independently uniformly distributed.

In the dark ages of the early '90s, when the United States still banned the export of cryptography as a munition, the ban covered encryption, per se, like DES—but had an explicit exception for authentication (22 CFR §121.1(XIII)(b)(1)(vi), since rescinded), and so the hash function Snefru was allowed to be published and exported.

A grad student named Dan pointed out in 1992 that you could use Snefru as a subroutine in an otherwise cryptography-free program to encrypt messages.  When he informed the United States Department of State of his remarkable discovery, and asked them to confirm his understanding that publishing his cryptography-free program together with the exempted Snefru would not fall afoul of the export controls, they were not amused.

The State Department's lack of humor led to a nearly decade-long court battle, Bernstein v. United States, about whether the regulations in 22 CFR §§120–130 and 15 CFR §§730–744 prohibiting the export of encryption software constitute prior restraint in violation of the First Amendment to the United States Constitution.  Eventually, the United States federal government, backed into a corner by an annoying grad student, relaxed the regulations and the case was dismissed.

Today, a newer incarnation of the same idea—using a hash function, ChaCha, together with a method inspired by the advanced technology of the one-time pad (also known in some circles as ‘xor’), to encrypt messages—protects the confidentiality of probably petabytes of data daily on the internet, in the form of the ChaCha/Poly1305 cipher suites in TLS.

But collision resistance is neither necessary—indeed, it is well-known that ChaCha is not collision-resistant—nor sufficient—as Rumba20 and VSH show—for indistinguishability from uniform random, which is what one needs for, e.g., a one-time pad to get any security.

P.S.  If you do use a hash function, e.g. generating the sequence of bits $H(k \mathbin\| 0)$, $H(k \mathbin\| 1)$, etc., and want to use that sequence of bits to choose an integer $x$ with $0 \leq x < n$ uniformly at random, make sure to do rejection sampling to avoid modulo bias if $n$ is not a power of two: if $H$ returns a string of $t$ bits interpreted as a $t$-bit integer, and $H(k \mathbin\| i)$ is below $2^t \bmod n$, reject it and try $i + 1$; otherwise return $H(k \mathbin\| i) \bmod n$


Why does TLS 1.3 AES cipher require both a server and client traffic key/iv?

Why is it necessary to derive the key/iv for both the server and client instead of a single key/iv for encryption and decryption?

Of course, it's not necessary for TLS 1.3 to be designed that way, however that's the way they decided to do it.
As for why, well, for all the encryption modes supported in TLS 1.3, it is necessary for security to never encrypt two different records with the same key/nonce combination.  With the current record design, the encryptor selects the nonce; hence, if two different encryptors (the client and the server) had the same key and selected the same nonce, well, things would be broken.
Now, they could have partitioned the nonce space; for example, tell the servers "you always encrypt with a nonce that starts with a "0" bit" and clients "you always encrypt with a nonce that starts with a "1" bit"; that would work, however they declined to do so.


Pre-image resistant but not 2nd pre-image resistant?

A cryptographic hash function $f : \{0,1\}^{*} \to \{0,1\}^n$ has three properties: (1) preimage resistance, (2) second-preimage resistance, and (3) collision resistance. Even further, these properties form a hierarchy where each property implies the one before it, i.e., a collision-resistant function is also second-preimage resistant, and a second-preimage resistant function is also preimage-resistant (with a condition on $f$).

In the case of (3) ⇒ (2), it's not too hard to see why: if an adversary cannot find any colliding message pairs, then they certainly cannot find a colliding message when one of the messages is fixed.

However, (2) ⇒ (1) is substantially trickier. For some intuition, consider a second-preimage resistant hash function $f$ that was not preimage resistant (modeled by being given access to a preimage-finding oracle). Suppose you were given a $m_1$; then you could compute $H(m_1)$ and consult the oracle for the preimage of $H(m_1)$. The oracle would then return a $m_2$ such that $H(m_1) = H(m_2)$.

This is very nearly a second preimage. The only question is if $m_1 \ne m_2$. Intuitively, given that $f$ maps infinitely-many inputs to a finite number of outputs, there "should be" a high probability that $m_1 \ne m_2$. For all real-life hash functions, this is pretty much the case, so a second-preimage resistant hash function should not lack preimage resistance.

However, it is possible to define "pathological" hash functions that have perfect, provable second-preimage resistance but not preimage resistance. The example given in chapter 9 of the Handbook of Applied Cryptography is this:

$$f(x) =
\begin{cases}
 0 || x & \text{if } x \text{ is } n \text{ bits long}\\
 1 || g(x) & \text{otherwise}
\end{cases}$$

where $g(x)$ is a collision-resistant hash function. In this case, for digests beginning with $0$, it's trivial to find a preimage (indeed, it's just the identity function), but such cases are provably second-preimage resistant, as there are no possible second preimages. In other words, this $f$ is bijective across the space of $n$-bit inputs.

To be more precise about when (2) ⇒ (1), Rogaway and Shrimpton have presented a theoretical analysis of the various relations between the three properties listed above in their Cryptographic Hash-Function Basics. Essentially, their analysis treats a hash function as having a finite, fixed-length domain, i.e. $f : \{0,1\}^m \to \{0,1\}^n$, wherein they show

"conventional implications", like the implication (3) ⇒ (2); these are essentially "true" implications in the sense that they are unconditional, and
"provisional implications", like the implication that (2) ⇒ (1); these are conditional in nature, relying on how much $f$ compresses the message space (as the message space gets larger relative to the digest space, the "stronger" the implication in a probabilistic sense).

So, provisional implications are essentially true if a hash function compresses the message space to a sufficient degree. (The "sufficient" example they provide is a hash compressing 256-bit messages to 128 bits.) Hence, second-preimage resistance implies preimage resistance only if the function in question compresses its input sufficiently. For length-preserving, length-extending, or low-compression functions, second-preimage resistance does not necessarily imply preimage resistance (as stated by the authors on page 8 about halfway down the page).

This should be intuitive given the above algorithm for finding second preimages given a preimage oracle. If you are expanding 6-bit inputs to 256 bits, it's actually quite unlikely that a preimage oracle would be able to find a second preimage. This isn't a formal argument, by any means, but it's a nice heuristic one.

Now, back to real life. Given the above algorithm for using a preimage oracle to find second preimages, I would not expect any real-life hash functions to have preimage attacks and not second-preimage attacks, especially since real hash functions typically compress data well.

On the other hand, I'm not personally aware of any historically-used, non-toy cryptographic hash function which has a second-preimage attack but not a preimage attack. Typically, collision resistance is the first thing attacked by cryptanalysts since it is (in a sense) the "hardest" property to satisfy. But if a hash function is found to be broken with regard to collisions, cryptanalysts typically go straight for the heart: preimage attacks. So, I don't know how much luck you'll have trying to find such a hash function.

You can look at the hash function lounge for some historic hash functions; it hasn't been updated since 2008, apparently, but still contains some useful info. I glanced through a few attacks and found mostly collision and preimage attacks, but you may have more luck.


Not using cryptography on URI:

If you store subscribers on a database, maybe you could also store additional (say) 128-bit random value on some column when there somebody about to unsubscribe. This way there is no meaning for the value beyond this transaction and it cannot e.g. leak anything about the key.

If you cannot use additional data on the database, then use e.g.:

Your favorite AEAD scheme (or Encrypt+HMAC scheme) to encrypt cid+pid pair and to attach authentication tag. Maybe e.g. GCM using 96 bit random IV and 96 bit authentication tag. If there is less than four billion customers and less than four billion product, that would fit in around 256 bits or the same size than (non-truncated) HMAC-SHA256. You may use some variant of base64 to encode the value in URI to 43 characters.

The HTTP standard does not specify how to encrypt or hash parameters. The TLS/SSL is the standard way to apply confidentiality and other security properties.


Why does gnupg create 4 separate keys and what does sub and ssb mean?

The abbreviations stand for the following:

pub -- public primary key
sub -- public sub-key
sec -- secret primary key
ssb -- secret sub-key

In asymmetric cryptography you always have key pairs: A public key to encrypt, a private (secret) key to decrypt. Here we have two key pairs: (1, 3) and (2, 4). They can be identified by their identical fingerprints.

But why are there two key-pairs? When generating an OpenPGP key with GnuPG, per default a primary key (pair), also called master-key, and a sub-key (pair) are created. The primary key, also called master-key, contains one or more user-IDs (name, email-address) and is used for for signing. The sub-key, signed by the primary key and thus confirmed to belong to its user-IDs, is used for encryption/decryption.

The idea for having a master-key with sub-keys is very well described here. If you want to deviate from the default behaviour and gain more control about the key generation, e.g. create only a single key-pair or select a certain cryptographic algorithm, you should try gpg --full-gen-key (introduced in GnuPG 2.1.17).


Secret sharing by using just "private secrets"?

The attacker sees AX and BAX, and just divides them to compute B. Then they see BX and divide again to compute X.


what is the order for the brainpool twisted curves?

What about the order $q$? Is the order the same for both curves?

Yes. This can be verified with the following commands:

openssl ecparam -name brainpoolP192t1 -genkey -text -noout -param_enc explicit

openssl ecparam -name brainpoolP192r1 -genkey -text -noout -param_enc explicit

This can be additionally verified by opening up RFC5639, which lists $q$ for both the twisted and non-twisted curves and shows them to be the same.

  If the curves are the same thing then couldn't one just treat them as aliases of one another? Like when you're randomly selecting $k$, between [$1, n-1$] and then multiplying the base point by that then you'd get the same answer no matter which curve you used?

No. As demonstrated thusly:

# generate private keys
openssl ecparam -name brainpoolP192t1 -genkey -noout -out brainpoolP192t1.pem
openssl ecparam -name brainpoolP192r1 -genkey -noout -out brainpoolP192r1.pem

# generate public keys
openssl ec -in brainpoolP192t1.pem -pubout -out brainpoolP192t1.pub
openssl ec -in brainpoolP192r1.pem -pubout -out brainpoolP192r1.pub

# sign using brainpoolP192r1
openssl dgst -sha1 -sign brainpoolP192r1.pem file.txt > signature.bin

# verify using brainpoolP192t1
openssl dgst -sha1 -verify brainpoolP192t1.pub -signature signature.bin file.txt

$p$ is the same as is $q$ but $a$ and $b$ are different.


XSalsa20 + Poly1305 authentication wtihout tag

The documentation is a bit misleading about crypto_secretbox_xsalsa20poly1305 that uses a 16-byte authentication tag of poly1305. The libsodium has more clear explanation on it. From Bernstein' paper's abstract;

Poly1305-AES computes a 16-byte authenticator of a variable-length message, using a 16-byte AES key, a 16-byte additional key, and a 16-byte nonce

I would be surprised that one authenticates an arbitrary message without using a MAC tag (Wikipedia quote);

In cryptography, a message authentication code (MAC), sometimes known as a tag, is a short piece of information used to authenticate a message—in other words, to confirm that the message came from the stated sender (its authenticity) and has not been changed.

Therefore the short piece of information must be somewhere!.


Is it possible to find what is the random generated key if I know the plaintext and ciphertext?

If you don't specify the stream cipher in question, then no.

If you do specify the stream cipher in question, and it meets some of the most modest security goals of a stream cipher, then no.


Does High Frequency Randomisation of valid and dummy messages in a high volume channel add security?

In addition to Paul's analysis, I'd point out that theres a few other issues.  The primary one is that, at best, you have increased the workload of your attacker by a factor of 1000, in exchange for increasing your own work load by a factor of 1000.  Let's say you're using a very poor encryption scheme that's known to be breakable in, say, 2^50 operations.  (after all, that's why you're relying on this obscuration right? because you didn't trust your crypto?)  Now the attacker needs to spend 1000*2^50 2^59.9 operations to crack it.  For the amount of extra resources you applied to send that much extra fluff data, you didn't get very much of a leg up on your attacker.

Worse, if your encryption is as bad as you think it might be, there's no guarantee that the attacker must fully process each message to discard it.  It may be very easy to identify which message is real because you may be able to identify the signature of the broken cryptography in the first place.

Finally, consider that you are absolutely dependent on the quality of your random number generator.  If you have a PRNG like that, and you have resolved all of the synchronization issues that Paul mentioned, you might as well have just used the PRNG to generate a one-time-use pad.  It would give you more security for less trouble.


Can we use Pohlig-Hellman Exponentiation Cipher with a PRG to achieve an oblivious PRF

I believe this protocol should be satisfying the requirements of an
  Oblivious PRF.

This protocol is (nearly) identical to what is proven secure as an OPRF in the OPAQUE paper (Appendix A). There the OPRF is described (up to some formal notation) as follows, I'll annotate your notation in parenthesis:

Parameters: A multiplicatively-written Group $\mathbb G$ of order $q$ where the discrete logarithm is hard. A hash function $H(\cdot,\cdot):\{0,1\}^*\times \mathbb G\to\{0,1\}^l$. A hash function $H'(\cdot):\{0,1\}^*\to\mathbb G$.
(You call $H'$ a "PRG" and use $\mathbb Z_p$, that is the group of integers modulo $p$ with multiplication, as $\mathbb G$. This means that if it says $a^b$ below it means $a^b\bmod p$ for this group. If you need guidance on instantiating any of these hash functions, have a look at my prepared answer for this)

Setup: The Server $\mathsf{S}$ picks $k\gets_R\mathbb Z_q$, that is the server randomly picks a non-negative integer smaller than $q$.

Execution:

$\mathsf U$ wants to learn $F_k(x)$ with $F:\mathbb Z_q\times \{0,1\}^*\to\mathbb \{0,1\}^l$ without learning $k$ nor having $\mathsf S$ learn $x$.

$\mathsf U\to\mathsf S: H'(x)^r$, that is $\mathsf U$ picks an $r\gets_R\mathbb Z_q$, stores it and sends $H'(x)^r$. (This is step 1 and 2 of your protocol.)
$\mathsf S\to\mathsf U: \left(H'(x)^r\right)^k$, that is $\mathsf S$ simply exponentiates the given input with its secret value and returns the result. (This is step 3 in your protocol)
$\operatorname{return}\ H\left(x,\left(\left(H'(x)^r\right)^k\right)^{1/r}\right)$ That is $\mathsf U$ simply "unblinds" the received value (which is the decryption in your commutative cipher) and returns the original input and the received value through another hash function. (The last hashing step has been missing)

Additional notes: In OPAQUE, $x$ is the password and one can see $H'(x)^k$ as the "salt" and $H(\text{pw},s)$ as a password-based key derivation function, which gets evaluated client-side to decrypt a server-stored long-term DH key-pair. Then this key-pair with an ephemeral keypair gets used in a standard DH-based key-exchange computation (in this case HMQV).


Does having a bunch of plaintext/ciphertext pairs help you break a ciphertext with unknown plaintext?

The known plaintext is only a useful tool for establishing that you actually found the right key if we assume a secure cipher (and mode of operation, etc.). It won't help you creating a faster than brute-force attack, as ciphers are assumed to be secure against known plaintext attacks.

So the complexity of breaking the cipher is simply still $m - 1$ (half the key space) on average, i.e. no change from normal brute forcing.


Looking at it closely, the linked RFC formally references SP800-56Ar2 section 5.8.1, which buries in 5.8.1.2.1:

Note: When the single-step KDF specified in Section 5.8.1.1 is used with H = hash as the auxiliary function and this concatenation format for OtherInfo, the resulting key-derivation method is the Concatenation Key Derivation Function specified in the original version of SP 800-56A. (emphasis mine)

Based also on this, I guess that when the authors of the RFC wrote "Concat KDF, as defined in Section 5.8.1 of [NIST.800-56A]", they had in mind  SP800-56Ar1 section 5.8.1, titled "Concatenation Key Derivation Function (Approved Alternative 1)", which is what I would use if I had to implement the thing. I suggest to ignore the RFC's reference to the aforementioned SP800-56Ar2, which seems to be a well-intentioned but unfortunate change; as well as the currently applicable SP800-56Ar3.
Big picture: that KDF hashes the concatenation of a 4-byte counter initialized at 1 (big-endian), the shared secret obtained by ECDH, and some other information passed as input. The counter is incremented and the process is repeated until enough data was produced. The concatenation of the hashes, truncated as needed, forms the output to be used as key. Except for the data hashed and the position of the counter (at start rather than end), this is similar in principle to MGF1 of RSASSA-PSS and RASAES-OAEP in PKCS#1v2.2.
If the hash is SHA-256 as now in the question, as well as in this code which claims to successfully implement something (without stating clearly against what it is tested), I do not see that this KDF has an exploitable weakness of cryptographic nature in the context. This is not a statement about code.


Does not using padding mean a lack of security?

I've read several texts which say that if the entire plaintext is a multiple of the block-size padding is not required (and not using padding would not mean a loss of security). I generally disagree on this.

In modes where padding is used (e.g., CBC), padding is mandatory. This is per spec. Not including the padding is simply not an option.

  In some special cases, for example in CTR of OFB mode padding could even unveil more information about the block-cipher output than not using it. But many currently used paddings are randomized.

It's a bit confusing what you're actually asking here, because CTR and OFB don't use padding, as they're stream ciphers. You could pad them (for instance, to make traffic analysis more difficult), but whether or not to do so is a decision completely independent of the block size of the underlying cipher. Padding to the block size is done for block modes like CBC.

  When using a randomized padding with modern block ciphers the smallest change in the block-cipher input will change the entire block-cipher output.

For the final block only. Unless you pad at the front, which isn't done by any modes I'm aware of. For streaming modes of block ciphers, padding doesn't change any of the bits of the actual ciphertext. Unless, again, you pad at the front.

  Therefore the randomness of the padding contributes to the encryptions security.

No, not even slightly. Even if you did pad at the front of a block cipher and get a completely new ciphertext as a result, this doesn't directly contribute the security of the block cipher in the least. If the block cipher was secure beforehand, you simply have a different stream of bits that are equally secure. If the block cipher was insecure beforehand, you still have a stream of bits that is (generally) going to be vulnerable to the same set of attacks as before.

Padding like this might change some bits, but it doesn't improve the actual security of the cipher. In fact, some times, it can weaken it (see CBC padding oracle attacks). Padding in block ciphers isn't done for security, it's done because block-sized inputs is required by the underlying block cipher.

  My first question is whether the above statement is correct or not and why. And second: Are modes like CBC/PCBC more secure than modes like CTR/OFB? Or does it depend on the used padding?

Your question doesn't really make sense as asked. These modes have different security properties and fail in different ways. CBC can fail catastrophically to padding oracle attacks because of its padding. CTR can fail catastrophically when IVs are reused, but padding won't help solve this problem. Both are equally secure when used correctly, but CBC is somewhat harder to use correctly in common use-cases.


Message authentication vs entity authentication

Message authentication (sometimes called data origin authentication) is the assurance that a given entity was the original
  source of the received data.

  Entity authentication (or user authentication) is the assurance that a given entity is involved and currently active in a
  communication session. [1]

A MAC provides data origin authentication as the receiver knows that the message and corresponding MAC could have only come from the one person with the shared key. Used on its own, a MAC will not give you entity authentication.

A digital signature also provides data origin authentication as the verifier knows that only the owner of the private key could have produced a valid signature. Used on its own, a digital signature will not give you entity authentication.

You mention a shared symmetric key and whether or not a security service is provided. You are likely confused with non-repudiation.

  Non-repudiation is the assurance that an entity cannot deny a previous
  commitment or action.[1]

If there is a shared key (such as in the MAC setting) one user could deny having produced a MAC tag on the message as the key is shared- external parties are not sure which owner of the MAC key could have produced the tag. Whereas with digital signatures, each key is unique to each user, so there is non-repudiation as only one user could produce a valid signature.

Used naively, neither MACs nor signature provide entity authentication as signatures/MAC tags could be forwarded or replayed. Recall: message authentication provides assurance on the original source and does not tell us anything about when the message was sent or who is sending it now.

Consider the following scenario with data origin authentication but no entity authentication: Alice could sign a message and send the message and signature to Bob. Bob could then forward the message and signature to Charlie, who can verify that the original source of the signature was Alice (as there is message authentication) but not that they are communicating with Alice now. Hence there is no entity authentication.

To get entity authentication, we need some kind of freshness. For example, for Charlie to be assured about Bob's identity and current activity, Charlie could request Bob produce a valid signature on a fresh nonce, generated by Charlie. This ensures that Bob is currently active and that the signature came from him. Obviously, this may be vulnerable to man in the middle attacks (Bob could forward the none to Alice to sign, and return the signature to Charlie), but there are things that can be done about this (for example, by asking Bob to sign the challenge along with a session ID: the session ID is unlikely to be the same as the session between Bob and Alice, so Alice would not sign).

In general, think of entity authentication as data origin authentication + freshness.

[1] Reference: Everyday Cryptography, 2nd Edition by Keith Martin (2018).


What is the relation between AES and PTK in WPA2 wifi

WPA2 uses either a password or a pre-shared key to create the PMK.

Specifically, the PMK comes from:

If there is a PSK, the PMK is the PSK
A PSK is either a 256-bit key or derived from a passphrase
If a passphrase is used, it generates the PSK using the AP SSID as the salt: PSK = PBKDF2(HMAC−SHA1, Passphrase, SSID, 4096, 256)
If there is no PSK, the PMK is derived using 802.1x EAP exchange, usually RADIUS

Once both the client and AP have the same PMK, they prove to eachother they have matching keys using a 4-way handshake, which is also used to derive the PTK by adding a nonce from each party.

Specifically, the 4-way handshake does the following:

Confirm the client’s knowledge of the PMK
Confirm the AP's knowledge of the PMK
Derive a new and unique PTK
Install encryption and integrity keys
Encrypt transport of the AP generated GTK to the client
Confirm cipher suite selection

The PMK, nonces, and handshake MAC addresses are run through a PRF based on HMAC-SHA1 to derive the 512-bit PTK. During the handshake the AP also transmits the 256-bit GTK, or Group Temporal Key, to the client. The PTK and GTK are split into several components, some of which are used as AES keys for different types of network traffic, and some of which are integrity keys.

KCK = PTK bits 0-127, the key confirmation key
KEK = PTK bits 128-255, the key encryption key
TEK = PTK bits 256-383, the temporal encryption key for unicast traffic
TMK = PTK bits 384-511, the temporal MIC keys for TKIP
GEK = GTK bits 0-127, the group encryption key for multicast traffic
GIK = GTK bits 128-255, the group integrity key for TKIP

When WPA2 is used the cipher is CCMP, which is an AES-CTR based mode with a CBC message authentication, and thus the TKIP integrity keys are not used


implication of tweak on bruteforcing a block cipher

The tweak is generally not secret, i.e. the adversary knows it (perhaps even chooses it, depending on the attack model) and thus doesn't have to try to guess it.  So no, tweaks don't increase the effort to brute force a cipher ... unless of course the tweak is kept secret, in which case it may or may not increase the required effort, depending on how the tweak is mixed into the cipher state.


Differential privacy on multiple queries – what is the behavior?

It would be helpful to have a link to the paper you are referring to. But the basic composition theorem says that each query $i$ an attacker sends to the database will just add its corresponding $\varepsilon_i$ to the total $\varepsilon$ of the entire process: $\varepsilon=\sum_i\varepsilon_i$. So "session" probably means "single query" in the context of your question.

And yes, your objection is a good one. If you use differential privacy in an interactive context, then you need to either:

split your total privacy budget across all users (and when it runs out, stop anyone from querying the database);
or assume that your users are not collaborating, and have some authentication in place to make sure each user cannot go above the privacy budget by connecting to the system as multiple people.


If you use an augmented PAKE (such as AuCPace or Opaque), the server never gets a copy of the password in the first place.  Hence, to update the password, you would reregister with the new password, but the reregistration process wouldn't involve sending the password.

If you use a balanced PAKE (such as Spake-2), well, the server does need the password.

Augmented PAKEs are designed to be used in a client-server scenario (where the client always initiates the negotiation, and we don't want the server to have the password in the clear); balanced PAkES are designed for peer-to-peer scenarios (where either side may want to initiate it, and so both sides need the password)


What is meant by domain separation in the context of KDF?

With KDFs, you need domain separation when you use the same initial key material to generate keys for different purposes like using the same initial key material and nonce to generate encryption and signing keys, you provide the KDF some data about the domain (encryption or signing) so it can generate different (private) keys. eg. for HKDF there is an info parameter that can be used for domain separation, see here.

Domain separation is a broader concept and also applies when the same hash function for hashing different kinds of data in a system, so if you wanted to hash say user id and user account balance using the same hash function, you will use different domain separators like user-id (assuming user-id is numeric) and user-bal. Another common example is hashing leaves and non-leaves in a Merkle tree, see here for more details.


Maxwell's vanity public key is a result of how the generator of the secp256k1 was chosen; as explained by Maxwell himself.

For some reason, the generator $G$ is the double of the point:

x = 0x00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63,
y = 0xc0c686408d517dfd67c2367651380d00d126e4229631fd03f8ff35eef1a61e3c

which is exactly Maxwell's vanity public key. Its private key is 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1 which is $1/2$, i.e. the inverse of $2$ modulo the curve order $n$. This is also equal to $(n+1)/2$.

The big question is: why was the secp256k1 generator chosen like that? I have no idea. But note that it's not difficult to find a generator with a lot of leading zeroes.


Simplified Lagrange interpolation formula inside Shamir's secret sharing scheme

All these calculations are done $\bmod{17}$.

$2^{-1}$ means here the number, $x$, that satisfies the equation $2x = 1 \pmod{17}$. (Note that this is the same definition that we use for the reals). When you're working $\bmod{17}$ (or any prime number, in fact), every number except 0 has an inverse.

To calculate inverses efficiently, you should use the extended Euclidean algorithm. But with a small number like 17, it might be worthwhile to just construct a multiplication table to get practice with modular arithmetic.


how to efficiently prove the query result is empty?

Obviously something needs to be trusted. If there is no prior  trusted something it can't be done.
In one setup used in DNSsec a trusted party signs empty intervals according to some ordering. So when you want to give a negative answer you provide the signed empty interval.
Obviously there is a problem with the validity of such answers when the data changes. You may get a properly signed but obsolete answer. Though people can in many cases commit on a  certain record remaining valid for a significant time frame. Commiting to a range remaining empty is much harder.


Can big numbers multiplication be a valid form of encryption?

Given a vector $[S_0 S_1 x_1, S_0 S_1 x_2, ...]$, it is quite easy to recover $S_0 S_1$ (by computing the GCD of the various elements).  With that information, the attacker can then recover the values $x_1, x_2, ...$, and so yes, a semihonest adversary could easily recover the $X_{reg}$ values.


Subtracting one pederssen commitment from another

how do I subtract one commitment from another?

Actually, it's surprisingly simple; you subtract the two commitments (and, no, that's not a joke, that's really how you do it).

That is, if we have a commitment $C_1 = x_1G + r_1H$, which is a commitment to the value $x_1$ (you don't know what the values $x_1, r_1$ are, but the prover does.

And, you have a commitment $C_2 = x_2G + r_2H$, which is a commitment to the value $x_2$ (again, known to the prover).

Then, all you do is compute $C_1 - C_2$, that is subtracting these two elliptic curve points.

We have $C_1 - C_2 = (x_1 - x_2)G + (r_1 - r_2)H$; where the prover can compute $x_1 - x_2$ and $r_1 - r_2$, and so this is a valid commitment to the value $x_1 - x_2$ (which the prover can open, should he choose to), which is what you are asking for.

However, I am unfamiliar with the javascript package you're using; I am unable to point you to how you'd do that...


No.

Basically your question is:

  The car maker X recently updated its flag ship car and the motor cycle maker Y makes a bike that is accelerating faster in straight lines - will the Lorry maker Z make a new lorry soon?

And I‘ll try to put this in laymen’s terms:

AES as a successor of DES is - in comparison to the lifetime of DES - relatively young.

Additionally, you are comparing ciphers that are not equivalent. ChaCha20 is a stream cipher and AES is a block cipher. The SHA family of hashing functions got new family members because the existing ones were showing signs of age and were generally thought to be feasible to break in several years because of the increasing computing power as well as increased progress in the cryptanalysis of sha1.

As to why you think AES would be slow, as Steffen said in the comments: this only might be true for software implementations. Yet, even smartphones do have hardware accelerated AES.

The process of replacing a cipher is very lengthy and I didn’t yet hear a call for papers for a successor of AES, so there should be at least years until AES gets replaced, probably a decade or two.

That being said, post-quantum cryptography is an active field of research and depending on when good enough quantum computers will be possible, a paradigm shift in standard ciphers will be necessary - yet I don’t think this applies to AES.


Authenticated encryption mode for stream cipher?

An OCB like mode seems impossible with stream-ciphers. It's coupled tightly to the concept of a keyed permutation i.e. a (tweakable) block-cipher.

Many authenticated encryption actually combine two distinct primitives. It's just that the specification and API only expose the combination.

Essentially these xor a key-stream into the message to encrypt it (i.e. they use a synchronous stream cipher), and then authenticate the ciphertext using a MAC. Often they use part of the key-stream as one-time keys for the MAC.

AES-GCM is built by combining a polynomial one-time MAC called GHash with the stream cipher AES-CTR.

While AES itself is a block cipher, AES-CTR behaves like a stream cipher. GCM doesn't use AES in a way that'd prevent the use of a stream cipher.
Salsa20-Poly1305 is built by combining a polynomial one-time MAC called Poly1305 with the stream cipher Salsa.
Poly1305-AES is built by combining a polynomial one-time MAC called Poly1305 with the stream cipher AES-CTR.

Then there are some stream ciphers which provide authentication without a separate primitive. These constructions aren't synchronous stream ciphers, and can't be used together with a one-time-pad or plain key-stream.

Helix and Phelix are authenticated stream ciphers that merge authentication and encryption. There has been some criticism of their security, but I'm not sure if that criticism is actually valid.
Keccak (built on an unkeyed permutation) using the duplex constructio can considered an authenticated stream cipher


How vulnerable is one-time pad (OTP) encryption, if the OTP is used twice, with a random substitution scheme

Bad idea (as far as I know & understood).

First, let's make sure you do not confuse Vernam cipher (XOR) with OTP.

OTP (One Time Pad) requires you – as described here – to use (1) a truly random one-time pad value, (2) generated and exchanged in a secure way, (3) at least as long as the message, and (4) only to be used once. So, what you are describing is not a One-Time-Pad.
Vernam cipher applies this concept with a stream cipher (simple XOR)

The best example of “miss-using” a OTP is usually given as:

$c_1 = m_1 \oplus k\\
c_2 = m_2 \oplus k\\
c_1 \oplus  c_2 = m_1 \oplus k \oplus m_2 \oplus k = m_1 \oplus m_2$.

where using the same key twice defeats its purpose and provides interesting information on the plain text (statistical attack).

Why your idea is bad ?

Given Kerckhoffs' principle:

The system must be practically, if not mathematically, indecipherable;
It should not require secrecy, and it should not be a problem if it falls into enemy hands;
It must be possible to communicate and remember the key without using written notes, and correspondents must be able to change or modify it at will;
It must be applicable to telegraph communications;
It must be portable, and should not require several persons to handle or operate;
Lastly, given the circumstances in which it is to be used, the system must be easy to use and should not be stressful to use or require its users to know and comply with a long list of rules.

Therefore you must consider that your Vigenere substitution table has to be publicly known : The secret should only rely on the OTP value. Hence the point of randomizing your substitution table is not that interesting any more.

Therefore, given the known substitution, statistical properties can be found that would defeat the randomization idea.

By the way, this idea is close to the design of Enigma, where the substitution table changes every round defined by an initial key, which is kept over the course of a day. Have a guess what happened during WW2... What would have happened if the Germans had changed their keys between every transmission?

PS: Rolling your own crypto is always a bad idea.


The total number of possible 12-word "seeds" is $2048^{12}$ as you already noticed.

The entropy of such a seed is $\log_2{(2048^{12})} = \log_2{((2^{11})^{12})} = \log_2{(2^{132})} = 132$ bits.

Therefore, remembering such a 12-word seed is equivalent to remembering a 132-bit key.

If you want to play it safe, pick a seed with 256 bits of entropy or with 24 words. (Because $\log_2{2^{11\lambda}} \ge 256 \Rightarrow \lambda > 23.3.)$


Is it feasible to break Diffie-Hellman key exchange when the implementation uses a poor-quality PRNG?

An attack would be trivial if the seed of the RNG was only 32 bits; just enumerate the seeds, and test which matches the intercepted messages. That's easy.

However the default Java Random class uses a 48-bit state and seed (which would still be attackable, though $2^{16}$ times less easily), and there are safe subclasses, thus use of Random does not imply an (insecure) 48-bit state, if the object really is a SecureRandom. See this Java 1.4.2 doc or this Java (1.)7.x one.

Update: While it seems the seed of the default Java Random class is 48-bit, its default seed indeed is 32-bit on some old Java platforms, and predictable to some degree on top of that; it is 48-bit on the latest Java platforms, and seems less predictable (though it could still be predictable/repeatable in a virtualized context).


Groth-Sahai proofs and the hidden-bits model

The hidden bits model is an abstraction of the CRS where the prover is able to reveal some random bits and not others (and where these are guaranteed to be uniformly distributed). The Groth-Sahai approach indeed uses a trapdoor in the CRS but its not the same as the hidden bits approach since the trapdoor is used in a different way (in the hidden bits model the trapdoors are the preimages of each block which enable revealing the bits).


What is the difference between "asymmetric key cryptosystem" "asymmetric cryptography" terminology?

The basic definitions from Wikipedia.

  Cryptography or cryptology is the practice and study of techniques for secure communication in the presence of third parties called adversaries.

  In cryptography, a cryptosystem is a suite of cryptographic algorithms needed to implement a particular security service, most commonly for achieving confidentiality (encryption)

  Public-key cryptography, or asymmetric cryptography, is a cryptographic system that uses pairs of keys: public keys which may be disseminated widely, and private keys which are known only to the owner.

Asymmetric Cryptography is the general technology to study techniques for securing communication with public-key Cryptography. Eg. public-key encryption, digital signatures.

Asymmetric Key Cryptosystem is the suite of asymmetric cryptographic algorithms applied. Eg. RSA, ECC.


Known-plaintext attack on two-dimensional affine cipher

Your subtracting two known solutions would be one way to eliminate $b$ from the equations and allow you to work only with $A$.

However, you've already been told that $b = (0,0)$, and so we don't need to eliminate it.

Instead, we know that the cipher satisfies the relations (omitting $b$ because that's known to be 0):

$$\begin{gathered}
  A \times \left[ \begin{gathered}
  d \\
  5 \\
\end{gathered} \right] = \left[ \begin{gathered}
  7 \\
  4 \\
\end{gathered} \right]\end{gathered},
\begin{gathered}
  A \times \left[ \begin{gathered}
  3 \\
  1 \\
\end{gathered} \right] = \left[ \begin{gathered}
  d \\
  c \\
\end{gathered} \right]\end{gathered}
$$

Where $A$ is a 2x2 array, and all math is done in $GF(16)$.  So, if we replace $A$ with the array $A = \begin{gathered}
  \left( \begin{gathered} x \\ z \end{gathered} \begin{gathered} y \\ w \end{gathered} \right) \end{gathered}$ (where $x, y, z, w$ are unknown values in $GF(16)$, we have:

$$d \cdot x + 5 \cdot y = 7$$

$$d \cdot z + 5 \cdot w = 4$$

$$3 \cdot x + 1 \cdot y = d$$

$$3 \cdot z + 1 \cdot w = c$$

By doing Algebra in $GF(16)$, it's easy to solve these simultaneous equations (hints: remember, $GF(16)$ is a field, and so algebra works there just as you'd expect; you'll need to compute multiplications and inverses in $GF(16)$, if you don't have any tooling on hand to do that, you might find it helpful to whip together a quick program.


Are convergently-encrypted ciphertexts safe from collision attacks?

The answer should be "No. A convergently-encrypted ciphertext is not safe from collision attacks."

Just because it is encrypted convergently does not mean it is not subject to collision attacks. MD5 has 128 bits, therefore, I could expect to have to generate at worst around 2^64 attempts to crack it.

Each collision attempt is more complex to generate because of the need to generate a new key via SHA256, reencrypt, and recompute MD5. There is no need to re-SHA256 the entire plaintext each time for the key, and it is also not obvious whether or not there might be a way to exploit known weaknesses of the MD5 hash to crack it in less than 2^64 attempts, but the question as stated was whether it was safe from a collision attack, and the simple answer has to be "No".

The 2^64 worst case seems to be similar to that of the Google SHAttered SHA1 collision demonstration even if generating each attempt requires more computation for convergent encryption. "Safe" might be a relative term that I did not define. I will try to be more concise in the future. But using MD5 to guarantee non-colliding convergently-encrypted content should not pass a security review. This would be why in the SHA2 specification there is no hash with less than 224 bits, which is 96 rounds greater than MD5, a factor of 2^48 difference for collision attacks.


RSA: Know the public key from a pair of plain text and their cipher?

From a couple of plaintext/ciphertext $(m_1, c_1)$ and $(m_2, c_2)$, then the modulus $n$ is a factor of
$$
\gcd(m_1^e-c_1, m_2^e-c_2).
$$
The explanation is that
$$
c_i = m_i^e - \lambda_i n
$$
for some unknown $\lambda_i$, so $n$ both divides $m_1^e-c_1$ and $m_2^e-c_2$.

Of course, this solution works if you know $e$, but it can be tried with some classically used values ($e=3$ for instance).


Is the ChaCha20 block function reversible using known plaintext?

The function which generates keystream blocks is based on a 512-bit permutation function. A permutation is, by definition, bijective.

The inverse of this permutation particular is trivial to implement in software. Just perform the individual operations (add, rotate, XOR) in reverse order, replacing modular addition with modular subtraction and reversing the direction of rotations.

Trying to reverse the entire keystream-block-generating function will fail, though, if the key is not already known. Actual keystream blocks are formed by combining  the input bits of the permutation with the output bits.1 Part of those input bits are key bits (which should be uniformly distributed and secret).

Since the permutation function scambles inputs so well, you can basically treat each input and its corresponding permutation-output as being statistically independent.

(Warning: Diliberate over-simplification. This is for illustrative purposes only. I don't want to say that "scrambling well" is sufficient. Or even that ChaCha's internal permutation is good enough to abuse in non-standard ways.)

If you change one input bit other than the key, then the output of the permutation will look completely different. When the secret key gets added back in, it obscures the value of the actual permutation output.

You would have to guess the 128-bit or 256-bit key before you could work backward even if you knew the full value of the keystream block in addition to the non-secret parts of the input vector. (The IV, counter, and constants. Adding these non-secret inputs to the permutation output does nothing to affect security, but it's included in the algorithm specification anyway for software efficiency reasons.)

One could almost make a stronger claim, that the keystream-block-generating function is one-way in the same way that hash functions are one way. Hash function design was actually a source of inspiration for ChaCha20's predecessor.

By one-way I mean there is no efficient algorithm to compute an input which produces an arbitrarily chosen output value. That's probably not possible (or at least is non-trivial) for any non-zero output block value.

The construction $F(x) = x \oplus P(x)$ should make $F$ a one-way function if $x$ has sufficiently many bits and $P$ were a random permutation. (Chosen uniformly from the set of all $(2^n)!$ possible n-bit permutations.)

Such a permutation would be unlikely to have any systemic relationship between input and output values. That thwarts the search for preimages for an ideal $P$. The same would be true if $\oplus$ were replaced with $\boxplus$.

We don't currently know an algorithm to find preimages for ChaCha20's hash-like operation, when we don't have foreknowledge of that preimage, with the exception of the value zero.2

That exception could be really important for some applications. So don't take the risk in adapting ChaCha to roll your own algorithm!

1. Specifically, ChaCha20 uses mod $2^{32}$ addition on the 16-word input/output vectors. It would also have worked if the design called for XORing inputs and outputs bit-for-bit, since both addition and XOR are non-linear with respect to the permutation function and neither operation should produce biased results.

2. ChaCha20 uses a pure ARX permutation. $F(0) = 0$ because $P(0) = 0$ because $0 \oplus 0 = 0, 0 \boxplus 0 = 0, \text{and}\ 0 \>>>> r = 0$.


Extracting Private Keys in Diffie Hellman

This is as hard as computing the discrete logarithm: Assume you have an algorithm $\mathcal{A}$ that given $g^a$, $g^b$ and $g^{ab}$ efficiently computes $a$ and $b$ for uniform $a$ and $b$. You can use this algorithm to compute discrete logarithms as follows: Given $h = g^a$, choose a uniform $b$, compute $g^b$ and $h^b = g^{ab}$. Now give $g^a$, $g^b$ and $g^{ab}$ to $\mathcal{A}$ to obtain $a$, the discrete logarithm of $h$.


Newbie question: one-way functions in cryptography

So it doesn't look like a one-way function to me.

What you're missing is the scale and basic ideas used in cryptography. Namely the following three facts:

Cryptographic exponents for discrete logarithms have thousands of bits instead of 3 as the example in the question. As such merely trying one value at a time, would take several billion years at least.
In cryptography, you only ever see the result of the exponentiation after the modular reduction (the third row of the graphic), because there are efficient algorithms for finding logarithms over the real numbers.
When using these system in cryptography we don't actually perform $2^{1000}$ or so multiplications but instead use repeated square and multiply which brings this down to a few thousand multiplications. Note that this algorithms requires full knowledge of the exponent to be applied.


How come Public key cryptography wasn't discovered earlier?

If you read about Merkle's experience with bringing the subject to the mainstream, you might be surprised. His professor rejected his initial proposal and show little interest in any further developments:

...We were required to submit two project proposals, one of which we would complete for the course. I submitted a proposal for what would eventually become known as Public Key Cryptography -- which Hoffman rejected. I dropped the course, but kept working on the idea.

He showed it to a different faculty member and was encouraged to publish it. His proposal to the Communications of the ACM was rejected:

... I showed an early draft to Bob Fabry, then on the faculty at Berkeley, who immediately recognized it as both novel and valuable and said "Publish it, win fame and fortune!" I then submitted it to Susan Graham, then an Editor at the Communications of the ACM in August of 1975. As I was to learn, Fabry's response was rare.
Graham sent my submitted paper out for review and received the following response from an "experienced cryptography expert" whose identity is unknown to this day:
"I am sorry to have to inform you that the paper is not in the main stream of present cryptography thinking and I would not recommend that it be published in the Communications of the ACM."
"Experience shows that it is extremely dangerous to transmit key information in the clear."
With this blanket rejection of public key cryptography by an "expert", she rejected my article. She "was particularly bothered by the fact that there are no references to the literature. Has anyone else ever investigated this approach. If they consider it and reject it, why?"

Novel concepts that aren't "mainstream" can be difficult to accept:

I had failed to provide any references to the prior work on public key cryptography, and the reasons previous workers in the field had rejected it as impossible. I should have looked up "public key cryptography" on Google before submitting my paper. My defense is feeble: there was no Google, the term "public key cryptography" did not yet exist, and there were no previous workers in the field. There were no words for what I had done, and looking up a concept to show that no one had previously thought of it is difficult. This is not a unique problem: it illustrates a problem faced by anyone trying to explain a new idea to an "expert" who expects a properly referenced article anytime anyone tries to explain something to them. The more a new idea is unrelated to any prior idea or concept the more it must appear as a squawling bastard, naked and alone, appearing de novo and lacking any respectable pedigree or family to vouch for its acceptability.
... CACM eventually published the paper, though only after almost three years of delay, and only after others (who were better able to persuade their editors to publish in a timely fashion).

Conclusion
While the utility of public-key cryptography is obvious to us, this was not always the case. Encryption that is secure when you know the key almost sounds like something that can't exist because it would be too good to be true. So you can certainly forgive people for not pursuing the idea seriously.


How are RSA and ElGamal compatible in PGP?

When creating a signed and encrypted PGP message, you only use your own keypair in the signing phase -- it's not used when encrypting the message (that only uses the recipient's public key). The recipient uses their own keypair only to decrypt the message, not to verify the signature. The two keypairs don't interact at all; that's why they don't have to be the same algorithm.


RSA key requirements so that it can decrypt a DES key

A DES key is 56 bits long or 8 ASCII(7 bit) characters.
The rsa public key n must be larger than that.
However RSA key only barely big enough to hold a DES key would give almost no security at all.
Common RSA key lengths today are 2048 or even 4096 bits long.
512bit RSA keys which used to be reasonably common can now be broken in minutes with commercially available cloud services. So big enough to be even remotely secure will be much bigger than the minimal size to encrypt a DES key.
P.s
If you want to use OAEP (and you do) you need some extra wiggle room beyond the raw message size but still don't go anywhere near secure key length.


How is the current used IV (nonce+ctr) synchronized among both communicating entities?

In CTR mode the counter starts from $0$, therefore one doesn't need to send the initial value in the CTR mode.
$$\text{64 bits nonce}||\underbrace{\text{00000...00000}}_{64 \, zeros}$$

Using the nonce more than one file ( a derived question )

If you want to use the nonce ( yes it is nonce in the CTR mode) in more than one file, then make sure that the counter is not repeated. This can be achieved by encrypting the next file's counter to the previous file's last counter plus 1. I.e., the previous file used the counter from $i$ to $j$ than the next file's counter must be started from $j+1$, and make sure that $j<2^{64}$, and no round to $$0 if it exceeds $2^{64}$.
By using the counter's remaining values, you need to send the start of the counter, too, and store it locally, you and the other side!. One can prepend this, too. Prepending is useful since it is at the beginning of the stream/file.
$$\text{nonce}\|\text{counter Value}\|\text{encrypted Message}$$
Sending the start of the counter doesn't cause any insecurity problem, otherwise, we should already have with the CTR since we all know it starts from 0.
There is, however, a danger to use in this form. During a system failure, you may lose the last value, and instead, you may use the previous values of the counter. This can result in a catastrophic failure of confidentiality since an observer will notice this and they will use the crib dragging technique. This doesn't mean that the AES will be lost, remember the CTR mode is CPA secure. The mitigation is using a new nonce, the best is exchanging a new key with ECDH and use a new nonce.
An interesting case of the danger is if both parties send a new message at the same time with the same counter, nonce, and key value. That is catastrophic! Therefore, if the messaging is in two directions with the same key, nonce, and counter continuation, it is not advisable to continue the counter where it is left. At least, generate a new nonce.
Remember, the CTR mode has many disadvantages with AES, as the lack of integrity and authentication that AES-GCM handles. And the AES-GCM is hard to use instead use ChaCha20-poly1305 where AES is not obligatory.

Updated for answers to comments;

Nonce in context of CTR means that I can use it together with one AES key as lons as a counter value is not used more than once, right? I.e. the combination of (key, nonce, counter) must not be used multiple times. Am I correct?

Yes, see it in this way.
In the CTR mode, the nonce and counter is encrypted with the AES
$$ c_i = AES(k, nonce\|counter_i).$$ Therefore under the same key any repeat of the $nonce\|counter_i$ can result in the crib-dragging attack.

What do you mean with "...more than one file."? I don't get this point. I guess the nonce doesnt have to be used (so only counter), if you are only encrypting one file using a given AES key. However, for each different file we shall use a new nonce (and start the counter from 0 again), if we do not want to establish a new AES key So in terms of the counter and –

I think I've over-read your question about sending the counter. Since the counter always starts from 0 there is no need for sending. It is only necessary if you are using it mode than one file.
The correct usage is using a new nonce for each file. If you don't establish a new key, generate a new nonce, and send it with appended. Make sure that you don't generate the nonce again.


How to implement homomorphic multiplication for Elgamal?

If $(R_1,c_1)=(g^{r_1}, A^{r_1}m_1)$ and $(R_2,c_2)=(g^{r_2},A^{r_2}m_2)$ are ciphertexts (with respect to the same public key $A$) corresponding to two messages $m_1$ and $m_2$, then
$$(R_1R_2,c_1c_2)=(g^{r_1+r_2},A^{r_1+r_2}m_1m_2)$$
is an encryption of the message $m_1m_2$ (note that the calculations are performed in $\mathbb Z/p\mathbb Z$, that is, modulo $p$).

Assuming that mpi_mulm(r, x, y, m) denotes the computation $r=xy\bmod m$ (which quick inspection of the GnuPG source code seems to confirm), this implies that (a, b) should indeed decrypt to the product of the plaintexts corresponding to (data1_a, data1_b) and (data2_a, data2_b).

This, in turn, likely means your correctness checks are flawed. If you care to post some example data and/or code, I can take a further look at the problem.


Here are some things to keep in mind

AES encrypts bytes, not characters. So you have to transform your plaintext into bytes. How are you going to do that?
In AES, a block is 128 bits. That is 16 bytes. If your plaintext is only 8 characters long, and each character is encoded as 1 byte, you are short 8 bytes. You can add some padding (a 1 followed by all 0's, something like that).
ECB mode is insecure (except maybe in some very specific use cases). That being said since you are only encrypting less than 1 block, and you are just doing it to try to learn AES, you shouldn't even really be concerned with a mode-of-encryption at this point. Just focus on AES running on a single block.

Without more information on where you are getting stuck, there isn't much more help I can give.


Vulnerabilities of AES method that uses MD5 to create the key

No, if the input key has enough entropy then using an MD5 hash will not reduce the security of AES. And AES protects the retrieval of the key from any combination of plaintext and ciphertext. MD5 can be seen as a poor man's (Key Based) Key Derivation Function or KDF which extracts (compresses) the entropy found in the input key material.

However, a lot of times MD5 is used instead of a Password Based Key Derivation Function or PBKDF (bcrypt, scrypt, PBKDF2 and the newer Argon2 variants are well known PBKDF's). If the input is a password or text then it is likely that a low amount of entropy is present. In that case it is easy to guess the input of MD5. The resulting AES key may seem secure and randomized, but the adversary may guess the input - for instance by using a dictionary attack - and perform the MD5 calculation to retrieve the AES key.

MD5 has been broken and the usage of MD5 is a red flag, often indicating that the developer hasn't got a clue about cryptography. This is true regardless if MD5 is used in a secure setting or not. The use of MD5 is often not by design, but because the developer copied another bad example of cryptography. In your case, the MD5 hash is hex encoded and then used as 256 bit key. Although using 128 bits (max) of entropy as 256 bit key doesn't break AES in practice, it does show that the developer wasn't a cryptographer himself.

If the quality is that bad, you can almost be certain that other errors have been made. In your example code, CBC mode could be used directly to achieve transport security, making padding oracle attacks a distinct possibility.

Please learn at least the basics of encoding and cryptography. Whatever you do, don't use self-made protocols like the one in your question. Try and use higher level frameworks or transport protocols such as TLS instead. You have been warned - and it is good you asked.


Why does a one-time-pad key have to be at least as long as a message?

If you using in one time pad key shorter then message, it means that some part of text will be encrypted with same part of key, two or more time.
In this case, XORing two part encrypted with same key, adversary can receive few information about plaintext. If key significantly shorter then plaintext, adversary can apply frequency analysis to discover whole message, or part of it.


Zero-knowledge proof or zero-knowledge proof of knowledge?

Since you reference my answer to a very similar question, I'm assuming you already read it, so you know what the difference between ZK and ZKPoK is at a technical level. To recall briefly, though: a standard ZK proves the existence of a witness, while ZKPoK proves that the prover actually knows the witness, which is formalized by saying that there exists an efficient extractor which can recover the witness from the code of the prover. Actually, a better full name for "zero-knowledge proof" would be "zero-knowledge proof of membership" (it proves that a word $x$ belongs to a language $L$, which is equivalent to saying that there exists a witness for the statement "$x$ belongs to $L$").
To answer your main question:

So, what is the real difference (if there is one) between ZKP and a ZKPoK? Is people using both concepts indistinguishable?

There is a clear difference at the technical level, and this translates into a clear difference in the applications. First, zero-knowledge proofs are used as components in larger constructions of cryptographic objects (there are hundreds of example, but just to name a few: verifiable encryption, maliciously secure computation, anonymous credentials, etc). In many of those applications of ZK proofs, the proof of knowledge property is actually crucial. This is for example the case in verifiable encryption and anonymous credentials - but not in maliciously secure computation, where standard zero-knowledge suffice.
To give you an intuition of when the difference matters, here is a rule of thumb:

If you just want to prove that "some property is verified" (for example: "the ciphertext you sent me contains a bit"), zero-knowledge proofs (of membership) suffice.
If you need to authenticate the prover in any way, then you need a zero-knowledge proof of knowledge.

To put it even more directly: a ZK proofs only says something about the statement ("the statement is true"). A ZK proof of knowledge is much stronger since it also says something about the prover himself: "the statement is true, and the prover knows a witness for it". This is absolutely crucial in any "authenticated" cryptographic protocol: you can say that an authorized user (for whatever definition of "authorized" in your application) is a user that knows a witness; then, sending a ZKPoK can be seen as authenticating the user, without revealing is authentication credential (which prevents stealing his identity).


Why is there an enormous difference between SAT solvers?

SAT solvers don't have a single approach -- not every approach works equally well for every problem. A SAT solver that performs well on a given problem will not necessarily work well in general.

Typically SAT solvers employ a whole bag of tricks -- deciding what heuristic to employ is one of the big differences between solvers. Different heuristics work well for different types of problems and a solver must identify traits of the problem at hand to decide which heuristic to use (unless the user specifies which heuristic to use, which one might, if one knows what to do, or for experimentation purposes).

As to why a given solver wasn't entered in the international SAT competition, you'd have to ask the creator of the solver! I'm pretty sure they could submit it if they wanted to...


AES-CTR security if S-boxes substituion is omitted?

An Sbox is a necessary condition for the security of the AES or a similar block cipher but may not be sufficient. We can list all AES operations on a high level as

SubBytes – a non-linear substitution step where each byte is replaced with another according to a lookup table.
ShiftRows – a transposition step where the last three rows of the state are shifted cyclically a certain number of steps.
MixColumns – a linear mixing operation that operates on the columns of the state, combining the four bytes in each column.
AddRoundKey

wonder if it's still relatively secure if we omit S-boxes substitution step in these circumstances

If you omit the SubBytes then the new AES cipher will be a completely linear cipher. That is a complete failure for a block cipher. When the attacker, in the simple attack, gets a known-plaintext then they will set up linear equations in total 128 for any AES. If there is no linear dependency on the equation, then they can solve AES-128 with a single-known plaintext pair.
Your design has no KPA security and in modern cryptography, we at least require CPA security.

using AES-CTR mode to make sure the same key with the same blocks will encrypt to different ciphertexts

I've got two understandings.

You use a new key for each block. This is useless.

one uses so many keys to encrypt messages
Instead of this use OTP with the key that has other problems.
one needs to run the key schedule again and again

Use one key

KPA attack can break this.

this way it seems that it's like we encrypting in a similar manner(not exactly) like one-time pad encryption since the result of encryption(that will get x-ored with plaintext) will be random.

Not really random, linearly depend on the key.
Instead in modern Cryptography what we do, we turn a PRF or PRP into a stream cipher like CTR mode. PFR can work since CTR mode doesn't require the reverse of the PRF. So that we can use one key with one key schedule for a long time. AES-CTR or ChaCha are examples of among the many. AES is believed but not proven to be a PRP. And. remember that for CTR mode one should not use a key-IV pair again.
For file encryption, it is better to use AES-GCM or ChaCha20-Poly1305 which also provides integrity and authentication. AES-GCM is faster since the hardware support like the Intel's AES-NI. The blow in my machine for AES-128 NI
openssl speed -elapsed -evp aes-128-ctr
The 'numbers' are in 1000s of bytes per second processed.
type             16 bytes     64 bytes    256 bytes   1024 bytes   8192 bytes  16384 bytes
aes-128-ctr     556160.77k  1822893.03k  3765397.08k  5115820.71k  5694253.74k  5739358.89k

If there is hardware support for ChaCha and Poly1305 it can beat AES.


A single full AES round consists of the following:

S-box application
Shift-Rows
Mixcolumns
Add round keys

2 subsequent applications of shift-rows and mixcolumns provides complete diffusion of the state and the initial round key.

What you posted is a software optimized design, which combines the first 3 steps into a table lookup, then adds round key words. Te0[] is the first lookup table, and s0 is the first word of the state. I would suggest looking at how the tables are generated.

  It's also hard to implement an even number of rounds

In that design, you simply set s0-s3 to t0-t3, and begin the next round with the correct round subkeys.


Are there any signature algorithms with pseudorandom signatures?

A valid signature $\sigma$ satisfies the very special property that $\textsf{Ver}(vk,m,\sigma)=1$, whereas a random value $\tilde \sigma$ will surely not satisfy this property. So a signature simply cannot be indistinguishable from random if $vk$ and $m$ are known. And if you consider $vk$ or $m$ to be secret, then you are leaving the standard realm of signatures. The paper mentioned above by Maeher does exactly this.


Are there ready-to-use software that can try many decryption techniques on a ciphertext, with no information?

The project Cryptool does some if not all of what you want. I have not used it extensively, but it seems quite well documented. Below from the webpage:

CrypTool 1 (CT1) was the first version of CrypTool. It was released in 1998 and allows to experiment with different cryptographic algorithms. CT1 runs under Windows and has two successors: CT2 and JCT.
CrypTool 2 (CT2) supports visual programming and execution of cascades of cryptographic procedures. CT2 contains an especially large number of cryptanalysis methods and also runs under Windows.
JCrypTool (JCT) is platform-independent and runs under Linux, Mac and Windows. One focus are post-quantum (signature) algorithms.
CrypTool-Online (CTO) was released in spring 2009. Here you can try out in a browser (on a PC or a smartphone) different algorithms.

The current version of CrypTool 1 offers numerous classic and modern cryptographic algorithms (encryption and decryption, key generation, secure passwords, authentication, secure protocols, etc.)

Visualization of several algorithms (Caesar, Enigma, RSA, Diffie-Hellman, digital signatures, AES, etc.)

Cryptanalysis of several algorithms (Vigenère, RSA, AES, etc.)

Cryptanalytical measurement methods (entropy, n-grams, autocorrelation, etc.)

Related auxiliary methods (primality tests, factorization, base64 encoding, etc.)

Number theory tutorial

Comprehensive online help


Short: CBC mode in context of TLS protocol has had security issues, and would have had to be reworked.

AES-CBC mode combined with decent HMAC can be as secure as AES-GCM. However, combining the cipher and MAC securely has been in practice found to be much easier said than done. Also, padding that is required by AES-CBC mode complicates things.

In particular, within the history of the SSL and TLS protocols, there is a long history of security vulnerabilities resulting from misuse of CBC mode or within combination of CBC and MAC, such as BEAST and Lucky13.

After the Lucky13 attack (a timing oracle caused by MAC-then-encrypt), it was thought that TLS should change ordering of the operations. Changing order of the operations would have affected the backwards compatibility with previous implementations so it was after all thought that it is more practical to switch to authenticated encryption only.

In addition to security aspects, there are some other practical benefits of AES-GCM over AES-CBC and HMAC:

On most platforms with hardware acceleration or AES-NI instructions, AES-GCM is many times faster than AES-CBC with HMAC. This is because AES-GCM is designed to be more parallelizable.
Generation of random bits is relatively slow. This is also where AES-GCM excels. Random bits are more seldomly needed than with AES-CBC (in TLS 1.1+.)
AES-GCM in average does not extend the size of the message as much as equivalent combination of AES-CBC, HMAC and padding.


Is there any existing cipher capable of scaling from a 1 bit key up to a one-time-pad?

a one time pad ia very different from other fixed key ciphers.
A one time pad is just a xor(or modular addition) It does not miz anything or extend key and even a tiny bit of key reuse is very problematic.
We have stream ciphers which take a key and produce an infinite stream of pseudo random bits.
Perhaps what you are asking for is for a cipher with arbitrary key size with guranteed perfect security for total message length less than key size and reasonable security for reasonable key sizes.
I can suggest the following construct. take the key and duplicate it by concatenation to produce naive infinite key.
Use Each key block to encrypt a counter like in CTR mode.
This by itself doesn't give perfect secrecy. You could then xor each block with the following key block. That would give  perfect secrecy when message is at least one block less than key. It might be possible to do better. But this construct will give at least the security AES CTR.


Is perfect-forward secrecy achieved with RSA?

This expands CodesInChaos's comment into an answer.

Forward Secrecy (that is, maintaining confidentiality of messages enciphered before compromise of the long term key) can be achieved in a protocol using a public-key signature scheme with a long-term public key, and a public-key encryption scheme with a per-session key; but in the case of RSA signature and encryption, that's inefficient, thus unusual.

As an example: Bob has a long-term RSA key pair $(Mpub_B,Mpriv_B)$ used for signature, with $Mpub_B$ trusted by Alice (perhaps by way of some certificate). In order for Alice to send a confidential message to Bob:

Alice

draws a 256-bit random $R$
sends $R$ to Bob

Bob

generates a new RSA key pair $(Tpub_B,Tpriv_B)$ used for encryption,
RSA-signs the (hash of the) message $R\|Tpub_B$ using $Mpriv_B$ giving signature $S$
sends $Tpub_B\|S$ to Alice

Alice

gets $Tpub_B$ and $S$
verifies that $S$ is a valid signature with respect to $Mpriv_B$ for $R\|Tpub_B$, where $R$ is from the recent first step
generates a random symmetric session key $K$
RSA-enciphers $K$ using $Tpub_B$ yielding $X$
enciphers the plaintext message $M$ using key $K$ by a symmetric algorithm (say, AES-CTR will implicit zero IV) yielding ciphertext $C$
forgets $K$
sends $X\|C$ to Bob

Bob

gets $X$ and $C$
RSA-deciphers $X$ using $Tpriv_B$ yielding $K$
forgets $Tpriv_B$
deciphers ciphertext $C$ with key $K$ yielding plaintext message $M$
forgets $K$.

$K$ allows $M$ to be large, when RSA encryption only directly allows short messages. $R$ protects against replay of an earlier $Tpub_B$.

The scheme is inefficient because the generation of a new RSA key pair is relatively expensive (and normally rare, thus not optimized for speed). That's a good reason why (EC)DH is most used in practice.

It is possible to send several messages using the same $K$, or/and reuse $(Tpub_B,Tpriv_B)$ across multiple sessions, improving performance. But Forward Secrecy triggers only when $K$ and $Tpriv_B$ are forgotten, and $R$ is no longer accepted.

Note: the scheme provides confidentiality, but not integrity or proof of origin; that can be added.


By Multi-Prime DH, I assume you mean something analogous to Multi-Prime RSA.
In Multi-Prime RSA, we pick a modulus with three (or more) prime factors; because the holder of the private key knows the factorization, he can compute (using the CRT optimization) using smaller prime modulii (and smaller exponents), yielding a moderate speed-up.
Given that is what Multi-Prime RSA, what would Multi-Prime DH be?  I assume that it is one where we pick a modulus with two (or more) prime factors.  If we know the prime factors, then we can use the CRT optimization (similar to how it works in RSA) to get a two time speed up in the DH operations (assuming two prime factors).
So, if that's the benefit, what's the downside?  Will if the attacker learns the factorization, he can use it to attack each prime factor of the modulus individually; this would yield a significant improvement in this expected effort.
So, what do we conclude?  Well, this would be a moderate optimization (factor of 2) for one side (we can't assume both sides know the factorization), at the risk that the adversary learns it (in which case it drastically reduces the security level).
Hence, I cannot recommend it.

Update: on reconsideration, I do see one scenario where it might make some sense; if you are generating ephemeral Diffie Hellman groups (which is quite unusual, however I have run into knowledgable people who have advocated for it); in that case, searching for (say) two 2048 bit primes is much simpler than searching for a single 4096 bit primes.  In addition, in that case, we wouldn't have to worry about whether $p-1$ has small factors (because the corresponding value for $\phi(n)$, which the adversary wouldn't know).  The security of the system would rely on the difficulty of factoring $n$ (as that factorization process would dominate the time taken by the discrete log problem modulo the smaller primes).  Hence, in this corner case, it would make some sense.


How do I safely anonymize/hash a unique identifier to protect privacy?

Few answers to your questions

Storing per address salt (assuming you are using it for encryption) is not same as storing the mapping with the hash. Salt could be public.
You could encrypt anything with a public key for which there is no private key yet, Checkout more on Identity based encryption techniques.

Few additional inputs for anonymization

Any anonymization technique for the MAC Address (either encryption, hashing or tokenization) could be broken through inferential attacks based on rest of the parameters that are not anonymized. Since you intend to do traffic analysis, you would need to deterministically anonymize (retain the one-one mapping either through hash or deterministic encryption), any adversary who has access to same anonymized database can identify the same patterns!
Other than inferential attacks on the logs/database, attacks based on implementation, key management, poor entropy etc also used in practice.
Micro anonymization techniques (say MAC addresses, IP Address and other field level anonymization alone ) are recommended only when any analytic s needs to be performed on the data, else it is better to encrypt the whole record.

Few references

*T. Farah, “Algorithms and tools for anonymization of the internet
traffic,” Ph.D. dissertation, SIMON FRASER UNIVERSITY, 2013

R. Pang, M. Allman, V. Paxson, and J. Lee, “The devil and packet trace
anonymization,” ACM SIGCOMM Computer Communication Review,
vol. 36, no. 1, pp. 29–38, 2006.

A. Narayanan and V. Shmatikov, “Robust de-anonymization of large
sparse datasets,” in Security and Privacy, 2008. SP 2008. IEEE Sym-
posium on. IEEE, 2008, pp. 111–125.*

Of course there are tonnes of other papers written on this topic over years.
You can read our recent paper published in IEEE- CCEM 2014
http://www.researchgate.net/publication/265598254_Network_Telemetry_Anonymization_for_Cloud_Based_Security_Analysis_-Best_Practices


I can only guess at Apple's specific reason for this. But a good reason for not allowing user-level reseeding is explained in a post by D.J. Bernstein here.

Consider two secure sources of entropy $x, y$, and a malicious source $z$:

  Generate a random $r$.
  Try computing $H(x,y,r)$.
  If $H(x,y,r)$ doesn't start with bits 0000, go back to step 1.
  Output $r$ as $z$.

For some crypto applications (i.e. DSA and ECDSA), being able to consistently predict as few as 4 bits of randomness could lead to a complete break (in the case of (EC)DSA, the recovery of the secret key).

In this case, allowing user-level reseeding is precisely what could allow this kind of attack, since it would be the last source added.

Like he says, there doesn't appear to be a good reason to be adding new entropy to the PRNG all the time, since many cryptographic applications (e.g. EdDSA) show it is perfectly possible to deterministically expand 256 bits of quality randomness into an unending stream of secure randomness. Needing to add entropy just indicates your PRNG has been compromised at some point in the past and everything you've done since should be considered utterly broken. Instead, generating high quality entropy once and keeping it safe is a much better idea.

It seems Apple has taken that approach.


Why does using a prime-order subgroup in DLP improve security?

Probably what your professor meant is that you start with any group element $\alpha$, and then use $g := \alpha^t$ as the generator for a cryptosystem such as Schnorr signatures, as long as $g$ is not itself the identity.

Why?  If $g \ne 1$, then $g$ is guaranteed to have prime order $q$, because $g^q = (\alpha^t)^q = \alpha^{tq} = \alpha^{\phi(p)} = 1$, and since $q$ is prime there are no smaller orders possible for $g$ (just start over with a different $\alpha$ if it is).

Then when you choose a public key $\beta := g^x$ for secret $x$, you're guaranteed that $\log_\alpha \beta \equiv 0 \pmod t$.  (Of course, you could have equivalently chosen $\beta := \alpha^{tx}$, but precomputing $g$ may be cheaper.)

Now since the group generated by $g$ has prime order, Pohlig–Hellman has no advantage over any other DLOG algorithms.


HMAC SHA256 for deriving session keys using random nonce

Yes, it is secure, as the KDF is secure, as the answers to the question you linked to indicates.

However, there are some things that you should keep in mind:

The result of the KDF is not validated; if the initial shared key is incorrect you will only find out once the session keys are used. This is tricky to implement if you want to use the session key for authentication (you may want to use explicit authentication rather than implicit authentication during the session).
Both parties now share a single session key, so you may need to be careful when using encrypt-then-MAC.
Both parties use share a single session key, possibly for communication in both directions, which means you can have messages replayed not just from $A$ to $B$, but also from $A$ to $B$ and then replayed back to $A$.
The scheme will not provide any forward secrecy that ephemeral Diffie-Hellman could provide.

You can e.g. use a single byte tag in addition to calculate both an encryption key and a MAC key, possibly a third one to create a value that can be exchanged to authenticate the entities.

You could include the identities $ID_A$ and $ID_B$ in the MAC calculation, e.g. $ID_A || ID_B || R_A || R_B$ for sending from $A$ to $B$.


Differences between HMAC and HKDF in a specific case

HKDF stage 1 is useful for when the SKM value is derived using some deterministic method, such as a key exchange, or from a source that may not be fully trusted. SKM may be substantially larger than the keys you want, but may have the entropy not evenly distributed. Stage 1 compacts and distributes the entropy into a key that is correctly sized for the hash function in stage 2.

If you have a source key from a true random number generator, or that has already gone through a strong KDF, you can substitute PRK with SKM, and skip the first HMAC operation.


I am not aware of any work that proposes a Gap problem related to LWE. The reason is probably that LWE is an average-case problem specifically designed for the use in crypto. However, there are the related worst-case problems, e.g. the shortest vector problem (SVP), that come with a Gap version. So, you might want to have a look at GapSVP and GapCVP.


This "dense key space means that there are more combinations of the keys in that particular space and sparse the opposite" is pretty much it.

Depending on cryptographic algorithm, key space can be less or more sparse. This depends on what primitives and possibly, what hard problems the security of the algorithm is based on.

Symmetric cryptographic algorithms use just one key and use simple algebraic or logical operations. Because these operations generally work with all possible input values, they key spaces can be (and usually are) dense. For many symmetric algorithm, each possible combination of bits of input key space is valid key (maximally dense), for some others bits less.

Public key algorithms use separate public key and private key, with specific semantics: it should be reasonably hard (likely require brute-force search of key space) to discover private key if public key is know. This kind of more complex semantics put more requirements into the operation of the algorithm. Algorithms become more complex, much slower and the key sizes they use become larger. The currently known public key algorithms are based on some problems known to be hard.

For instance, RSA is based on integer factorization problem: it is hard to factor composite number built from two prime numbers to prime numbers that make up the number. This is actually already quite close to the reason why RSA's key space is sparse. The RSA key for common 2048-bit key size is built from two 1024-bit primes. Prime number theorem describes how to estimate number of primes smaller than specify number. Math question How many all prime numbers p with length of bits of p = 1024 bits? answer can be used to estimate how sparse RSA key space is: only $\frac 1 {2ln 2^{1023}}$ out of 1024-bit bit combinations are acceptable prime numbers, and it is required to have two such primes. This means that only around every millionth of number between $2^{2047}$ and $2^{2048}$ is acceptable, which could be considered relatively sparse.

(Note: in RSA also public exponent needs to be chosen. For simplicity I've not considered full RSA key generation here, feel free to refer NIST's FIPS 186-4 standard in case you want more detail).

When considering elliptic curves, important number to consider is prime number n, one of the curve parameters. For most curves, (nearly) any number smaller than n will be acceptable private key. Thus it is easy to see that the key space is considerably denser than RSA.

Note: for EC, some of formats for the public key take twice as much bits to represent than the strength of the curve (or private key). Still, they are significantly denser than RSA of equivalent strength.

Relation with security

The sparse/dense key space has some relation with strength of the cryptographic algorithm. If only acceptable keys are prime numbers, then possible attackers may skip many of keys with little processing. Thus the strength of the algorithm can be considered to be at most the effective key space, this does not, however, remove any other algebraic reasons why there would be even better (easier) ways to attack the algorithm.

Please, tell me if I need to be clearer.


There are curve types, and equation types.

As algebraic objects, all curves can be expressed with a "Weierstraß equation". Through some changes of variables, that equation can be simplified into a "short Weierstraß format", which, for a finite field of characteristic more than 3, looks like:
$$ Y^2 = X^3 + aX + b $$
for two constants $a$ and $b$. In the case of the secp256k1 curve, the equation is:
$$ Y^2 = X^3 + 7 $$
i.e. the constants are $a = 0$ and $b = 7$.

"Montgomery curves" are curves which can also be expressed (with appropriate changes of variables, again) with another equation:
$$ bY^2 = X^3 + aX^2 + X $$
for some two other constants $a$ and $b$. When a curve can be expressed with such an equation, then it allows computing multiplications of points with the "Montgomery ladder", a mechanism which is simpler to implement, and somewhat faster, than generic code with Weierstraß equations. However, secp256k1 cannot be expressed that way. In fact, it is easily seen that a Montgomery curve necessarily contains the point $(0,0)$, which has order 2 (since its coordinate $Y$ is 0, that point, added to itself, yields the point-at-infinity). No curve with an odd order (and in particular curves whose order is a big prime, such as secp256k1) can have a point of order 2, and thus no such curve can be a Montgomery curve.

"Twisted Edwards curves" work with yet another equation, this time with a degree 4. They are more-or-less equivalent to Montgomery curves. There again, secp256k1 cannot be expressed as a twisted Edwards curve.

"Koblitz curves" (named after Neal Koblitz) are curves whose Weierstraß equation has a special format, which allows for some extra stuff. This terminology has been applied to curves in binary field (fields of characteristic 2, where addition is XOR), with equation:
$$ Y^2 + XY = X^3 + aX^2 + 1 $$
where $a$ is either $0$ or $1$. For finite fields with a large prime characteristic (e.g. integers modulo a given prime $p$), a "Koblitz curve" is a curve with equation:
$$ Y^2 = X^3 + b $$
i.e. a curve with a short Weierstraß equation with $a = 0$.

Koblitz curves have internal endomorphisms that can be leveraged to give a boost to performance (a much larger boost for binary curves). secp256k1 is a Koblitz curve.

Summary: all curves are "Weierstraß curves". For some curves, the Weierstraß equation has a special format, and they are called "Koblitz curves" (this is the case of secp256k1). For some curves, alternate equations can be used (Montgomery, twisted Edwards) with some implementation/performance benefits, but secp256k1 is not one of these curves.


Is there a cryptographic method to add noise to a plaintext instead of actually encrypting it?

You first need to consider your adversary and what are your goals for this mechanism.

This kind of mechanism appears less effective than proper cryptographic means:

having secure PRNG means that both ends of the message exchange have access to some proper cryptographic means
Adding noise means that the information exchange is less efficient: there is much more information to exchange
Even when garbage is added, some cryptanalysis techniques could be effective in retrieving the true text from the garbage.

The principled way (in my humble opinion) would be to use proper cryptographic primitives. Otherwise, you risk getting your system efficiently attacked by attacker who know the system (Kerckhoffs' principle).

Steganography

Steganography is about encoding and hiding message so that only sender and recipient should detect existence of the message. Steganographic techniques often involve adding various materials to make it easier to detect the message. I recommend studying steganographic techniques (in case you do not follow advice on just using cryptography) because there you may find partial aid for your problem.

Format preserving encryption

If the target is to make it look like it has not been encrypted, one possibility is to use format preserving encryption for encryption instead of adding garbage.


Hill Cipher Plaintext Attack: Dealing with Non-uniqueness of Matrix Inverses?

More standard is that we multiply a column with a plain text vector to get the cipher text vector so the known plain text equation (the first two pairs) yield

$$KP=C = K\begin{bmatrix}5 & 8\\17 & 3\end{bmatrix} = \begin{bmatrix}15 & 2\\16 & 5\end{bmatrix}$$ so I get $P=\begin{bmatrix}5 & 8\\17 & 3\end{bmatrix}$ which is invertible as $\det(P) = 15 - 8 \cdot 17 = 9$ and $9$ is invertible modulo $26$, with inverse $3$ as $3 \times 9 \equiv 1 \pmod{26}$.

The inverse is easily computed (as for all $2\times 2$ matrices) via

$$P^{-1} = 3 \cdot \begin{bmatrix}3 & -8\\-17 & 5\end{bmatrix} = \begin{bmatrix}9 & 2\\1 & 15\end{bmatrix}$$

which is easily checked to be the inverse. Note that the matrix in your text uses the transpose (as it left multiplies by $1 \times 2$ matrices instead, so all equations transpose) and the one from the online calculator is not an inverse at all (which becomes obvious if we do the full matrix multiplication; only the first row looks OK). So that online calculation is wrong, and Mathematica is confused (and you made a typo: 15 should be 5 I think).

Anyway, knowing $P^{-1}$, $$K = CP^{-1} = \begin{bmatrix}7 & 8\\19 & 3\end{bmatrix}$$ (your text probably gives its transpose) and this indeed checks out as $$\begin{bmatrix}7 & 8\\19 & 3\end{bmatrix} \begin{bmatrix}0 \\ 24\end{bmatrix}=\begin{bmatrix} 10 \\ 20\end{bmatrix}$$

so it maps the plain ay to ciphertext KU. The decryption matrix is
then $$K^{-1}=\begin{bmatrix}23 & 8\\19 & 19\end{bmatrix}$$ if you want to decrypt the rest (or its transpose if working by rows from the left, as before).


Is it possible to crack a LFSR encrypted file without using bruteforce?

First up: a 5 bit LFSR is horribly small, so getting the initial seed which was used is a piece of cake.

But indeed, it’ll basically boil down to a (rather quick) brute-force job where – unless that file contained purely random data – you’ld have good chances detecting the initial state (resulting in successful decryption) by just looking at the first couple of bytes.

Remember executable files, images, compressed files, and specific program files (like MS Word files) all come with specific headers. And text files can easily be detected too. UTF-8, UTF-16, etc mostly include BOMs (Byte Order Marks) and even if they don’t, they’re text – which greatly differs from random binary data. This makes "attacking" easier and can speed up things in scenarios where you’re facing multiple encrypted files each using different seeds.

That being said – never, ever, use a plain LFSR for encryption. If you really need speed, use a stream cipher (and don’t forget to use a MAC for authentication, as in "encrypt-then-MAC").


In OTP, one party generates a uniform randomly key, writes it in a roll of paper, or a book, or CD, or USB. They transmit it in person with reliable people to the other side.
The OTP keystream obviously is a long stream to long-time use, i.e. one can encrypt many messages over time without using any bits again. If a predetermined size exists to achieve the perfect secrecy, the long stream must be divided into chunks.

OTP with hiding the maximum possible length of the message;
Wikipadia defn;

One-time pads are "information-theoretically secure" in that the ciphertext provides no information about the original message to a cryptanalyst (except the maximum possible length of the message).

Let both parties agree on a maximum length of the messages in advance, say $t$.
Let the keystream is represented by $k_i$ and the message to be encrypted be $m$ with length $\ell$. Then the encryption is performed with the first $\ell$ part of the message. The remaining part is padded, here 10..0 bit padding is used since it is easy to apply even by hand.
\begin{align}
 c_i &= k_i \oplus m_i , \quad\text{for } 0\leq i < \ell\\
 c_{\ell} &= k_1 \oplus 1\\
 c_i &= k_i , \quad\quad\quad\;\; \text{for } \ell < i < t\\
\end{align}

One time pad - how is the difference in length between the plain text & the OTP handled?

Two cases we have;

The OTP keystream is shorter: in this case, one should not send reusing the keystream. Otherwise, two(or many)-time pad use occurs, and that OTP is no longer informationally secure and can be broken.

How does one attack a two-time pad (i.e. one-time pad with key reuse)?

Taking advantage of one-time pad key reuse?

One can break the messages into parts. This, however, may leak the information about the message length is longer than $t$ if the adversary observing the message traffic and two consecutive message sending is unusual.

The OTP keystream is longer: The 10.. padding as above.

10..0 padding (bit padding)
The padding simply works as adding 1 to the message then adding as many as 0s to fill the message size and possibly none. Consider only 16-bit length fixed messages;
message1 = 1010110          wiht padded 1010110100000000
message2 = 101011101100101  wiht padded 1010111011001011

The unpadding (removing the padding) starts from the end of the message, remove the trailing zeros if there are any, and then one 1.
Note that to work with the fixed messages, the length of the message must be one bit less than the fixed size. Otherwise, one cannot decide that the padded message 1010111011001011 is message2: 101011101100101 or 1010111011001011.
Other paddings
The bit padding works for bits, there are other paddings that works in the binary case;

ANSI X9.23 : Block-based padding, the remaining bytes in the last block is filled with 00 and finally the length of the padding is added.
ISO 10126 : Same as above, instead of 00s random bytes are added
PKCS#5 and PKCS#7 : can only support a message size of fewer than 256 bytes.
ISO/IEC 7816-4: Identical to the bit padding, the byte 80 is added then the remaining bytes are set to 00

Historical paddings:
In short, currently none.

Currently, the first describer is Frank Miller in 1882. the OTP is patented by Gilbert Vernam in 1919 (U.S. Patent 1,310,719) this patent doesn't include any padding.

The Venona project doesn't mention either

Shannon doesn't define either