Examining his claims about "Thundercloud":

You can use it with "any existing software, operating system, or device" (a massive amount of effort---by whom?)
Has its "own cryptographic language that is completely independent of any existing security technology" (this is a negative thing: abandoning the entire knowledge base of cryptography is incredibly stupid)
Its strength is "built within [its] proprietary design of the public and private cryptographic keys" (proprietary design is not a strength)
Those keys are 1 billion bits (125 megabytes!!!)
Those keys are "rotated randomly every 5 seconds" (a generation rate of 200 megabits per second)
Those keys are "controlled entirely by the user" (how they can generate 200 megabits per second is beyond me)
"No information is ever stored... the size of our standard encryption key is in excess of a terabyte data block" (???)
However, the above is what makes their technology so exciting---since it's transferred in the space of 200 kilobytes! (what?)
Will conform to any existing method of data storage or communication without any overhead
"Most security keys range from 128-bit to 4096-bit" (I guess the range includes both symmetric and asymmetric encryption!)
Since "most" security keys are so small, "cracking security keys in this size is fairly easy with enough computational power" (of course this is true---by definition, "enough" computational power will break computational security; that's kind of the point)
Current cryptographic technology is no longer safe: even RSA crypto was discovered to have "back doors" (yes, recently a blog post circulated showing that RSA can be backdoored if you let someone else control key generation, but that is practically a non-issue)
The system is designed from the ground-up to be impossible to breach
Every supercomputer in the world in tandem can't break it! (Neither can they break ChaCha20 with its 256-bit key, though, either......)
Adding tracking elements to Thundercloud is "technically impossible"

Needless to say, I am very skeptical. He certainly uses many technical terms, but there's very little substance. Sporting massive key sizes are a telltale sign of bullshit.

Answering your question directly: 128-bit encryption is generally considered very sufficient. Maybe it is not very sufficient: then you can pick 256-bit, whose breaking by exhaustive search is "totally out of reach of Mankind".

If exhaustive search of a 256-bit keyspace is totally out of reach of Mankind, why should you use 1 billion bit keys? Even if you built a system that could, is the massive overhead of trying to use a 1-billion-bit key really worth it? I wouldn't say so: not when 256-bit keys suffice.

Some schemes can be broken much faster than by doing an exhaustive search. For example, to get "256 bits of security," you need 15360 bits for RSA, so there's an example of needing a really, really, really large key to attain a certain security level. (Also, notice that I'm saying 15Kbits is really, really, really large. Imagine how I must feel about a gigabit!)

(Almost?) all practical cryptosystems might be broken in the near future, so we can't say that 256-bit encryption with, say, ChaCha20 gives you ironclad, unstoppable security. At the same time, though, if we somehow extended ChaCha to use a gigabit key, there's no guarantee that a new attack would necessarily be thwarted by such a large key, either. So, I don't view excessively large keys as great "insurance" against future cryptanalytic attacks.

As an update for anyone curious, today (2015 July 04) was labeled as "internet independence day" in the linked video - supposedly the launch date of "Thundercloud." The Thundercloud website (warning: autoplaying video) has not been updated, and the Thundercloud Twitter account has gone dark, so at this point, the software probably classifies as vaporware.


Since 8 is half of 16, there are alternative solutions whereby you use both upper and lower bytes but still get 8 bytes out.

XOR adjacent pairs of bytes.
Fold the MAC, XORing 1st and 9th bytes etc.

These techniques are good for when you just can't decide which byte you like best and only take a few lines of code...


Comparing two definitions of one-way function

I assume that $|x|$ in the exercise denotes the length of the bitstring $x$.

If so, the answer is simple: a polynomial time algorithm needs to complete in a number of steps bounded by a polynomial function of the length of its input.

How long is $|x|$, represented as a bitstring?  Well, it takes $k$ bits to represent a number between $2^{k-1}$ and $2^k-1$, so the length of the input $n = |x|$ is about $\log_2 n$ bits.

Thus, in order for $A$ to be a polynomial-time algorithm, $A(|x|)$ must complete in at most $p(\log_2 |x|)$ steps, where $p$ is some polynomial function.  But writing out a string containing $|x|$ bits obviously takes at least $|x| = 2^{\log_2 |x|}$ steps, which is not bounded above by any polynomial function of $\log_2 |x|$.

Essentially, the problem is that the input $|x|$ given to $A$ is "too short" compared to the expected output $x$.  The way we "fix" this issue is simply by giving $A$ an extra input $1^n$ whose length matches the length of the expected output.  That way, by "padding" the input of $A$ to be at least as long as what its output should be, we effectively allow the running time of $A$ to be a polynomial function of the length of both its input and its (expected) output, while still adhering to the standard definition of a polynomial-time algorithm.

In programming, we'd call this a hack, or perhaps a kluge.  But it's a convenient kluge, as it saves us from having to redefine "polynomial time" in crypto differently from the way it's usually defined in complexity theory, and so avoids facilitates communication between these two related fields.

Alas, the cost of this notational uniformity is that the extra $1^n$ argument sometimes appears confusing to new students in crypto — especially as some authors, perhaps out of some misplaced sense of professional embarrassment, seem rather reluctant to explain that it is, indeed, essentially just a notational hack to make the standard definition of "polynomial time" fit what we need in crypto.


Why is SHA3 prefixed with SHA despite the fact that it is structurally different from SHA2 and SHA1?

SHA3 is the name of the hash function standard, and the acronym is for 'Secure Hash Algorithm', pretty neutral one saying nothing about the structure.  The algorithm itself was originally named Keccak by the developers.  After winning the SHA3 competition, Keccak became SHA3.


Try looking at the Vigenere, or here is a complete list of keyword ciphers:
All the ciphers listed here are based on keys, but could be a little difficult to use. Some include making the keyword into a numerical sequence. By numbering each letter according to their place in the alphabet. If a letter appears twice, number them left to right.

i.e.
CAESAR =
314526


Simplified AES S-box multiplication - calculation error

Endianness strikes again! Quoting the S-AES paper

  we associate the nibble $b_0 b_1 b_2 b_3$ with the polynomial $b_0x^3+b_1x^2+b_2x+b_3$.

The nibble $0101$ maps to $b_0=0$, $b_1=1$, $b_2=0$, $b_3=1$ associated to the polynomial $x^2+1$. Its inverse modulo $x^4+x+1$ is $x^3+x+1$, associated to the nibble $1011$ that maps to$b_0=1$, $b_1=0$, $b_2=1$, $b_3=1$ rather than$b_0=1$, $b_1=1$, $b_2=0$, $b_3=1$ in the question.

Note: this comment voices puzzlement that coefficients of a polynomial are numbered differently (and in reverse order) than the corresponding powers of $x$. There are two reasons for this convention:

Technical: it is common in telecoms to both receive bits sequentially with their number initially unknown (naturally numbering them starting from 0 onward), and perform on-the-fly a Cyclic Redundancy Check by division of the polynomial associated to the message by a shorter fixed-size polynomial. Polynomial division is performed starting from the high-order coefficient of the dividend, hence the convention. Analogy: finding $d\bmod 97$ by performing Euclidean division while given integer $d$ of initially unknown magnitude as a stream of decimal digits in usual reading order.
Precedent: the block cipher DES numbered bits from left to right starting from 1 onward in inputs, output, and internal variables including S-box-index (on page marked 14 of FIPS 46-3 the numbering of bits grows as their weight in base 2 decreases, and doing otherwise would have required shuffle of the S-boxes). Time and reason largely shifted practice towards numbering from 0 in fresh cryptographic work, but the numbering direction sticks. Modern practice is to number things according to binary weight up to some size, then the other way around (the threshold is often octet for the external form of large integers as used in RSA and ECC; in FIPS 180 it is 32-bit in SHA-256, 64-bit in SHA-512, with an exception in the padding).


Factoring RSA number knowing some B-smooth numbers

You probably know the algorithms to multiply and divide numbers by hand; that's what you do. Yes, it will be painful. No, there's no other way, but I don't think you will be expected to do it in an exam (confirm that with your instructor, however).


Why do different applications of hash functions demand different properties of the hash function?

Hash + digital signature

If the hash is not collision resistant, the attacker can produce two messages having the same hash. They'll request a signature on the first and present the signature on the second, a forgery.

When second pre-image resistance is violated, this attack becomes much more severe, since now the attacker doesn't need control over both messages, they can simply use any (signature, message) pair they observed.

First pre-image resistance is not directly required, since signatures make no promise about hiding the message, But for common definitions first pre-image resistance is implied by second pre-image resistance.

IDS / virus detection

If second-pre-image resistance is violated an attacker can give their malware the same hash as an existing benign software, preventing blacklisting of the malware without the collateral damage of also blacklisting the benign software.

If collision resistance is violated an attacker can create one benign and one malicious piece of software. That's probably not a big deal, since the blacklisting will only affect the decoy software and not software somebody else developed. Still I'd strongly recommend using a collision resistant hash so you have a clear 1-to-1 mapping between hashes and executables, preventing confusion and misunderstandings.

Password hashing

Clearly the attacker must not learn anything about the password input, which is closely related to first pre-image resistance.

Lack of collision resistance only allows the attacker to construct two different but equivalent passwords which are valid for their own account. Second pre-image resistance requires knowledge of the correct password, and is thus harmless as well. The popular PBKDF2 password hash suffers from certain trivial collisions and second pre-images.

MAC

A MAC is keyed, a normal hash is not. So you need to specify how you construct a MAC from the hash. The standard choice is HMAC, which does not require collision resistance. As an example, HMAC-MD5 is still secure as MAC/PRF while the collision resistance of MD5 is utterly broken.

Key recovery is related to first pre-images, so you probably need that property. You also don't want any key independent collisions, but those are much harder to construct that plain collisions.

For a detailed description of sufficient conditions for HMAC security you can consult the HMAC proof of security.

Hash + symmetric encryption

If you want both integrity and confidentiality, we use authenticated encryption. The standard approach is first encrypting the message and then computing a MAC over the ciphertext. This is known as Encrypt-then-MAC and requires the same security properties as the MAC above.

Encrypting a hash of the message is insecure for many popular encryption algorithms, no matter how strong the hash. Don't do that, unless you really know what you're doing.


What is the recommended minimum key length for ECDSA signature

You are already well on your way if you've found keylength.com. It references the documents that the recommendations are based on, so if you need a more clear reason to go for a specific key size then you could simply dig deeper. Yes, you need to look at Elliptic Curve sizes for ECDSA.

Using different key sizes for different purposes is spot on. Kelalaka pointed to an interesting document NIST Special Publication 800-57 Part 3
Revision 1: Recommendation for Key Management
Part 3: Application-Specific Key Management Guidance.

