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.txtThu 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 rThu 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 qMon 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=onMon 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=blynn@cs.stanford.edu&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