Delivery-Date: Sat Feb 26 10:00:38 2005
Date: Sat, 26 Feb 2005 10:01:15 -0800
From: ho chung <hochung@usc.edu>
Subject: Another question on HW3 Problem 3.2 solution
To: cs530@bourbon.usc.edu
Message-id: <193622a8291ab.422048eb@usc.edu>
MIME-version: 1.0
Content-type: text/plain; charset=us-ascii
Content-language: ko
Content-transfer-encoding: 7BIT
Content-disposition: inline
Priority: normal

Someone wrote:

You wrote that message was signed by alice with his prive key and decrypt it using bob public key. 

But actully if message was signed by alice with his private key then bob must decrypt it using alice public key not bob's. If bob decrypt using his public key then he must not get corect sign.

If this true then there is never issue with na nad nb reletionship. because message was signed by alice private key and bob decrypt it with alice public key. 
------------------------------------------------------------------------------------------------------------------------------
I think you are misunderstanding the question. Here, Alice wants to send a message that is BOTH *signed* and *encrypted* using RSA.  Traditionally, one would use hybrid of RSA and symmetric key to do this. But here the problem is just using the PKC.

So, Alice would sign the message (using her private key), and encrypt the signed message with Bob's public key.   However, if the size of the signed message,s , is greater than n_Bob, then message recovery fails. So, there is an issue with n_A and n_B relationship.

To avoid this case, if n_A > n_B, Alice can either encrypt the message first with Bob's public key, then sign the encrypted message (using her private key).


Return-Path: cs530@bourbon.usc.edu
Delivery-Date: Fri Feb 25 13:33:27 2005
Received: from bourbon.usc.edu (bourbon.usc.edu [128.125.9.75])
	by merlot.usc.edu (8.12.8/8.12.8) with ESMTP id j1PLXRja012981
	for <cs530@merlot.usc.edu>; Fri, 25 Feb 2005 13:33:27 -0800
Received: from bourbon.usc.edu (localhost.localdomain [127.0.0.1])
	by bourbon.usc.edu (8.12.8/8.12.8) with ESMTP id j1PLVXio026796
	for <cs530@merlot.usc.edu>; Fri, 25 Feb 2005 13:31:33 -0800
Received: (from cs530@localhost)
	by bourbon.usc.edu (8.12.8/8.12.8/Submit) id j1PLVWjc026788
	for cs530@merlot.usc.edu; Fri, 25 Feb 2005 13:31:32 -0800
Received: from msg-mx3.usc.edu (msg-mx3.usc.edu [128.125.137.8])
	by bourbon.usc.edu (8.12.8/8.12.8) with ESMTP id j1PLVWio026785
	for <cs530@bourbon.usc.edu>; Fri, 25 Feb 2005 13:31:32 -0800
Received: from usc.edu ([128.125.137.12])
 by msg-mx3.usc.edu (Sun Java System Messaging Server 6.1 HotFix 0.08 (built
 Dec  8 2004)) with ESMTP id <0ICH00FGJL8Q4LA0@msg-mx3.usc.edu> for
 cs530@bourbon.usc.edu; Fri, 25 Feb 2005 13:34:02 -0800 (PST)
Received: from [128.125.137.4] (Forwarded-For: [128.125.134.116])
 by msg-store1.usc.edu (mshttpd); Fri, 25 Feb 2005 13:34:02 -0800
Date: Fri, 25 Feb 2005 13:34:02 -0800
From: ho chung <hochung@usc.edu>
Subject: Questions on HW3 solutions
To: cs530@bourbon.usc.edu
Message-id: <f66dcc332ddb9.421f294a@usc.edu>
MIME-version: 1.0
X-Mailer: Sun Java(tm) System Messenger Express 6.1 HotFix 0.08 (built Dec  8
 2004)
Content-type: text/plain; charset=us-ascii
Content-language: ko
Content-transfer-encoding: 7BIT
Content-disposition: inline
X-Accept-Language: ko
Priority: normal

Someone asked:

(1) in 2.2,,,the answer said it reduces the space from 2^55 to s^54?shouldn't
 be from 2 ^56 to 2^55?
 
