news

斯坦福大学密码学家Boneh的基于身份的公钥密码系统

Fri Sep 21 15:08:37 PDT 2001
    Finally got ibe request working in Windows (did it by reading at the
    end of all the writes).

    Fixed infect.cc (was using "mail=" instead of "id=") and updated the
    webpage.


Thu Sep 20 18:51:13 PDT 2001
    Projective coordinates may help after all; it is true that I = 2.7M
    in F_p^2, but I = 7.5M in F_p, and group_times is only ever called
    with points in E/F_p.

    Small speedup after implementing signed sliding windows in group_times().

    More speed from switching to weighted projective coordinates.

    1024-bit times:

    0.01 initialization
    0.04 computing rP
    0.02 first part of map_to_point
    0.17 make_order_q
    0.18 miller()
    0.19 Tate power
    0.02 computing gid^r
    elapsed time: 0.64

    512-bit times:

    0.01 initialization
    0.01 computing rP
    0.01 first part of map_to_point
    0.03 make_order_q
    0.08 miller()
    0.03 Tate power
    0 computing gid^r
    elapsed time: 0.17

    (This was a report produced by a function I just wrote, which uses the
    routines in benchmark.cc which I also just wrote.)

    [ibe-0.16.tgz]

    Started writing ibe_help.txt


Thu Sep 20 15:27:42 PDT 2001
    512-bit times: (new goal is to get this running under 0.1 seconds)

    0.02 finding rP
    0.01 first part of map_to_point (hash + determine x coord)
    0.05 making it order q
    0.08 miller
    0.03 exponentiation of miller's output
    0.01 exponentiation of gid by r


Thu Sep 20 02:59:21 PDT 2001
    Put in rP optimization but it doesn't seem much faster. In fact,
    loading the cache file slowed it down but that's because I'm using
    the inefficient config.cc instead of special purpose cache loading
    routines. I suppose I need to use windows with the cache to get
    best results.


Thu Sep 20 01:52:12 PDT 2001
    Now I'm confused, after reading Blake, Seroussi & Smart
    ("Elliptic Curves in Cryptography", London Mathematical Society
    Lecture Note Series, Cambridge University Press),
    I wrote imratio.cc to find the relative costs of
    inversion and multiplication in F_p^2, and the ratio is under 3!
    This means projective coordinates shouldn't help at all!

    Maybe the speed gain is due to the lack of if's and assumptions made
    by fast_group_times()? (There is definitely an improvement of about
    0.05 seconds.)

    Will put in rP optimization. (i.e. take advantage of P being fixed
    throughout whole system.)


Wed Sep 19 19:54:02 PDT 2001
    Changed format of params file to look like config files for the other
    programs. That way I can use config.cc routines to parse it rather
    than some ad hoc routine. Also made it a struct instead of a class.
    I don't like OO programming in languages with no GC so I'll stick to C
    data types.

    Added R1, R2 to params (precomputed random points on the curve) to
    cut 0.05 seconds from the running time.

    I should mention that the other day I added an "ibe" account to rooster,
    and gave it the full name "Stanford IBE Private Key Generator" so it
    looks better when you receive your key. Plus I don't have to be logged in
    as ben.


Tue Sep 18 18:58:56 PDT 2001
    Thanks to Dan, now realized that the optimization I used in Weil pairing
    still applies to Tate pairing, so I removed a lot of unnecessary code.
    Though it still didn't improve the speed much. After more testing, it
    seems miller() takes less than .2 seconds, and now the bottleneck
    appears to be group_times in make_order_q where it must multiply by
    a 1024-160 bit number.

    A more detailed breakdown of where the time is spent (based on
    just one run with 1024-bit p, 160-bit q):

    0.01 initialization
    0.07 multiplying rP
    0.02 first part of map_to_point (call to G hash function + calculation
	of y coordinate)
    0.4  making the point order q (by multiplying by (p+1)/q)
    0.05 finding random R1, R2 for miller()
    0.2  miller()
    0.2  exponentiation due to using Tate pairing (must raise to
	(p^2 - 1)/q power i.e. 2048 - 160 bit number)
	This explains why using the Tate pairing doesn't seem to be much
	faster than using the Weil pairing
    0.02 raising g_id to the power of r

    After looking through my short signature code, I realize that I can
    shave 0.05 seconds off by using precalculated R1, R2. But first I'll
    try and improve group_times().

    Reactivating fast_group_times() reduces these a bit:
    0.06 multiplying rP
    0.3 making the point order q