For application for non-repudiation I would go for P-384 or P-521 though, not P-256 or P-384 as indicated in that document. These are signatures that should be made to last. I also think the recommendation to choose an RSA 2048 bit key - a key that has significantly less security than the EC P-256 counterpart in that document - is dangerous practice.

Maybe after 2030 we should worry about quantum computers. You'd better store it at a notary or another third party who can additionally sign the document with post-quantum crypto once (and if) that starts to become a requirement.

For real time authentication - the other major use case of ECDSA - you could go for P-256 or a similarly sized curve. However, if your systems can handle it, you might as well use a larger key size - if just to give you some leeway.

Beware: in the end the protocol and implementation security are endlessly more likely to be an issue than key size. Too often the key size debate is only important to the sales department and management - mainly because it is really the only thing they kind-of understand.


How to solve encryption with ASCII output

I don't think it's possible to give any specific and concrete answer without seeing the actual ciphertext (which in turn would make your question borderline off-topic here).  Nonetheless, I'll try to give a general answer below, outlining how you might be able to approach the problem.

Modern secure encryption algorithms all but invariably produce output that looks like uniformly distributed random bytes.  In particular, they do not natively output printable ASCII text.

Thus, if you see ciphertext that looks like readable ASCII, there are basically two possibilities:

after encryption, some binary-to-text encoding has been applied to it, or
it's not actually encrypted with a secure modern cipher.

In the first case, your first task will be identifying the encoding scheme.  The most common one is probably Base64, but plenty of other choices exist too.

Ideally, you'd like to find a specification describing the scheme, or the code that encodes and/or decodes it.  Failing that, the first thing you should check is the set of characters used in the encoded ciphertext.  Often, this alone may be sufficient to identify the encoding scheme.  Note that the beginning and/or the end of the data may sometimes contain extra padding or metadata tags that aren't actually encoded with the same scheme as the encrypted data itself, and which may use different characters.

You should also check how often each character occurs in the encoded ciphertext.  Binary ciphertext (which looks like random bytes) encoded with a base-conversion scheme like Base64 will typically feature all of the actual data-encoding characters with roughly equal¹ frequencies.  Characters that appear with significantly different frequencies may be padding or formatting characters, like = and newlines in Base64 or the length markers at the beginning of each line (usually M, except for the last line) in uuencoding, or they might only occur in metadata.

Alternatively, if some characters appear significantly more often than others, that may be a sign that you're actually dealing with a variable-length encoding like URL-encoding or MIME quoted-printable, or that the unencoded bytes are not uniformly distributed (which may indicate that they're not really encrypted after all).

Note that, if the (supposed) encryption is any good, then you might still be out of luck even if you do manage to decode the ASCII text back into binary.  Modern encryption schemes are generally designed according to Kerckhoff's principle, which says that a cryptosystem should remain secure even if the attacker knows everything but the key.

Even if the encryption scheme used is broken and vulnerable to attacks, with just a bunch of captured messages you're basically restricted to ciphertext-only attacks, which are the weakest kind of attacks possible — and that's assuming that you even know how the encryption scheme works, which may not be the case here.

It's also possible that the data you're trying to analyze is not properly encrypted at all, at least not in the modern sense.  It might be text encrypted with some classical cipher (i.e. something from the era before byte-based computerized ciphers like DES became commonplace) or with some weird custom home-brew encryption scheme that might be more or less (usually less) deserving of the name "encryption".

It's also possible that the data is not really encrypted at all, but merely obfuscated to make it harder to read.  The difference between obfuscation and encryption is basically Kerckhoff's principle, as mentioned above: actual encryption is designed to remain secure even if the attacker knows everything about the system except the key, whereas an obfuscation scheme may not even have a key, and simply relies on the attacker not being smart enough to figure out how it works.

One common place where obfuscation is often found is in computer games, which may "encrypt" (more properly speaking, obfuscate) their data and save files to deter players from modifying them in order to cheat.  Sometimes, such obfuscation schemes may be designed to keep the obfuscated text as printable ASCII, e.g. to reduce the chance of accidental data corruption when editing partially obfuscated files.

Of course, in practice, these categories can blend together: many classical encryption schemes that were considered reasonably secure in their time are nowadays little more than puzzles for amateur cryptographers armed with computers and modern codebreaking techniques, and similarly, many home-brew encryption schemes developed by amateurs with little if any knowledge of modern cryptography also amount to little more than mere obfuscation.  In any case, the techniques to attack all such schemes are similar:

if possible, try to analyze the code that encodes or decodes the data;
failing that, try to obtain and/or generate ciphertexts corresponding to known plaintexts with small differences, and see if the differences between the ciphertexts reveal a pattern;
also, if possible, try to submit slightly modified ciphertexts for decryption and see if there's any pattern in how changes to the ciphertext affect the plaintext;
if none of the above are possible, try to simply guess what the scheme might look like, based on resemblance to other common and/or standard encoding or obfuscation schemes.

You might also find the answers to these related questions useful:

Is it generally possible to employ brute force methods when the encryption scheme is not known? Why or why not?
Possible ways to crack simple hand ciphers

(Yes, the top answers to both are mine, because I was lazy and only looked through my own contributions.  If you can think of other related earlier questions with good answer, feel free to suggest them in the comments.)

Also, here's a practical example of ciphertext-only reverse engineering of (double) binary-to-ASCII encoded data that I posted to SO a while ago.

1) As a rule of thumb, two character counts may be considered "roughly equal" if their difference is no more than a couple of times the square root of their average.  This is because, for a string of independently chosen random characters, the number of times each character occurs in the string approximately follows a Poisson distribution, which has a standard deviation equal to the square root of its mean.


Discrete Logarithm problem with selected order

If the attacker can pick, say, an order $p=3$, then it's easy.
However, if the attacker is constrained to pick a large order, that may not be enough.  If the attacker is able to select a smooth group order, that is, an order $p$ which is the product of a multiset of small primes, then the discrete log problem is easy (using the Pohlig-Hellman algorithm).
Hence, unless the flexibility that the attacker is granted is more constrained than the question indicates, the answer is "no, the discrete log problem may be easy"