No. Statistically, if you guess a key from 2^56 keyspace, you only need to search 2^55 on average (that is, half of the keyspace).
However, in worst case, one has to search for all the keyspace 2^56. 
(I will deduct only a fraction, if you have answered the rest correctly except this numerical answer, 2^55.)

(2) in 2,2. the answer said this reduction is not of practical concern,,,,As 
know DES has been broken in 1998 by EEF(in page 64 in the book). So if the full
 key space (2 ^ 56) is of practical concern (because it was broken), why an att
ack to half of the keyspace is not of practical concern? Also minimzing it by half = eliminating 2 ^55 trials  > 3 * 10 ^ 16 ,,,,I believe that is a very large set of keys has been eleminated,,,why is that not of practical concern?(if 2^56 is of practical concern because DES was broken why not 2 ^ 55 of practical concern as well?)

The focus/keypoint of this question was whether the complementary property of a symmetric algorithm (e.g. DES) affects the security of the algorithm.  If so, how much?  As you've mentioned, DES was broken by other cryptanalysis techniques with the aid of hardware, but not due to the complementary property.  For example, if an encryption algorithm with 2^56 keyspace is secure, we can causiously say that 2^54 is also safe.   On the other hand, if an encryption algorithm with 2^56 keyspace is insecure, it is obvious that 2^54 is insecure.  Therefore, we can say that the complementary property is not a practical concern. In other words, dont  worry(?) about the property will significantly affect the level of security.


Return-Path: cs530@bourbon.usc.edu
Delivery-Date: Thu Feb 10 08:30:48 2005
Received: from bourbon.usc.edu (bourbon.usc.edu [128.125.9.75])
	by merlot.usc.edu (8.12.8/8.12.8) with ESMTP id j1AGUmja031857
	for <cs530@merlot.usc.edu>; Thu, 10 Feb 2005 08:30:48 -0800
Received: from bourbon.usc.edu (localhost.localdomain [127.0.0.1])
	by bourbon.usc.edu (8.12.8/8.12.8) with ESMTP id j1AGTWio016982
	for <cs530@merlot.usc.edu>; Thu, 10 Feb 2005 08:29:32 -0800
Received: (from cs530@localhost)
	by bourbon.usc.edu (8.12.8/8.12.8/Submit) id j1AGTWir016980
	for cs530@merlot.usc.edu; Thu, 10 Feb 2005 08:29:32 -0800
Received: from msg-mx3.usc.edu (msg-mx3.usc.edu [128.125.137.8])
	by bourbon.usc.edu (8.12.8/8.12.8) with ESMTP id j1AGTWio016977
	for <cs530@bourbon.usc.edu>; Thu, 10 Feb 2005 08:29:32 -0800
Received: from usc.edu ([128.125.137.12])
 by msg-mx3.usc.edu (Sun Java System Messaging Server 6.1 HotFix 0.08 (built
 Dec  8 2004)) with ESMTP id <0IBP000OXF7DPBE0@msg-mx3.usc.edu> for
 cs530@bourbon.usc.edu; Thu, 10 Feb 2005 08:30:49 -0800 (PST)
Received: from [128.125.137.4] (Forwarded-For: [24.24.228.58])
 by msg-store1.usc.edu (mshttpd); Thu, 10 Feb 2005 08:30:49 -0800
Date: Thu, 10 Feb 2005 08:30:49 -0800
From: ho chung <hochung@usc.edu>
Subject: Cancelling office hours today
To: cs530@bourbon.usc.edu
Message-id: <3119d62d18722.420b1bb9@usc.edu>
MIME-version: 1.0
X-Mailer: Sun Java(tm) System Messenger Express 6.1 HotFix 0.08 (built Dec  8
 2004)
Content-type: text/plain; charset=us-ascii
Content-language: ko
Content-transfer-encoding: 7BIT
Content-disposition: inline
X-Accept-Language: ko
Priority: normal

Hello class,

I am cancelling my TA office hours today because I am not feeling well due to cold and fever.
Sorry for the inconvenience.

Ho