面临密码学的学习挑战吗？别担心！我们的crypto-guide团队专业为您解决公钥密码、对称加密、哈希函数、数字签名等方面的问题。我们拥有深厚的专业背景和丰富的经验，能帮您完成高水平的作业和论文，让您的学习之路一路顺风！

以下是一些我们可以帮助您解决的问题：

密码学基础：对称加密、非对称加密、哈希函数等。

公钥密码和私钥密码：RSA加密、椭圆曲线密码、Diffie-Hellman密钥交换等。

哈希和数字签名：SHA-256、MD5、DSA、ECDSA等。

身份验证和安全协议：Kerberos、SSL/TLS、IPsec、OpenID等。

其他相关主题，如：密码学在网络安全、区块链、云计算中的应用、隐私保护、密码政策等。

Exercise 1 (30 points). Consider the following identification problem: there’s a “box” that controls access to some resource (e.g., a door) and authorized people are given some secret information that enables them to use the resource, but unauthorized people cannot do so, even if the know the contents of the box.

1. Consider the weakest security definition of this problem where the only attack we’re considering is an adversary that “listens in” on conversations between honest users and the box). Construct a non-interactive (i.e., a protocol consisting of a single message from the user to the box) protocol solving the identification problem and prove its security.

2. Construct a non-interactive identification protocol that remains secure under the stronger attack where an adversary may open up the box and see the data it contains, listen in on other conversations and also construct “fake boxes” and have the authorized people talk to these fake bozes. Prove the security for your protocol. You may assume that all parties have access to a perfectly synchronized global clock.

1. The most straightforward way to solve this identification problem is to use a symmetric key system. Each authorized person is given a unique secret key, and they simply send the key to the box when they wish to access the resource. The box compares the received key with its list of authorized keys, and if there’s a match, access is granted.

This system provides security against an adversary that only listens in on the conversation because without knowing the secret key, they cannot pretend to be an authorized user. However, this protocol is not secure if the adversary can also “talk” to the box because they can simply replay a key they’ve heard before, a so-called “replay attack”.

2. To construct a non-interactive identification protocol that remains secure even when an adversary can open up the box, see its data, listen in on other conversations, and create fake boxes, we can use a system based on public-key cryptography and timestamps, such as the following:

Each authorized person has a unique private/public key pair. When they want to access the resource, they send a message to the box containing their ID, the current time, and a digital signature over this data. The digital signature is generated using their private key.

The box checks the timestamp to make sure the message is recent (to prevent replay attacks), verifies the digital signature using the public key associated with the ID (which it has stored), and if the signature is valid, grants access to the resource.

This protocol is secure against the specified attack because even if an adversary listens in on a conversation or opens up the box, they cannot create a valid signature without the private key. They also cannot reuse an old message due to the timestamp check. Fake boxes are harmless because the authorized people only send their public key and a signature, which does not reveal any sensitive information.

This proof, however, assumes that the global clock is perfectly synchronized and that the time needed to break the encryption is longer than the validity period of a timestamp. Otherwise, the adversary might still be able to replay a message, or even have enough time to break the encryption and forge a signature.

Exercise 2 (Non malleability of CCA secure schemes – 30 points). An attractive way to perform a bidding is the following: the seller publishes a public key $e$. Each buyer sends through the net the encryption $\mathrm{E}_e(x)$ of its bid, and then the seller will decrypt all of these and award the product to the highest bidder.

One aspect of security we need from $\mathrm{E}(\cdot)$ is that given an encryption $\mathrm{E}_e(x)$, it will be hard for someone not knowing $x$ to come up with $\mathrm{E}_e(x+1)$ (otherwise bidder $\mathrm{B}$ could always take the bid of bidder A and make into a bid that is one dollar higher). You’ll show that this property is also related to CCA security:

1. Show a CPA-secure public key encryption such that there is an algorithm that given $e$ and a ciphertext $y=\mathrm{E}_e(x)$, converts $y$ into a ciphertext $y^{\prime}$ that decrypts to $x+1$. (If it makes your life easier, you can make the algorithm work only if $x$ is, say, a multiple of 100 .)

2. Show that if $\mathrm{E}$ is CCA secure then there is no such algorithm. In particular show that if $M$ is any polynomial time algorithm, and $X$ is a set of possible numbers $x$, then

$$

\underset{(e, d) \leftarrow \operatorname{Gen}\left(1^n\right)}{ }\left[\mathbf{D}_d\left(M\left(e, \mathrm{E}_e(x)\right)\right)=x+1\right]<\frac{1}{|X|}+n^{-\omega(1)}

$$

1. Consider a modified version of the ElGamal encryption scheme. In the usual ElGamal scheme, a message $x$ is encrypted under a public key $(g,h)$ as $(c_1, c_2) = (g^r, x \cdot h^r)$ for a randomly chosen $r$. Here, let’s consider an encryption of $x$ under public key $(g,h)$ as $(c_1, c_2) = (g^r, x \cdot 100 \cdot h^r)$ for a randomly chosen $r$.

Now, given an encryption $(c_1, c_2)$ of $x$ under public key $(g,h)$, we can compute an encryption of $x+1$ as $(c_1′, c_2′) = (c_1, c_2 \cdot g^r)$ for the same $r$. It’s easy to see that this is an encryption of $x+1$, since $(c_2′)/h^r = (c_2 \cdot g^r)/h^r = x+1$. This doesn’t violate the security of the ElGamal encryption because the adversary doesn’t know $r$.

2. If $E$ is CCA-secure, then there cannot be an algorithm $M$ that given $e$ and a ciphertext $y=E_e(x)$, converts $y$ into a ciphertext $y’$ that decrypts to $x+1$.

To see why, suppose that such an algorithm $M$ exists. We will use $M$ to build an adversary $A$ that can win the CCA security game. The adversary $A$ will submit $x$ and $x+1$ to the challenger in the CCA game, and receive a challenge ciphertext $y=E_e(x)$ or $y=E_e(x+1)$. It then applies $M$ to $y$ to obtain a new ciphertext $y’$, and submits $y’$ to the decryption oracle. If $y’$ decrypts to $x+1$, then $A$ guesses that the challenge ciphertext was an encryption of $x$; otherwise, it guesses that it was an encryption of $x+1$.

Clearly, $A$’s guess is correct with probability greater than 1/2, so this contradicts the assumption that $E$ is CCA-secure. Therefore, the probability of the event described in the question must be less than $1/|X| + n^{-\omega(1)}$.

**E-mail:** help-assignment@gmail.com **微信:**shuxuejun

**help-assignment™是一个服务全球中国留学生的专业代写公司专注提供稳定可靠的北美、澳洲、英国代写服务专注于数学，统计，金融，经济，计算机科学，物理的作业代写服务**