Take a look at this chapter (Introduction to post-quantum cryptography by Daniel J. Bernstein). It gives an excellent overview of what is known. (Bottom line, Grover's is the best known today and so this can be thwarted by taking 256 bit keys.)


What makes an algorithm "fast in software" vs. "fast in hardware"?

"In software" means programming the cipher on a multifunctional processor or smart chip. The normal instruction set is used to build the algorithm, and not available operations have to be emulated.
"In hardware" means building the cipher in real hardware, like on a Field-programmable gate array (FPGA) or Application-specific integrated circuit (ASIC).
(Nearly?) all ciphers are faster in hardware than in software, but we say "fast in software" if an algorithm is not much slower in software than in hardware.

Some operations can be done fast in software, some other are hard to emulate for the typical x86 (or x86-64) processor. A few examples:

Bit shifting (with a constant length) is one of the fastest things in hardware. You can just connect the outputs with the appropiate inputs on the silicon, no transistors needed. Only the speed of the input / output and the current limits this kind of operation, while in software you have to "waste" an entire CPU cycle.
Additions are pretty fast in software, because that's what processors are made for. Higher integer performance was the main goal of CPU optimizations in the past and is even now of high priority. Additionally it's pretty costly to implement big bit size adder because of the carry over. All this makes addition preferable for software implementation.
Permutations are slow in software, but very fast in hardware. It's the same like bit shifting in hardware, but slow in software because there's no specialized operation for permutations. It has to be emulated, and that's pretty costly. Here's a document about fast software permutation instructions. With this a CPU could be much faster at this task.

Other important factors are as example Pipelining. This can enhance the performance on hardware (and limited in software) and reduce the needed area of the chip. All this factors lead to the fact that some ciphers are "faster in hardware" than "in software" or the other way round.


Difference between encrypting something and hashing something

(I am new to cryptography, so hopefully I wouldn't say anything wrong. The following I hope should help give an idea of differences).

In general you always have a plaintext or something that you want to keep secret. This might be a message or a file or a password.

Encrypting: encryption transforms the plaintext into something that cannot be understood - something that doesn't have any meaning. Something unintelligible. You encrypt the message/plaintext by using an algorithm and a key. The output (the ciphertext) always depends on the key. The essential thing about encryption is that you can always recover the plaintext (if you know the key/password), and given a key/password you have only one plaintext. So you can think of encryption/decryption as a way to move back and forward between you plaintext and your cipher text (using a key).
Uses: Encryption is good if you say have a message to send to someone. You encrypt the message with a key and the recipient decrypts with the same (or maybe even a different) key to get back the original message.

Hashing: hashing turns something (usually a key or a password) into a (usually fixed length) string of characters. For example your hashing algorithm might always produce a string that is 8 bytes long. As with encryption you transform something intelligible into something unintelligible. One might call the product of the hashing the hash codes of the hash sums. One difference is that hashing two different messages might produce the same hash values. So you cannot decrypt something that you have hashed. But even though you can't decrypt a hashed value, it is (or it should) in general hard to make two messages that have the same hash value. Another difference is that hashing doesn't require a key.
Uses: One use of hashing is if you want to send someone a file. But you are afraid that someone else might intercept the file and change it. So a way that the recipient can make sure that it is the right file is if you post the hash value publicly. That way the recipient can compute the hash value of the file received and check that it matches the hash value.


What is the best way to sign a message using RSA?

Option A signs the public key rather than the message. As the goal is to authenticate the message, the signature over the public key is useless for this purpose.

Option B signs the message. It however has the disadvantage that it is possible for an adversary to guess the message and verify the correctness of the guess. As such, it doesn't provide full confidentiality. It may also be vulnerable against oracle attacks unless a IND_CCA2 secure cipher is used; it could be that the receiver leaks information when trying to decrypt unauthenticated ciphertext.

Option C signs the encrypted ciphertext. It doesn't provide any authenticity of the message for email encryption because somebody can simply strip off and replace the signature. It would only provide authenticity if Bob only expects signatures of Alice, and disregards any other public keys that can be used to verify the message. This is however commonly not the case for person-to-person mail encryption.

Option D is clearly some mumbo jumbo to have a fourth option. As the operation $K_{A}^{+1}(M)$ doesn't make any kind of sense even with regards to the notation, it is probably best to ignore it.

Option B is an encrypt-and-sign scheme, option C is an encrypt-then-sign scheme.

Generally we use a (missing) sign-then-encrypt scheme where we send $E_{K_B}(M, \text{Sign}_{K_{A}^{-1}}(M))$. Obviously sign-then-encrypt should be used with care as well; it does require a IND_CCA2 secure cipher just like option B. Note that I've left out some kind of encoding function to merge the message with the signature.

Now that you know the terms you can look up Q/A and discussions such as the one here. Note that we often need to include additional information in the scheme for it to be secure in a practical sense; protocol design is however a separate topic.

EDIT: Come to think of it, it is also possible to replace the signature for option B, so that would make option C marginally better.


Does revealing shares of the result reveals shares of the inputs?

It depends on how you make shares out of a polynomial. Consider for example Shamir secret sharing, using which a party can share a secret $s \in F$ (where $F$ is a finite field) with $n$ parties by doing the following:

Construct a polynomial $f(x) = s + a_1x+a_2x^2+\dots + a_nx^t$, for some $t$, where $a_i \in_R F$ for all $1 \leq i \leq n$.
Send the value of $f(i)$ to party $P_i$ for all $1 \leq i \leq n$.

The above mentioned secret sharing scheme is linear and it further allows us to perform multiplication of shared values as well. When using Shamir secret sharing for evaluating an arithmetic circuit securely, we release the shares of the final output in public, from which the final output can be constructed. The proof for the fact as to why the shares donot leak anything more than the described output can be found in the Chapter 3 of the textbook titled "Secure Multiparty Computation and Secret Sharing".


Authentication impossible without pre-shared public key

You dont need the public key/certificate to be present in the browser. You just need to devise a method to ensure the public key/certificate which is presented by the peer is valid. In a Web Browser scenario this is typically done by a number of known CAs which sign those certificates. But you can also ask the user to authenticate the certificate by a fingerprint or by registering it at a central directory you trust.

You can also what is called "Trust-on-First-Use" which is basically "install this cert". This has the one-time risk of a person in the middle attack. It is how SSH is used most of the time today.

You do not even need a known/verified certificate but can use instead anonymous key agreement. This has of course the big problem that each time this key exchange is done a person in the middle can spoof the server. TLS has aDH ciphers for this.

And finally you can use TLS based on a shared password as well. It depends if both parties know each other and can actually verify each other out of band or not.

If you do not have a central directory authority the most common method is to use a trust on first use setup with the additional option to manually verify the peers (this is for example also used in Whats App in addition to the weak identity proof with phone number).


Indeterminate Message Validity as a Noise Source in High Volume Channels

Please take this with all respect and decency you deserve, but you're absolutely wasting your time with this elaborate scheme :-) What you propose is a protection system for true OTP transmissions. The OTP doesn't need protection.  We know this and I'm not going to further champion its virtues.  But I will put some numbers to my reasoning:-

Assume what I call computer Morse code (characters A-Z, 0-9, space, period).  That's a 38 character alphabet.
Also assume for comparison a 256 bit key for something like AES.
There is an answer here as to how much energy it would take to simply cycle through a 256 bit counter from a thermodynamics perspective. The answer quotes Bruce Schneier's back of the envelope assessment at needing  all the energy from a super nova (and more), which is quite a lot of batteries.
Using our computer Morse alphabet, 256 bits of entropy is equivalent to 49 characters.  That's a short message.
A more likely Twitter length message (160 characters) is 840 bits of entropy, or 2^840 permutations.
That would take many more super novae + even more batteries and it proves that it's impossible to brute force a Twitter length OTP message.
This is all based on having a good OTP generated with a good true random number generator made from physical components like cogs, diodes and wires.  Absolutely no cheating and using /dev/random and certainly not CryptGenRandom.

So don't bother making the NSA's life more difficult that it already is.

Where your system has merit though is channel masking.  The high and perhaps constant level of comms traffic obscures the time and number of real messages. This is standard counter intelligence against traffic analysis and chatter measurement as part of military communications intelligence.  Heavy stuff.

For no practical reason, this is a very recent super nova, lovingly named G1.9+0.3:-

and is more likely to reoccur than breaking a good OTP. Instead focus your effort on generating the OTP correctly.


Why is garbled circuit a randomized encoding?

First of all, having a precise definition of garbled circuit is a bit cumbersome - if you want to see a clear and nice (formal) definition, I suggest looking at page 2 of this article.

The purpose of a randomized encoding is to create, from a function $f$ and an input $x$, an encoding $\phantom{i}\hat{f}(x;r)$ such that:

Correctness: there is an algorithm $D$ such that, for any input $x$ and any random coin $r$, $D(\hat{f}(x;r)) = f(x)$
Security: $\phantom{i}\hat{f}(x;r)$ reveals nothing about $x$ except $f(x)$. Formally, there is a simulator that, given only $f(x)$, can sample from a distribution indistinguishable from $$\{\phantom{i}\hat{f}(x;r) | r \text{ random}\}$$

The level of indistinguishability (perfect, statistical, or computational) gives the corresponding flavor of the randomized encoding.

For a randomized encoding to be be useful, computing $\phantom{i}\hat{f}(x;r)$ must be simpler than directly computing $f(x)$ for a definition of "simpler" that depends on the application in mind. An example: suppose you want someone to learn $xy$ and nothing more, but you cannot directly compute $xy$ because all you know are, say, additively homomorphic encryptions of $x$ and $y$ - so you can compute any function of the form $ax+by+c$, but not $xy$. Here, you can pick two random coins $(r_x,r_y)$ and send (encryptions of) $(u,v,w) = (x+r_x,y+r_y, xr_y+yr_x+r_xr_y)$: your opponent (who has the secret key of the scheme) can compute $xy = uv-w$, and one can easily prove that he can only learn $xy$.

So, why are garbled circuits randomized encodings? Well, given a function $f$ represented by a circuit $C$, the randomized encoding of $C(x)$ is just Garble$(x;r) = (C',K)$ ($K$ is the list of keys for every input bit, $r$ is a random coin) together with Encode$(K,x) = E$: given $(E,C')$, one can recover $C(x)$ by evaluating the garbling $C'$ with the keys $E$ associated to $x$ (this is the correctness of the encoding), and it reveals nothing more than $C(x)$ (this is the security of the randomized encoding). Therefore, this does indeed correspond to a computational randomized encoding of a function.

But why is it useful? Because with known constructions of garbled circuits, computing $(C',E)$ is simpler than computing $C(x)$ in the following sense:

Garble$(C;r)$ can be computed by a constant depth circuit, independently of the depth of the function computed by $C$. Indeed, one can garble all the gates in parallel. This has many applications in cryptography and led to a fruitful line of work that started with the article Cryptography in $NC_0$.
Garbling the circuit and encoding the input are two separated algorithm, and Encode$(x,K)$ is usually a very simple algorithm (a table lookup).


Coppersmith's method for small public exponent

If you only know the ciphertext and the public key, you should not be able to do anything, since RSA is intended to  be used that way.

However, here are some leads which may help you to recover your message (since $e$ is low):

If the same message (with the same padding!) have been sent to $e$ different people (hence encrypted with $e$ different public key), you can recover the message using the Chinese Remainder Theroem. This is known as Hastad's broadcast attack.
If the message is short and not padded, you may be able to recover the message simply by taking the $e^{th}$ root of the ciphertext. Note that it can only work if $m^e < n$.

In a more general way, I invite you to take a look at Dan Boneh's "Twenty Years of Attacks on the RSA Cryptosystem" namely the section about low public exponent.


Hashing items of different Bytes but same length would enable a timing attack?

It is a bad idea to use any user information of host information to generate a salt. Salt should be random.

Use password stretching. Depending on tools available to you considers bcrypt, scrypt, argon2. Then no matter if user exists or not the password stretching can take (depending configuration) substantial time. It will be safe against timing attacks.

Since the stretched password hash will not depend on user ID,  your users will be able to change their IDs (whatever you use as ID - email, user name or anything else) as often as they want. When user ID changes, it will not bve necessary to recalculate the password hash.


How should I interpret this note on diffusion of the internal state of a PRNG?

I see no issue here about bit diffusion; if $\textit{MIX-i}$ has a problem, so does $\textit{MIX}$.

The reason is simple, $\textit{MIX-i}$ is precisely $\textit{MIX}$, but backwards.  Hence, if $\textit{MIX}$ starting at initial state $S_0$ and ending at final state $S_n$, would generate the output:

$B_0, B_1, B_2, ..., B_{n-2}, B_{n-1}, B_n$

then $\textit{MIX-i}$, starting at initial state $S_n$, would generate the output:

$B_n, B_{n-1}, B_{n-2}, ..., B_2, B_1, B_0$

If the sequence $B_n, B_{n-1}, B_{n-2}, ..., B_2, B_1, B_0$ has a problem (either against a statistical analysis, or against a cryptographical attack), then $B_0, B_1, B_2, ..., B_{n-2}, B_{n-1}, B_n$ should have the same problem.

Now, is $\textit{MIX}$ (or $\textit{MIX-i}$) a good random number generator – either statistically, or as a cryptographically secure random number generator?  Well, I don't know if it's a good statistical rng (it does have an obvious state recovery attack that takes $O(2^{64})$ time, hence I believe it is disqualified from being considered a CSRNG); however the fact that hidden bits from $A, C, D$ are not mixed in as well as they may be are not an automatic disqualification.


How much would removing enigmas biggest flaw improve it?

with enigmas flaws removed, how comparable to modern algorithms would it's security be?

With the specific change you specified, it would still (by modern standards) be considered "broken".

Here is how you can perform a distinguishing attack, and do a partial key recovery (recover the first two rotor settings with a good probability of recovering the third rotor setting) with about 400 characters of known plaintext.

I'll be assuming a 26 character rotor, however the attack scales to other sizes.

Here's how to recover the first rotor setting (and if you do recover a setting that works, that's a distinguishing attack):

In the encryption operation, the note that:

The plaintext character is sent through the first rotor: $A := R_i({Pt})$
The ciphertext character is sent through the first rotor after stepping it one position: $B = R_{i+1}(Ct)$
The mapped plaintext $A$ is different than the mapped ciphertext $B$

This holds because the internal rotors and the reflector do not step during the operation, and hence will never map a character to itself.

Note that this might not be true if the second rotor is stepped during the encryption operation; however that will occur only once every 13 character encryptions.

So, if we take a guess at an initial rotor setting, we can determine how all the plaintext and ciphertext characters are mapped.  Then, if we find two instances where the plaintext and ciphertext characters are mapped to identical $A, B$ values (and those locations are not multiples of 13 apart), we know that that initial rotor setting is impossible.

After 400 characters, the probability that an incorrect rotor setting will show as possible is approximately $2^{-13}$; as there are significantly fewer than $2^{13}$ possible settings for the first rotor, then with high likelihood, only the correct setting will remain as possible (and if no settings remain, then this isn't modified Enigma).

Now, that we've recovered the first rotor setting (and position), we can peel off the first rotor operation (by applying the now-know first rotor operation to the known plaintext/ciphertext), and use a similar attack to recover the second rotor (which is actually easier; we have a lot more information per rotor step).  And, if the third rotor steps during the 400 character encryption but not the fourth (probability >50%), then we can recover the third rotor (using the same trick)

Bottom line: this would be considered (by modern standards) totally broken


how does a time-memory trade off attack work?

Time trade off, or in your case, time-memory tradeoff, works by having massive "rainbow tables" that show you ALL hashes in a hashing algorithm (probably MD5, or other low security algorithm). A "Rainbow Table" saves you time and processor power, rather than having a hash cracker eat up your ROM, but are probably many gigabytes large. The trade-off then becomes size vs. time & power. If this doesn't satisfy you, or this seems like it's missing something, there is PLENTY of research being done on hash cracking, and even a youtube channel called "Computerphile" that has a better explanation on this than me.


This is a condensed explanation, but should be enough to get you to the result.

First you must generate the intermediate data.

For each boolean function and bitmask, you run through a loop, $i$ from 0 to 255:

testval = sbox(i) XOR sbox(i XOR mask)
bitval = testval AND 1
results(mask,0) += bitval

The bitval is the low bit of the test result on the s-box input $i$. The results is the sum of all the bitvals for the given mask and boolean function, in this case boolean function 0.

For the other boolean functions, you must rightshift the test value, as you are testing the other bits rather than the low bit:

divisor = 2^booleanfunction
testval = sbox(i) XOR sbox(i XOR mask)
bitval = (testval / divisor) AND 1
results(mask,booleanfunction) += bitval

The loop for the single bit mask are from 0 to 7, as that is how many there are for an s-box with 8 input bits, the mask is $2^{loop}$. The loop for the boolean function is from 0 to 7, as that is how many there are for an s-box with 8 output bits. Here is an optimized loop to calculate the results

m = 0 to 7      [loop for masks]
i = 0 to 255    [s-box input entries]
n = 0 to 7      [boolean functions]

for m:
  mask = 2^m
  for i:
    testval = sbox(i) XOR sbox(i XOR mask)
    for n:
      divisor = 2^n
      bitval = (testval / divisor) AND 1
      results(m,n) += bitval

Now that you have the results calculated, you simply display them as a matrix:

             boolean function
       7   6   5   4   3   2   1   0
   0  128 116 124 116 144 116 132 132
   1  136 128 116 124 128 144 124 120
m  2  128 136 128 144 120 128 132 132
a  3  140 128 136 128 116 120 136 136
s  4  136 140 128 128 132 116 128 116
k  5  136 136 140 120 120 132 132 116
   6  124 136 136 120 132 120 136 136
   7  132 124 136 124 136 132 144 132

This is for SAC with a single bit mask (1st order SAC) for other orders, the bitmask calculation is different, and there will be more masks, 2nd order has 28 masks for example.


Is there an English translation of Vigeneré's "Traicté des Chiffres"?

There is neither a „modern” French edition, nor an English translation, contemporary or modern. Time to learn some contemporary French. What's the use of attempting cryptoanalysis if you can't manage the historic version of a quite common language, in this case early modern French? Your approach works like the Traicté on its own linguistic grounds, not on yours.


The output of experiments Real and Ideal in simulation-based security proof

The question is rather abstract, so the answer will be rather abstract too.
In general in simulation-based proofs you compare two worlds (ideal and real).
Consider some protocol $\pi$ between two or more parties.

In the real world, the adversary corrupts some fraction of the parties and executes $\pi$ with the remaining honest parties that have some secret information.
The honest parties follow the protocol description, whereas the corrupted parties may behave arbitrarily.

In the ideal world, the corrupted parties interact with a simulator that does not have the secret information of the honest parties, but still tries to somehow simulate the messages that the corrupted parties expect.
To successfully accomplish this task, the simulator is usually given some sort of auxiliary information.

Now imagine that at the end of any interaction the adversary outputs a bit, which is its guess of whether it was in the real world or in the ideal world.
If the adversary cannot do much better than guessing in which world it was, then it will output bit $b$ with roughly the same probability in both worlds.
This in turn means that it cannot tell the difference between talking to real parties holding some secret information and a simulator that does not know the secret information, which in turn means that "nothing" about the secret information was leaked from the protocol execution in which the adversary participated.
Usually "nothing" is a bit much to ask for and thus we at least hope that the adversary learns nothing beyond what we gave the simulator as auxiliary information.

You can find a great introduction to simulation-based proofs here.
The concrete formulation, where the adversary outputs a single bit, which represents its guess regarding which world it was in, is common to security definitions in the Universal Composability model


Pari's "chinese" function (as in Chinese Remainder Theorem) does the solution for you, for two congruences. You can fold in more congruences via induction.

? chinese(Mod(42,91), Mod(11, 37))
%1 = Mod(3045, 3367)

The previous example solves for $x \equiv 42 \pmod{91}$ and $x \equiv 11 \pmod{37}$, which is unique modulo $91 \cdot 37 = 3367$. You can use "raise" to promote a Mod object to the integers.


Understanding the HAIFA (hash iterative framework) structure

HAsh Iterative FrAmework (HAIFA) proposed by Biham and Dunkelman, in 2005-2007. The main idea of the work is to fix the flaws of  Merkle and Damgård (MD) construction. Interestingly, Invented by Ralph Merkle and Ivan Damgård working independently and presented in the main Cryptography Conference.

R. Merkle. A certified digital signature, CRYPTO '89.
I. Damgård. A design principle for hash functions, CRYPTO '89.

Flaws in MD constructions are found even the underlying compression function is secure. In MD, the iteration maintains the collision resistance of the compression function proved by both Merkle and Damgård. Over time, it is shown that it not enough;
MD construction problems

fix-point of the compression function can be used in the second-pre-image attack by Dean.
Kelsey, and Schneier same as above with the fixed point assumption is removed in Second Preimages on $n$-bit Hash Functions for Much Less than $2^n$ Work
Chosen target pre-image attack by Kelsey, or known as Herding attack' Herding Hash Functions and the Nostradamus Attack
The well-known length extension attack.
Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions by Joux. Joux showed that finding multiple messages that have the same hash value is almost the same as finding a single collision on iterated hash functions.

HAIFA is designed with these goals

simplicity: this is important since the simple design a better understanding to analyze.
maintaining the collision resistance of the compressions function
increasing the security of iterative hash
functions against (second) pre-image attacks, and
the prevention of easy-to-use fix-points of the compression function. HAIFA also supports variable hash size.

Previous MD modifications
There are patches for MD before HAIFA, and actually HAFAI can use all.

Randomized hashing scheme: They reduced the collision-resistant requirement of the compression function. They randomized the inputs of the compression function so that, the collision of the compression function can be masked.

Enveloped MD construction: This method preserves the collision resistance, the pseudorandom and the pseudorandom family properties of the compression function. This construction can be very useful like the case of a hash function is designed for MACs, since the pseudorandom properties of the compression function is preserved.

Wide pipe: This method uses a larger internal state than the output size. This construction results in finding internal collisions as hard as finding the pre-image of the hash function itself.

HAIFA design
The compression function of HAIFA is designed as
$$C:\{0,1\}^{m_c} \times \{0,1\}^n \times \{0,1\}^b \times \{0,1\}^s  \to \{0,1\}^{m_c}$$ or
$$h_i = C(h_{i-1}, M_i, \#bits, salt)$$ $\#bits$ is the number of bits hashed, $h_0 = IV$, and $salt$ is the usual salt value.

The padding scheme
It is bit padding, add 1 then and as many as 0 then the length encoded in $t$ bits, then the digest size encoded in $r$ bits. Therefore the added 0 is $ \equiv n - (t+r-1) \mod n$
Security

Collision resistance: Similarly to MD, the have proved that if the underlying compression function is collision resistance the HAIFA construction, too.

Fixed point countermeasure: the inclusion of the number of bits hashed so far prevents the fix-ed point attacks.

Randomized hashing is achieved by the salt.

Multi-collision attack: The attack still works, however, the inclusion of the salt prevents pre-computation

Hearding attack: The precomputation is infeasible if the salt is unknown.

Hash Algorithm Based on HAIFA

BLAKE, BLAKE2 uses a simple desing to elimiate the Length extension attack.
SHAvite-3
ECHO
LAKE
Sarmal
SWIFFTX
HNF-256

The first three are in the second round of the SHA-3 competition of NIST.


Calculate new hash from old hash + appended string

What you are looking for is called a length extension attack. A length extension attack is, when an attacker given and $h = H(m)$ is capable to compute $h' = H(m\|m')$ for some $m'$ without knowing $m$.

Hash functions constructed using the Merkle-Damgård construction are generally susceptible to length extension attacks and SHA512 is not an exception.

The reason is the structure of a Merkle-Damgård hash function, which operates by iterating a compression function $$f : \{0,1\}^{\ell'} \times \{0,1\}^\ell \to \{0,1\}^{\ell'}$$
that maps an $\ell'$ bit intermediate hash-value and an $\ell$ bit message block to a new $\ell'$ bit intermediate hash-value. (For SHA-512, $\ell=1024$ and $\ell'=512$).
Essentially it takes a message $m$ that must be a multiple of the block size $\ell$, splits it into blocks $m_1,\dots m_L$ (for a total message length of $|m|=L\cdot\ell$), sets $$h_0 := IV \in \{0,1\}^{\ell'}$$
and for $1\leq i\leq L$ computes $$h_i := f(h_{i-1},m_i).$$
Finally it outputs $h_L$.

From this description you can easily infer that given $h=h_L$ you can choose a new block $m'$ and compute $h_{i+1} = f(h,m') = H(m\|m')$ giving you a length extension attack.

However, as most things it's not quite that simple. I said above, that $| m|$ needs to be a multiple of the block size. This is in general not the case, so some padding needs to take place to bring the message length up to the next multiple of the block length. For SHA-512 the padding works like this:

Let $m$ be a message of length $|m|=b$ bits.
Then we append a single $1$ bit and $k$ $0$ bits, where $k$ is the smallest number, such that $b+1+k+128$ is a multiple of $1024$. Finally $b$ encoded as a $128$ bit integer is appended. This padded message is then fed into the construction outlined above.

What does this mean for a length extension attack? Mainly two things: First, in addition to $h_i$, we also need to know the length $|m|$ of the original message to compute the new padding. Second, we will not be able to freely choose $m'$.

If we run the length extension attack we will end up with a hash for the message $$m\|1\underbrace{0\dots0}_k\|b\|m',$$ which depending on context may or may not be sufficient for whatever an attacker is trying to do.


which exponent to be used for RSA e =3 or 65537 for RSASSAPSS signature verification

Use the value of public exponent $e$ that came with the public key, here $e=3$ according to the question. Otherwise, signatures won't check.

Common RSA public exponents include $65537$ and $3$, and more generally the Fermat primes $2^{(2^k)}+1$ with $0\le k\le4$; and $37$ (used by Putty).

$e=3$ leads to the fastest RSA public key operation, because we can compute $x^3\bmod n$ as $((x\times x\bmod n)\times x\bmod n)$; more generally, when using $e=2^{(2^k)}+1$, the public key operation $x\to x^e\bmod n$ requires $2^k$ modular squarings and one modular multiplication.

Using $e=3$ is believed safe when used with good padding techniques (including signature per RSASSA-PSS as in the question), but $e=65537$ is recommended by many authorities and can sometime act as an effective patch (for example, it has the potential to save implementations of PKCS#1 v1.5 decryption from disaster by side channel leakage thru error codes or timing attacks; and faulty implementations of PKCS#1 v1.5 signature verification that incorrectly validate the padding).


ZKIP for Paillier public key correctness

First, the awkwardness of ZKPs and distributed key generation in Paillier is the reason many protocols use exponential Elgamal for protocols like mental poker. It is additively homomorphic but has the drawback on only being able to decrypt a small message space. In your case, since users are opening their encryptions, it seems suitable. The whole protocol could be run under a common key that is shared among the users (in a distributed or threshold manner).

I don't know of a ZKP for well-formed keys in Paillier. This is just an initial thought. In the following Paillier variant (from Encyclopedia of Cryptography and Security):

It should suffice to prove $n$ is a well-formed RSA number (e.g., CM99) and prove knowledge of $\lambda$ given $y=(g^n)^\lambda$ for $y=1$ (e.g., knowledge of discrete logarithm)?


What alphanumeric string length can be used to guarantee no hash collisions from CRC-64?

If you have 62 chars you can transform 62 letters ($10+26+26$) in 6 bit number (approx). CRC is guaranteed to be unique mapping (Injective function) as long as input is shorter than output  – you can have at most 10 letters, but not 11 since $62^{10} < 2^{64} < 62^{11}$.

It same goes whit most other hash functions. Lets say that you have hash function that takes only 64 bits and makes 64 bit output and is bijective (like a symmetric cypher). That mean you will not have collision as long as your input is shorter than 64 bits.

If you have mappings from all 64 bit inputs you are 100% sure that each new input will produce collision (because there is no value that is unused)


Mixing algorithms for password hashing good or bad?

Does this look like it's done by someone who knows what they're doing or is it just a case of someone throwing all the algorithms they find together and hoping it's a good solution?

This is obviously someone who threw something together without knowing what they were doing. If they knew what they were doing, they wouldn't roll their own algorithm (“Dave, you are not a cryptographer. Stop it.”), they'd use one of the standard algorithms such as PBDKF2, bcrypt or scrypt.

PBKDF2 has been in the standard library in PHP since 5.5.0, and there are plenty of open source implementations that are slightly slower but work in earlier versions. It can be debated whether PBKDF2 is the best choice, but it's a reasonable one. There is no excuse to rolling your own.

  The use of crc32 looks like a terrible idea to me

Indeed, the way crc32 is used makes it really terrible. If you replace crc32 by md5, the algorithm is merely bad, because it isn't slow. A password hashing algorithm must be slow to resist brute force guessing attempts. PBKDF2 achieves this by doing something similar to the algorithm you're looking at — repeated hashing — but 1. the hashes are assembled together sensibly and 2. it typically runs for hundreds of thousands of iterations, not a just a couple.

The way the algorithm uses CRC32 is a devastating flaw. It makes it easy to find a password by brute force. There's no guessing involved: a working password can be found in just a few minutes of computer time. This may not be the password that the user chose, but it would be a password that produces the same hash.

The critical issue is that CRC32 only has $2^{32}$ possible values, which is about 4 billion. A CPU performs that many operations in just a few seconds. If you look at the structure of the hash, it's F(CRC32(G(password)), salt). The exact structure of F and G doesn't matter, the issue is that the password only influences what goes into the CRC32 function. It only takes a few minutes to calculate G(P) for a few billion values of P. Some of them will result in CRC32 collisions, but so it'll take more than $2^{32}$ values of P to reach all $2^{32}$ possible values of CRC32(G(P)), but not a lot more. So if you calculate F(CRC32(G(P)), salt) for a little more than 4 billion values of P, one of them will be the target hash.

This doesn't necessarily give you the original password, just one that works on the system that uses this hashing algorithm. If you wanted to find the original password (because users often reuse their passwords, and other sites probably don't use such a broken hashing algorithm), you'd have to work a little harder. But not much harder. When you enumerated all the CRC32 values, you found G(password). The value CRC32(G(P)) that makes the hash pass is equal to CRC32(G(password)) where password is the original password, because the function F doesn't have any “random” collision (in fact, it has no known collision, although MD5 and SHA-1 individually do, and even for those hashes individually, collisions require crafting the two source values, not just one and then looking for a collision). Take a table of MD5 values of common passwords and filter the ones that have the target CRC32; unless the password is too rare to be in the table (and there are techniques to make huge tables), you'll find the original password.

Using multiple hash functions in case a weakness is found in one of them is not a bad idea, but it needs to be done right. PBKDF2 uses the password at each iteration. If the algorithm in this question was modified to use the password in the final SHA-1 and MD5 steps, it would drop back from being extremely bad to merely bad. And although using multiple hash functions is not a bad idea, it is by no means required; in fact, it's probably not worth the added complexity (i.e. the added risk of getting it wrong).


AES 256 Encryption - Is it really easy to decrypt if you have the key?

I assume you follow Kerckhoffs' principle so the attacker knows the padding scheme and derivation function so the answer is yes, it only takes a few seconds to decrypt and anyone can do it.

If he doesn't know these things, he can find them by trial and error (assuming he can get his hands on a valid ciphertext).

The IV can be sent in the clear so making it depend on the key reveals some information on the key. It should also be unique for each session so I'm a bit worried about it. It should be OK if the KDF you're using is non-deterministic, which implies it uses its own IV so the problem remains. See this question for more on IVs.

Edit based on comments:
The cracking procedure is the following:
$a$ is the number of all modern ciphers. Let's set this to 100. $m$ is the number of modes per cipher, set it to 6. $k=100$ is the number of key derivation functions, $p=100$ are the padding schemes. The values are arbitrary. So we have $(p*k*m*a*c)/n = 6*10^6$ which equals to approx. 69 days with $c=1$ second and $n=1$ processor.

Your adversary will solve the problem in $69/2=34.5$ days. Not as practical but definitely feasible, especially if you throw extra processors at it. This solution is completly brute-force, it makes no attempt at distinguishing and pre-eliminating ciphers.

Since non-indistinguishability is a business requirement (really?) you could just get away with using ECB instead of any other mode.


Is the following key stretching algorithm as memory hard as I think it is?

Let $n$ be the number of "memory cells", and $t$ the number of iterations (i.e. the three steps you describe in your question). Then we see that at each iteration, each cell has an equal probability of being picked. Then, the probability that any one cell is not selected on this iteration is:

$$1 - \frac{1}{n}$$

And hence, the probability that one cell is never selected, is:

$$\left (1 - \frac{1}{n} \right )^t$$

And so if the attacker uses an intelligent memory cell addressing system, he really only needs:

$$b \cdot n \cdot \left [ 1 - \left (1 - \frac{1}{n} \right )^t \right ] ~ ~ ~ \text{bits of memory}$$

Where $b$ is the cell's size. For $b = 256$, $n = 128 ~ \text{MB} / b = 4 \cdot 10^6$ and $t = 200000$, we get:

$$\text{Memory required} \approx 6.25 ~ \text{MB}$$

Far less than the $128 ~ \text{MB}$ expected. And that's a lot of iterations. For $t = 2 \cdot 10^6$, we need $50 ~ \text{MB}$.

Now look at the probability of a cell only getting used once (then saving its value is irrelevant), and watch your scheme crumble. At least, if I understand it properly. To be specific, your logic fails at this point:

  Intuitively, it seems to me that any algorithm that wishes to find the
  digest after the last iteration of the above loop needs to invest in
  at least enough storage to hold all cells that have been modified.

In which you didn't consider that with your current key stretching algorithm, most cells won't be modified more than once unless you have a ludicrous number of rounds, so you don't need to invest memory to save those cells (since they are zero-initialized). Take a look at how scrypt does it - you can choose to not use any memory at all if you want, but you'll need to spend a lot more computational power. It's a trade-off. In your scheme, there is no trade-off. I can choose to not spend memory... for free.

In other words, your algorithm is a bit too simple. What you are missing is a step that initializes all the memory cells with pseudorandom (not random-access) values derived from the key, in which case storing them would be a necessity, and the scheme would a priori not be subject to this weakness.

Of course, this is all for fun and academic interest. If you need a memory-hard KDF, use scrypt.


Security of password hash with known prefix and appendix

Except against rainbow tables, it makes no difference whether you've prepended or appended any bytes if they're known and static. Both may as well not exist.

So the scenario is reduced to "doing a checksum of" (presumably trying to hash) a 32-byte password.

There isn't a CRC-128 in common use, but if you extended the CRC algorithm to 128 bits, you'd get a completely insecure transformation. CRC was designed for simplicity and low collision probability, making it reversible. There's a paper specifically on reversing CRC - https://sar.informatik.hu-berlin.de/research/publications/SAR-PR-2006-05/SAR-PR-2006-05_.pdf - and the process can be implemented by a decent high school student.

Algorithms resistant to that - producing a true one-way transformation - are called hashing algorithms, not checksums. Popular examples of hashing algorithms include SHA-3 and SHA-2.

For passwords specifically, an even higher level of security is often called for, such as using key derivation functions (PBKDF) - bcrypt, scrypt, argon2. In addition to the quasi-randomness property that hashes have and CRC don't, PBKDF deliberately tie up additional computer resources to somewhat improve their brute-force resistance.


What are the relations between cryptanalysis of block ciphers such as AES and Kendall's tau coefficient?

Here is a wild guess as to what this reference may actually mean.

TL;DR; The Kendall $\tau$ can be used to measure how close different rankings of key guesses resulting from stages of the attack are, to track if the attack is getting close to the real key ranking, in some sense.

Aside: The paper On Probability of Success in Linear and Differential Cryptanalysis by A A Selcuk, available here is an excellent reference on probability of success in linear and differential cryptanalysis, where ranking of keys is also mentioned.

Please note that the idea of Pearson correlation coefficient is quite general, however it does measure correlation between random variables, including the type of binary random variables encountered in linear cryptanalysis, for example, if we focus on a single Sbox $S(\cdot)$,
$$
\textrm{corr}_{a,b}(S)=\sum_{X \in \{0,1\}^n} (-1)^{a\cdot X\oplus b\cdot S(X)}
$$
is exactly a Pearson type of coefficient for the pair of binary random variables
$$
(-1)^{a\cdot X},(-1)^{b\cdot S(X)}.
$$
However, I don't think this is where the interesting direction of this argument lies.

For sure, we choose $a,b$ in order to maximize the correlation, and eventually do this for $r-1$ rounds in order to attack some input key bits into the $r^{th}$ round by partial decryption of the ciphertext, conditional on those guessed keys. Specifically the key  guess which maximizes the overall correlation dependent on whatever $a_i,b_i$ choices in a collection of Sboxes away from zero as we compute biases over a large set of plaintext/ciphertext pairs are hypothesized to be more likely to be the correct key guess.

However, how does this actually work in practice?

We obtain a ranking of key guesses from most likely to less likely, based on the correlation samples obtained. We keep a count of how many times each key guess satisfies the hypothesized linear expression, and rank guesses according to how biased they are. I will refer to the most likely key as the highest ranked. There is an actual correct ranking which puts the correct key on top and all the rest below it. In fact the collection of rankings which put the correct key on top, and the rest arbitrarily are all admissible.

Let's recall the wikipedia reference to Kendall's $\tau.$

  The Kendall tau rank distance is a metric that counts the number of pairwise disagreements between two ranking lists. The larger the distance, the more dissimilar the two lists are. Kendall tau distance is also called bubble-sort distance since it is equivalent to the number of swaps that the bubble sort algorithm would take to place one list in the same order as the other list.

The evidence is that AES is very strong against differential cryptanalysis. This means that it will require a huge number of plaintext/ciphertext pairs to break it this way.

To make things simple, consider attacking AES in a sequence of attacks using $K_i=2^{(i+N)},$ for $i\geq 0,$ plaintext/ciphertext pairs, where $N$ is some large integer. This is conceptual of course, since $N$ has to be impractically large.

Say we look at the ranking of the key guesses that result from each of these attacks (by doubling the number of P/C pairs used at each step as $i$ increases). If we want to gauge how we are progressing as $i$ increases, we would like to find out if some kind of convergence in the key ranking is occuring towards the correct ranking. Let $\pi_i$ be the ranking corresponding to the $i^{th}$ attack.

One way of doing this would be to compute the Kendall $\tau$ coefficient between the different rankings $\pi_i.$

A similar argument could be made for differential cryptanalysis as well, since both attacks rely on collecting enough plaintext/ciphertext samples so that the correct key guess has the highest rank, rank 1, with high probability.


Note: this is only an attempt at answering the first part of the question, asking if William's p+1 factorization method is redundant with Pollard's p-1, on the basis of how the algorithms are used in practice.

Pollard's p-1 (resp. William's p+1) factorization method is efficient to find a factor of $n$ if any of the factors $p$ of $n$ is such that $p-1$ (resp. $p+1$) has no prime factor above some moderate bound $B$. An improvement puts a bound $B_2$ for the highest prime factor of $p-1$ (resp. $p+1$), and another bound $B_1\ll B_2$ for the other factors.

The original paper on Williams's p+1 also presents Pollard's p-1.

Pollard's p-1 factorization is used in some recent factorization efforts with bounds up to $B_1≈2^{40}$ and $B_2≈2^{50}$; if unsuccessful, that's sometime followed by William's p+1 with slightly lower bounds, before gearing-in ECM.

If we construct a 1024-bit integer $n=p⋅q$, with $p+1=p_0⋅c_0$, $q+1=q_0⋅c_1$, $p−1=p_1⋅p_2⋅p_3⋅⋅⋅p_{11}⋅p_{12}⋅c_2$; $p$, $q$, $p_j$, $q_0$ primes; $p$ 415-bit, $q$ 610-bit, $p_0$ and $q_0$ at least 200-bit, other $p_j$ 32-bit; then it is likely amenable to Pollard's p-1 factorization (because $p-1$ has no factor wider than 32-bit), but I see no reason why I can't tell if it would be amenable to William's p+1 factorization (because both $p+1$ and $q+1$ have a high prime factor).

One such integer (also in this pastebin) is $n =$ 170008213545910965886460576572090982063408798024984543559001546422534644045470603998698706971810963093964580198788881904271608774213396896678573575267676754780622889919559692654436815810637860509009977667589657189496387034548011094365919416175990986348895410113935005204972304311894659720336969894022598750477

Another similarly constructed integer of 448 bits, factorisable with Pollard's p-1 setup with $B_1=4000$, $B_2=10000$, is $n =$
726286104974888320831459714524497735770165786243885681724247623636059281197969465033496277725004244158329276076523947799294094896411843


Do any (non-hardware) RNGs exist which could be used to create an OTP for crypto purposes?

The system you describe is not a one-time pad, it is a stream cipher, and a bad one for that.

A one time pad has real (truly) random bits in the XOR pad, which are never reused for two messages. "Their" cipher has a pseudorandom pad (with non-crypto PRNG), and if I understand right, even the same one for each message.

Even a real random one-time-pad is vulnerable if the same key is used twice (or more often) for different messages (or the same message, if you don't want the attacker to know that it is the same message).

Even if you use a good stream cipher (or PRNG), and use different "passwords" (i.e. keys) for each message (or use a stream cipher with an IV input, and use different IVs for each message), you don't get the perfect security guarantees of an one-time pad – it can be brute-forced, with effort depending on the key size.

For a system to have the security guarantees of an OTP, you need key entropy of at least as much as the message length.

If you have such keying material, but not in a form suitable for direct use as a key (e.g. not equi-distributed, like a really really long passphrase), you might be able to pre-process it using some crypto functions like a hash functions, to transform it into a form usable for an OTP key. Though the transformation algorithm must be studied to make sure that enough entropy stays – for your OTP you need your $n$-bit output to have $n$ bits of entropy, which is not that easy using hash functions with internal state size $< n$.

Actually, most hardware PRNGs work that way – they measure some data and use it as entropy input to a crypto-PRNG.


Is it possible to use an algorithm to generate an OTP?

This is a standard concept in cryptography, and it is called a stream cipher.

It doesn't give ‘perfect’ secrecy, which is a red herring, but it is the modern standard for how to do cryptography—for example, your web browser is almost certainly using exactly this principle right now to talk to the crypto.stackexchange.com web server, using either AES-GCM or ChaCha/Poly1305, which are authenticated ciphers built out of stream ciphers.

Much more important: Use an authenticated cipher so that a forger can't modify your messages in transit, which can sometimes—like in OpenPGP's EFAIL—have the consequence of losing confidentiality too.


Can we share an n-bit string by using shamir's secret sharing n times?

For Shamir's Secret Sharing, with a secret of size $n$, instead of having a finite field of order $n$, can we just use Shamir's Secret Sharing $n$ times, once for each bit, using a field of order $2$?

If you are asking whether Shamir Secret Sharing works over the field $GF(2)$, well, no it doesn't (unless we have exactly one share); the problem is that, for each share, we need to give it a distinct nonzero $x$ coordinate.  For $GF(2)$, there's only one available value (1), and so, unless we're happy with there being only one share that we can distribute, it doesn't work.

However, if you mean 'can we use a field with a characteristic of 2' (say, $GF(2^8)$, yes, that works just great (and, in fact, what is commonly used in practice); $GF(2^8)$ gives us 255 possible shares, and that's often enough.

In addition, it is perfectly safe to split up a secret, and share each part separately; the only issue with your proposal is the size of the field.  Of course, if you were using $GF(2^8)$, you could split up the secret into 8 bit pieces, rather than a single bit, if you so choose.


Is rekeying attack the same as related-key attack?

No, rekeying is about changing keys: https://en.m.wikipedia.org/wiki/Rekeying_(cryptography)
And we can have attacks ob the process of changing the key without need to have related keys. Which are two(or more) keys with some relation to each other which may lead to an attack.


Is this correct way to generate stream cipher using AES CTR mode?

The seed should be the key and the nonce or IV. Those input parameters determine the value of the key stream. Note that the nonce may be implied if the key is not reused, in that case the key may be the only seed, with the nonce having a static value (you should however make sure that you are not vulnerable to multi-target attacks if you use a static IV, see the comment of CodesInChaos below).

For most stream ciphers - such as CTR mode of encryption - the key stream is used to encrypt the plain text by XOR'ing the plain text with the key stream. Obviously if you are just interested in the key stream of N bits then you can simply encrypt a plain text consisting of N bits set to zero (as zero is the identity element for XOR). Depending on the implementation the underlying key stream may also be available directly.


R-LWE key exchange why using FFT instead of Karatsuba

First, as "Hope that's a start" mentioned, your citation is about the algorithms for multiplying integers, not polynomials. For polynomials, the FFT starts to be more efficient than Karatsuba and Toom-Cook methods much earlier, for polynomials of degree between (very roughly) a few hundreds and a few thousands.

However, for polynomials with integer coefficients, it is usually better to take the NTT (number theoretic transform) rather than the FFT, especially if those coefficients are considered modulo a certain $q$. First, you get no precision issues. Second, it is much faster. I have no idea why in the article you mentioned, the authors use FFT and not NTT, so it might be a good idea to ask them.

Now, to answer your question, the efficiency of NTT and Toom-Cook/Karatsuba methods are comparable for parameters equal to those you mentioned. Most lattice-based crypto implementation papers I have seen use the NTT (eg. New Hope), since the underlying rings are usually of the NTT-friendly form $\mathbb Z_q[x]/(x^{2^k}+1)$, and applications such as homomorphic encryption require bigger $n$'s, in which case NTT is clearly faster. That being said, I have seen efficients combinations of Karatsuba, Toom-Cook and schoolbook multiplication (eg. NTRU Prime) in lattice-based crypto.


Simultaneous Discrete Logarithm with Small Exponent

For $i\in\{1,2\}$ it is given prime $p_i$ with $q_i=(p_i-1)/2$ also prime, integer $g_i$ of multiplicative order $q_i$, and integer $y_i$ such that for some untold integer $x$ common to both $i$, it holds ${g_i}^x\equiv y_i\pmod{p_i}$.

With the additional information that $0<x<\min(q_1, q_2)$, if we can solve either of the two Discrete Logarithm Problems, then we can solve the other with a single modular reduction.

Proof: WLoG, say we solved for $x$ the DLP ${g_1}^x\equiv y_1\pmod{p_1}$ and a solution is $x=x_1$ (swap the indices if we solved the other DLP). Compute $s=x_1\bmod q_1$. It holds that all solutions to that DLP are of the form $x=k\,q_1+s$ with $k\in\Bbb Z$. And $x=s$ is the only solution to that first DLP with $0\le x<q_1$. Hence $s$ is the only possible solution to that first DLP matching the stronger condition $0<x<\min(q_1, q_2)$. Hence that $s$ must be a solution to both DLP, and the only such one (formally, we do not even need to check that $0<s<\min(q_1, q_2)$ and ${g_2}^s\equiv y_2\pmod{p_2}$, even though in practice we would).

Since we need to solve only one DLP, and anyone of the two possibly according to which we find easier, that's "better" than "solv(ing) the two discrete logarithms independently"; and that improvement is directly enabled by $0<x<\min(q_1, q_2)$. This answers in the affirmative a possible reading of the question.

But we are told that the question really asks: assuming $0<x<\min(q_1, q_2)$, is there an approach which solves the two DLPs simultaneously that is faster than solving either DLP? That's a much harder question, and right now I have no clue.

Note: even the weaker additional information $0<x<\max(q_1,q_2)$ and solving one of the two DLPs in isolation would greatly help towards solving both. When $p_1\ge p_2$, the $s$ computed as above would be the only possible $x$. And for $p_1<p_2$ we could reduce the search of $x$ to the search of $k$ in a DLP of the form $g^k\equiv y\pmod{p_2}$ with $0\le k<\lceil q_2/q_1\rceil$, making the search easier (by enumerating $k$ when $p_1$ and $p_2$ have about the same size, or Baby-Step/Giant-Step if they differ by a few dozen bits). $g$ and $y$ are easily computed as $g={g_2}^{q_1}\bmod p_2$ and $y={g_2}^{-s}\,y_2\bmod p_2$.


Two plaintexts map to the same ciphertext in fully homomorphic encryption?

Same ciphertext from different keys

Since deterministic Homomorphic encryption schemes are insecure, all the proposed HE schemes randomize the ciphertexts in some way, i.e., during the encryption, some random value $r$ is sampled and combined with the ciphertext.

Hence, given two different keys $k_1$ and $k_2$ and two messages $m_1$ and $m_2$, we usually can find two possible random values $r_1$ and $r_2$ that make $Enc(m_1, k_1; r_1) = Enc(m_2, k_2; r_2)$, therefore, the answer for your question is yes.

For example, in schemes based on the Approximate-GCD problem, such as DGHV10, a message $m_i$ is encrypted as $pq_i + r_i + m_i$, where $p \in \mathbb{Z}$ is the secret key and $q_i$ and $r_i$ are random integers.

So, given two keys $p_1$ and $p_2$ and two messages $m_1$ and $m_2$, it is sufficient to take $q_1 = p_2k$, $q_2 = p_1k$ (for any $k$) and $r_1 = r_2 + m_2 - m_1$.

Then we see that
$$Enc(m_1, p_1; q_1, r_1) = p_1q_1 + r_1 + m_1 = p_1p_2k + r_2 + m_2 = p_2q_2 + r_2 + m_2$$
which corresponds to $Enc(m_2, p_2; q_2, r_2)$.

For the BGV scheme, it is a bit more complicated, but you can still choose keys such that it holds. Namely, let $s_1, s_2 \in R := \mathbb{Z}[x]/\langle f(x) \rangle$ be two secret keys and use the same $\vec e$ in the corresponding public keys. Than, we can set

$$m_1 + s_1\langle \vec a, \vec r \rangle + 2\langle \vec e, \vec r \rangle = m_2 + s_2\langle \vec a, \vec r \rangle + 2\langle \vec e, \vec r \rangle \mod q$$
where $\langle \vec a, \vec r \rangle $ denotes the inner-product and it is a polynomial in $R$.

This equality is satisfied if $s_1 = m_2\langle \vec a, \vec r \rangle^{-1} + s_2 \mod q$.

Computational "paradox"

First of all, you are not modeling the running times correctly, because finding four keys that produce the same ciphertext is more than two times slower than finding two keys, that is, you cannot simply use $T(key)\cdot|X|$, you should use $T(key, n)$ and $T$ is most probably not linear in $n$, since you have to solve systems with more than $n$ variables to find the keys.

Furthermore, that apparent contradiction with the "laws" of computation is not implied by the ability of finding such keys. Actually, what you need is not only to create equal ciphertexts but also two find a way that their evaluation yield the same ciphertext. It might be the case that $c_1 := Enc(x_1, k_1) = c_2 := Enc(x_2, k_2)$, but $Eval_1(f, c_1) \not = Eval_2(f, c_2)$, and therefore, you could not evaluate $f$ homomorphically a single time and decrypt it with two different keys.


Examples of applications that use the Schnorr digital signature?

Despite their theoretical security advantages, Schnorr signatures aren't very popular. Probably because they were patented. Since the patents expired in 2008 they might rise a bit in popularity. But probably only in the elliptic curve form, and not in finite fields.
I don't know of any application actually using Schnorr signatures, but I know several that plan to or at least considered it. Either in the form of EC-Schnorr or Ed25519.
Both of these are essentially Schnorr signatures, but on elliptic curves. Ed25519 adds a few modifications, such as making signing deterministic and a message hash that hashes R before the message, but it's still very similar to Schnorr.

Tahoe-LAFS plans to use Ed25519
Ticket #217 - Ed25519-based mutable files -- fast file creation, possibly smaller URLs
https://tahoe-lafs.org/pipermail/tahoe-dev/2012-March/007109.html
It looks like they'll include in some places in their next big release (1.10)

Cryptosphere plans to use Ed25519
https://github.com/tarcieri/cryptosphere#readme

Bitcoin developers considered using Ed25519:
Theoretical max speeds for ECDSA verification
But it seems like they won't actually use it

EMVCo considers using EC-Schnorr in their EMV standard

EMV is a global standard for credit and debit payment cards based on chip card technology. As of end-
2010, there were more than 1.24 billion EMV compliant chip-based payment cards in use worldwide.

From the EMVCo homepage

What is the EMVCo position on elliptic curves or other alternative cryptography?
EMVCo constantly reviews alternative types of cryptography. For further information regarding elliptic curve cryptography with EMV see the ECC draft of Book 2 (June 2007) located on the EMV website under Specifications > Additional Files > New Cryptography Drafts. The EMVCo Security Working Group is considering the use of ECDSA (or Schnorr ECDSA) for offline card authentication and the use of ECIES for offline PIN encipherment.

From EMVCo Security FAQ


Why is feed-forward mechanism used in hash functions?

If you remove the feed-forward part, then you reduce the strength of the hash against preimage attacks.  We expect a hash with an $N$ bit output to require $O(2^N)$ steps to find a preimage (that is, an input that hashes to a specified value).  However, without the feed-forward, we can find a preimage with $O(2^{N/2})$ steps.

Here's why: without the feed-forward, the compression operation is reversible; if you know the output of the compression function and the block of data being hashed, you could compute the input to the compression function.

Here is how this works: suppose we have SHA-256 (to take a concrete example), and we want to find a preimage for a specific value $x$.  We consider two block messages (after padding); we construct $2^{128}$ initial blocks $A_i$ and compute what the state $a_i$ of the SHA-256 hash after each such initial block.

We also construct $2^{128}$ final blocks (which include the SHA-256 internal padding) $B_j$ and compute what the state $b_j$ of the SHA-256 hash would be previous to that (assuming that the final state of the SHA-256 hash is $x$.

We scan through the lists $a_i$ and $b_j$ looking for a match; if we find a specific pair $a_i = b_i$, we then know that the message $A_i B_j$ will hash to the value $x$; that's because the initial block $A_i$ will set the SHA-256 state to $a_i$, and then the final block $B_j$ will convert that state $b_j$, which is the same as $a_i$ to the desired final state $x$.  Thus, we found a preimage to a 256-bit hash with about $2^{128}$ steps.

In essense, we use an internal collision to find the preimage.  Adding the feed-forward makes this attack impossible.

(One note: if you try this attack against SHA-384, you find it takes $2^{256}$ steps, not $2^{192}$ as this analysis would seem to imply.  It is still easier than the $2^{384}$ steps would would expect from a 384 bit hash.


What I will describe is "the RSA timelock proof of work protocol",

which does not seem to have a canonical reference.

The server generates large random primes $\hspace{.02 in}p$ and $q$, then calculates

$M \: = \: \hspace{.02 in}p\hspace{-0.02 in}\cdot\hspace{-0.02 in}q \;\;$ and $\;\; L \: = \: \left\lfloor \sqrt{M}\right\rfloor\hspace{-0.02 in}+\hspace{-0.02 in}1 \;\;$ and $\;\; \lambda \: = \: \operatorname{Lcm}(\hspace{.03 in}p\hspace{-0.03 in}-\hspace{-0.04 in}1,\hspace{-0.01 in}q\hspace{-0.03 in}-\hspace{-0.04 in}1) \;\;\;$.

The server publishes $M\hspace{-0.02 in}$, stores $L$ (not necessarily secretly), and keeps $\lambda$ secret.

To give a challenge with difficulty paramter $T$, the server samples $n$ from $\{L,L+1,L+2,L+3,...,(M-L)-2,(M-L)-1,M-L\}$

and then sends $T$ and $n$ to the challenge's recipient.

To solve a challenge, the recipient iterates $\: n\mapsto \operatorname{mod}(n^2\hspace{-0.02 in},\hspace{-0.01 in}M\hspace{.02 in})$

$T$ times and then sends the result to the server.

The client (if honest) will end up with $\:\operatorname{mod}(n\text{^}\hspace{.01 in}(\operatorname{mod}(2^T\hspace{-0.02 in},\lambda)),M\hspace{.02 in})\:$, $\:$ which the server can easily calculate.


Hashing or encrypting twice to increase security?

SHA-256(SHA-256(x)) was proposed by Ferguson and Schneier in their excellent book "Practical Cryptography" (later updated by Ferguson, Schneier, and Kohno and renamed "Cryptography Engineering") as a way to make SHA-256 invulnerable to "length-extension" attack. They called it "SHA-256d". We started using SHA-256d for everything when we launched the Tahoe-LAFS project in 2006, on the principle that it is hardly less efficient than SHA-256, and that it frees us from having to reason about whether length-extension attacks are dangerous every place that we use a hash function. I wouldn't be surprised if the inventors of Bitcoin used it for similar reasons. Why not use SHA-256d instead of SHA-256?

Note that the SHA-3 project required all candidates to have some method of preventing length-extension attacks. Some of them use a method that is rather like SHA-256d, i.e. they do an extra "finalization" hash of their state at the end, before emitting a result.


Tape is a basic concept from Turing machines.

The random tape is the tape with random bits on it.


Decrypted RSA 64 bit encryption using modulus and private exponent. Got gobbledygook [Verify]

I did the procedure myself, and I can confirm that base64 decoding will do the trick; the full decrypted file will have == at the end somewhere. After decoding, the "file" command will reveal the plain text type. The '.uyu' file is quite easy to "decrypt" as well, I noted.


The way your question is written, it's hard to tell what you're asking.

The trivial answer to your original question is that, if you only know $a$ and $c$, then you can calculate $s_1 \oplus s_2 = a \oplus b$, but not the individual values $s_1$ and $s_2$; for every $s_1$, there's a corresponding $s_2$ that satisfies the equations, and vice versa.  The same holds true even if you know multiple $(a,c)$ pairs calculated using the same $s_1$ and $s_2$, since each such pair will just yield the same value of $s_1 \oplus s_2$, and no other relevant information.

As for the protocol description you edited in, I have no idea what your protocol is supposed to accomplish, and I suspect you've garbled the description somehow.  In particular, if Bob indeed computes both $b = a \oplus s_1$ and $c = b \oplus s_2$, and only sends $c$ back to Alice, then the value $b$ plays absolutely no role in the protocol: Bob could equivalently just compute $c = a \oplus s_1 \oplus s_2$ directly.  Also, without knowing $b$, Alice cannot possibly verify that $b = c$.  Bob could do that, but that's equivalent to just verifying that $s_2 = 0$, which he could just as well check without running the protocol at all.  So your protocol, as written, makes no sense.

Anyway, even if the protocol was fixed to actually work, I don't see any way to build a secure authentication protocol out of just linear operations like XOR.  You'd need something else, like a block cipher, to do that.


Given 2 Digital Signature generated by $S=D\times k^r$ how do you solve for $k$?

Given that $\gcd(r_1, r_2) = 1$, using the extended Euclidean algorithm we can find $a,b$ such that $a \cdot r_1 + b \cdot r_2 = 1$. If $D_1$ and $D_2$ are invertible $\mod N$ (which is quite likely; they only have to be coprime to the two large primes that make up $N$), we can compute $$k^{r_1} = S_1 \cdot {D_1}^{-1}$$ $$k^{r_2} = S_2 \cdot {D_2}^{-1}$$

Then we can compute $$(k^{r_1})^a \cdot (k^{r_2})^b = k^{a \cdot r_1} \cdot k^{b \cdot r_2} = k^{a \cdot r_1 + b \cdot r_2} = k^1 = k$$


Scalar multiplication with projective coordinates

3d multiplication is a simple multiplication not a mod multiplication.

I suggest you to check IEEE Std 1363-2000 document and "A.10.3 Elliptic scalar multiplication" part of that document if you can.
It has somewhat more explanation than Nist's document.


The values $\mathtt{sign0}$ and $\mathtt{sign1}$ are just signs, i.e., indicating negative or positive sign (elements from the set $\{-1,1\}$).


Comparison of security definitions for signatures

What I see that their difference is that in EUF-CMA experiment, the adversary needs to produce a valid signature for a message of its choosing, where the message has not been queried before (i.e., a message for which the adversary hasn't made queries to the oracle).

  Whereas in the sEUF-CMA experiment, similar thing happens, though now the adversary needs to make sure that it hasn't queried the oracle with the forged (message, signature) pair. So, simply the signature also enters into the equation in sEUF-CMA.

Right.  The point of EUF-CMA is the forger simply can't find a signature on any message it didn't send to the oracle.  With sEUF-CMA, the forger can't find a message/signature pair it didn't get from the oracle—not even a second signature on a message it did send to the oracle.

  The part that I don't understand is why the sEUF-CMA actually constitutes a stronger definition than regular EUF-CMA definition? Why does including the signature makes it stronger?

Can you forge signatures for messages not previously seen in an sEUF-CMA signature scheme, or can you prove that that's not possible?  What does that imply about whether an sEUF-CMA signature scheme is necessarily EUF-CMA?
Can you find a signature scheme that satisfies EUF-CMA but not sEUF-CMA?  (Hint: you already did!)  What does that imply about whether an EUC-CMA signature scheme is necessarily sEUF-CMA?

‘Strong’ just mean it implies other properties which don't necessarily imply it conversely.  Most protocols don't rely on strong unforgeability.  While Bitcoin doesn't rely on strong unforgeability, the first Bitcoin exchange, MtGox, did; it was exploited, because ECDSA does not provide strong unforgeability, and the subsequent demise of MtGox was later blamed on transaction malleability, whether rightly or not (paywall-free).

Another relevant property is signature uniqueness where even the signer can't come up with a second signature for a message—for this you may even want a VRF, a verifiably pseudorandom function, which is a PRF to anyone who doesn't know the key and is a signature to anyone who does and gives a verifiable proof of uniqueness.

  Also, for example in ECDSA, for a message $m$ and a valid signature $\sigma = (r,s)$, the signature $\sigma' = (r, -s \bmod N)$ is also valid. So, in a sense you get a new signature $\sigma'$, but, actually the signed message is the same $m$.

  So, this seems to me that it does violate sEUF-CMA as, although the message is the same one, the signature is different, so adversary wins. Whereas, this cannot violate EUF-CMA, while there we care only for the message, so we don't care if adversary can produce a forgery for an already queried message. So, it achieves EUF-CMA security, but not sEUF-CMA, right?.

Correct.

  I think the situation is also different in textbook RSA, where it has homomorphic properties, so given a valid $(m, \sigma)$ pair, using the homomorphic properties one can produce a valid signature $\sigma'$ for a new message $m'$, and it seem does not satisfy any of the provided security definitions, is that right?

Textbook RSA signature is, indeed, completely broken.  RSA was the first idea for how to make a signature scheme, but it was completely insecure; the first secure signature scheme was Rabin's in 1979.

The crucial insight of Rabin was that hashing is an integral part of a signature scheme.  Some textbooks will confusingly describe hashing as an afterthought to compress long messages, and talk of hash-then-sign, which is a dangerously wrong idea that can lead people to make mistakes that destroy security.

The computation of a hash and the computation of fancy math can be done separately, but only when they are combined into a verification equation like $\sigma^e \equiv H(m) \pmod n$ do you get a secure signature scheme.


I don't understand RSA encryption (specific questions)?

Why do we choose the value of e such that e is relatively prime to the totient (as opposed to just being relatively prime to n?)

The final goal of RSA encryption is to have $m = c^d \bmod n$, which is the same as $m = (m^e)^d \bmod n \rightarrow m = m^{ed} \bmod n$, i.e., if you encrypt and then decrypt, you get the same original message. For that last equality to be true, raising to $ed$ needs to be the same as raising to $1$.

When you work with powers modulo some number, you eventually "go back to the start". For example, if you compute $m^1 \bmod n$, $m^2 \bmod n$, $m^3 \bmod n$, the result will eventually go back to $1$ (unless $m\bmod n=0$). The exponent where this happens is called the order of $m$. If $n$ is the product of two distinct primes, then this happens at $\phi(n) = (p-1)(q-1)$ (it happens sooner: at $\lambda(n) = \operatorname{lcm}(p-1, q-1)$, the Carmichael's Function; or sooner depending on $m$; but it doesn't matter for this explanation).

Therefore, we know that $m^{\phi(n)} = 1 \bmod n$ and therefore $m^{\phi(n)+1} = m \bmod n$. And if you add any multiple of $\phi(n)$ to the exponent the result stays the same. In short, in the exponent, you're working modulo $\phi(n)$. And since you need $ed$ to be the same as $1$ in the exponent, then $d$ must be chosen such that $ed \equiv 1 \pmod{\phi(n)}$

  Also, if both e and n are public then how is that secure at all? I guess I'm confused because if everyone is receiving the same public key then isn't the inverse operation going to be the same for everyone and thus not secure?

Each person has a different public key and matching private key. Thus the inverse operation is not going to be the same for everyone, it's the same for each person (each public key holder). The values $e$ and $n$ are indeed public, because the secret value (the private key) is $d$. Each person has their own $e, n, d$ values (tough $e$ is usually the same for everyone, but the others should always be different).


Why is only one generator stated in literature for elliptic curve group P-256?

You are correct.
All points in a prime order curve (except $\infty$) are generators of the whole group.

But for practical applications a specific one must be chosen to make protocols work.

For example, Diffie-Hellman works only if the two public keys are computed as a random multiple of the same generator.

So it make sense that, among the curve's parameters, there is also a chosen, fixed, base point.

You are free to design protocols with alternative generators, but, as any point (except $\infty$) is as good, it makes no sense for interoperability purposes.

For P-256 the choice of the generator, like for the curve's parameter $b$, is done using a deterministic algorithm with a (supposedly) random input seed.

Other curves might have different way of choosing it. For example curve25519 uses the point with the lowest absolute value of $x$ belonging to the large prime order subgroup.


…
  What is the best method to make the bias go away?
  …

No matter if we’re talking about the bias coming from manufacturing flaws, or the bias we know from casino-quality dice, you can use the Von Neumann skew-correction algorithm to generate uniformly random data from skewed input.

The Von Neumann skew-correction algorithm was published in “Various techniques used in connection with random digits.” (NIST journal, Applied Math Series, 12:36-38, 1951). Since the paper is hard to find online due to its age and publication date, I‘ve put a copy in my Google Drive account (PDF) for reference purposes.

The general idea behind Von Neumann’s skew correction is to consider sequences of rolls/coin-tosses/whatever instead of isolate ones while picking a sequence length long enough that an even number of possible outcomes has equal probabilities.

Explaining the Von Neumann skew-correction algorithm:

For dice, pick a sequence length where $n>2$. The reason for picking a sequence length of $n>2$ is that no subset of possible outcomes of equal probability for $n=1$ or $n=2$ has a cardinal divisible by $6$.

So, for this example, let’s simply take $n=3$. Doing so, the outcomes of any dice can be partitioned into 6 categories of equal probability according to the relative ordering of the successive numbers rolled – provided these numbers are all different.

We need this, so that sequences can be grouped according to whether the second number is greater – 1 – or smaller – 0 – than the first, and whether the 3rd number is greater 111,011 or smaller 100,000 than both the first and the second, or between them 110,001.

All 6 possible orderings will occur with equal probability because each of the sequences belonging to any of these orderings matches exactly one sequence of equal probability in every other ordering. Meaning: 1,2,4,1,2,4 matches the ordering 111, while 2,1,4,2,1,4 (which is equally likely to be rolled) matches 011.

EDIT

@fgrieu describes a different, yet equally practical implementation in his comment below.


HMAC vs PKDBF2 as the first step towards HKDF

I don't think you get those "examples": they implement HKDF. The full name of HKDF is HMAC-based Extract-and-Expand Key Derivation Function. They do not use PBKDF2 because they don't implement a specific use case, they implement the algorithm.

So it is perfectly fine to use:

master = PBKDF2(SHA-256, iterations, salt, password, 32)
authKey = HKDF(SHA-256, master, "authKey", 32)
encKey = HKDF(SHA-256, master, "encKey", 32)

This is pseudo code where the configuration options such as the hash function and the output size are also present in the parameters.

Note that although the SHA-256 is specified as configuration option, both PBKDF2 and HKDF will use HMAC-SHA-256 underneath (but HMAC has only one configuration option: the hash function to use, so this is equivalent).