Mon Aug 27 19:02:32 PDT 2001
    Added daemon_init() to daemonize pkghtml.cc. Decided not to inetd it
    because in principle it would be under heavy load.
    Intend to debug POST query handling to see why Mozilla doesn't like it.


Sat Jul 21 18:05:29 CDT 2001
    Forgot to log some entries: crosscompiled IBE a few days ago
    (see makefile.cross), though request doesn't work unfortunately.

    Added FMT_decrypt(). Being retabbing some files.

    [ibe-0.15.tgz]


Tue Jul 17 21:47:34 CDT 2001
    Fixed bug pointed out by Rishi in IBE_combine;
    it was delete[]ing index (relic of old code).

    Managed to cross-compile OpenSSL! Unfortunately I'm having
    trouble cross-compiling IBE; there seems to be a problem with
    ostrstream.


Fri Jul 13 02:16:54 CDT 2001
    Began writing a tutorial for the library. Also added comments here and
    there for Rishi et al.


Thu May 24 16:09:30 PDT 2001
    randomize_NTL() now closes the open fp.


Wed May 23 21:10:46 PDT 2001
    Fixed group_times so that you can do group_times(P, a, P).


Wed May 16 16:33:12 PDT 2001
    Minor changes to weil.cc. (Changed V *= V to sqr(V, V), got rid of unity.)
    This is because I found them while working on the short signatures
    project.


Mon Apr 30 17:59:45 PDT 2001
    Maybe 3 files are required? one for ibe_lib, one for file i/o and one
    for easy interface to libraries.


Fri Apr 27 12:43:35 PDT 2001
    Forgot to put in entry yesterday. Wrote FMT_construct_master, but haven't
    tested it.

    [ibe-0.14.tgz]


Wed Apr 25 16:56:03 PDT 2001
    Moved IBE_encrypt_to_fp, IBE_decrypt_from_fp to format.cc.
    Moved load_private and save_private to format.cc.

    Decided to move load_params, save_params as well:
    using file pointers is more portable, and splitting the file i/o
    part makes it more general (can fool around with many sets of parameters
    in memory rather than loading and saving all the time).

    Added call to randomize_NTL in IBE_init. Much safer now.

    Some design notes:
    weil.cc: low level elliptic curve stuff
	modify if you have faster math routines
	interface for cryptosystem developers

    ibe_lib.cc: basic cryptosystem, passes things around as ASCIIZ or
	    unsigned char * and length
	modify if changing cryptosystem, e.g. different hash function
	and also if adding more than basic encryption (at the moment can't
	encrypt big files)
	interface for library developers

    format.cc: handles file i/o (file formats)
	modify to change file formats
	interface for application developers

    Justification: file i/o and file formats don't have much to do with
	    the crypto side. ibe_lib.cc getting too big. OpenSSL separates
	    encryption and file I/O as well.
    
    Moved file I/O to format.cc
    Should make_id go in format?

    If format.cc is an API, is that where IBE_version, IBE_n and stuff
    should go? Or should format.cc just coexist with ibe_lib.cc?

    Keeping index separate to actual share means an extra argument to the
    functions. Could change by modifying load_key_share to concatenate
    index to share.

    bugfix: pkghtml.cc not checking validity of params file.

    Now construct_master doesn't work. FMT_construct_master must be rewritten.

    Need to rename some files.


Tue Apr 24 15:02:22 PDT 2001
    Added format.cc, coded new version of encrypt.cc.
    Rewrote IBE_encrypt, IBE_decrypt to use yesterday's functions.


Mon Apr 23 14:11:29 PDT 2001
    Added IBE_hidekey(), IBE_hidesinglekey(), IBE_revealkey(), IBE_verify().
    Compiled, but untested.


Wed Apr 18 18:27:29 PDT 2001
    Discovered that Bob's plugin doesn't work with infect. Added a bunch of
    MIME headers and changed format to conform with Bob's.
    Renamed decrypt to odecrypt, and added a new decrypt that takes Bob's
    format. Will have to do the same for encrypt.

    Will change nature of encrypt/decrypt in ibe_lib. Why not
    have it just deal with keys and not do hashing/encryption of message?
    Then I have a lot less to worry about e.g. allocating buffers for very
    long messages. In detail: when user calls encrypt(), they provide
    sigma, E_sigma(M) and Hash(M). My routine simply works out
    r = H_1(sigma, M) = H(sigma||Hash(M)), and returns rP, sigma xor H(gidr)
    Then the caller of decrypt() gives U, V. I return sigma, they find
    M, and they call a verify() with U, Hash(M), sigma to check integrity.
    Note I never touch W!


Thu Apr 12 16:18:27 PDT 2001
    Used mail -a flag to solve MIME header problem.


Sun Apr  8 13:58:47 PDT 2001
    Disabled banning temporarily, updated pkgform.html.

    [ibe-0.13.tgz]


Thu Apr  5 10:26:43 PDT 2001
    Finally did private key password. Still has fixed IV though.
    Rudimentary banned list added.
    Added GPL to beginning of each source file. Got rid of nettest.cc,
    ssl*.cc and other debugging programs.

    Don't know what about to do with no fork() in Windows problem. Maybe
    select can help?

    Wrote infect.cc, that sends someone their first encrypted message.
    Probably should rename...

    Renamed params to params.txt to make things easier for Bob.


Wed Apr  4 18:10:25 PDT 2001

    Was able to cross-compile NTL with GMP! Now I'll see if Bob can use the
    libraries I made. Details below.

    First copy GetTime4.c to GetTime.c, and then modify make.tail
    and run my crossntl script. For make.tail, I commented out setup2 and setup4
    and added "HOSTCOMPILE" and "HOSTLINK" so setup1 and setup3 produce
    executables that can be run on the host. crossntl is something like

    ./configure CC=i586-mingw32msvc-gcc \
    CXX=i586-mingw32msvc-g++ \
    AR=i586-mingw32msvc-ar \
    RANLIB=i586-mingw32msvc-ranlib \
    GMP_INCDIR=-I/tmp \
    NTL_GMP_LIP=on


Mon Apr  2 12:35:32 PDT 2001
    Renamed UTL_config to config.
    Added purpose field, renamed "mail" to "id".
    Added date (just the year) field.
    Now:
    "purpose=email&date=2001&id=[e-mail]&subject=foo&system=bar"
    Fp2 power now uses sliding windows. Continued optimizations.
    Tate pairing now just under a second, weil pairing just over.
    (0.98, 1.06 seconds.)

    Cross-compiled GMP. Was surprisingly easy. Just configure with these
    options:

    ./configure host=pentium3-pc-linux-gnu target=pentium3-pc-mingw32 \
    CC=i586-mingw32msvc-gcc \
    LD=i586-mingw32msvc-ld \
    RANLIB=i586-mingw32msvc-ranlib \
    NM=i586-mingw32msvc-nm \
    AR=i586-mingw32msvc-ar \
    AS=i586-mingw32msvc-as \
    STRIP=i586-mingw32msvc-strip \
    DLLTOOL=i586-mingw32msvc-dlltool \
    OBJDUMP=i586-mingw32msvc-objdump

    Still having trouble with cross-compiling NTL with GMP. First hurdle:
    sys/resource.h doesn't exist in Windows.


Thu Mar 22 19:37:16 PST 2001
    Talked with Victor Shoup today. Turns out I was misinterpreting gprof
    results completely! Still takes 1.2 seconds on new machine, and almost 3s
    on laptop.

    Optimized low-level Fp2 routines. (Made it like assembly language.)
    No noticeable speedup(!). Will try more later.

    [ibe-0.12.tgz]


Mon Mar 19 13:03:18 PST 2001
    With NTL compiled using GMP, it only takes 0.25 seconds on the laptop
    (and 0.05 on my new machine in the office). However, I still intend to
    add Tate pairing to weil.cc. test.cc modified to test Tate pairing
    instead.

    Finally have it working now. To port system to ehat, must ensure
    q does not divide p-1 (only 1/2^160 chance of this) and we're done.


Tue Mar  6 20:31:33 PST 2001
    Found another strange bug that didn't matter; I was calling init() in
    ibe_lib too early (q wasn't initialized!) but why does it work? q seems
    to hold the correct value. Wasn't the only bug either.
    Got rid of global p, q in ibe_lib.cc to avoid confusion.

    The fast version of group_times breaks on ibe_test often because of
    point at infinity problems. Will use slow version for now.

    Split U, V, W so email for multiple recipients will work.
    Changed id from unsigned char* to char*.
    Made params file human-readable on request.
    Added IBE_make_id()

    [ibe-0.11.tgz]


Mon Mar  5 13:41:48 PST 2001
    Implemented Dan's new version of Miller's algorithm. Now takes 25 seconds.
    With random points shortcut (only works for p = 2 mod 3) takes 9 seconds.

    Ideas left to try: move to GMP, sliding windows instead of repeated
    squaring, group_times only in F_p, proj. coords in group_times