『中世なぞなぞ集』 (Chuusei nazonazo shuu) is, as the title says, a Collection of Medieval Riddles -- or, more accurately, a modern collection of several medieval collections of (medieval) riddles. Yes, I think I can safely say that this is the only book of medieval Japanese riddles you will ever need.

The Japanese word for "riddle" (nazo, or the SE Asia-style repeated version nazonazo) actually comes from 何ぞ, nanzo?, "What [is it/am I/etc.]?" The solution to solving a nazo of the variety depicted here lies not in "the more you take away, the bigger I become" logic tricks, but rather, word-, phone- and radicalplay. Here's an example from a 16th-century collection:

うはぎえしたる雪ぞたえせぬ
uhagie sitaru yuki zo / tae senu
snow with the top gone / without ceasing

Since the word for "snow" is yuki, and the "top" of this word (when written vertically as two kana: ゆき) is yu, the first line gives us ki. The second line actually requires us to think of another word for the idea of "always". The one we want is tsune (常). ki + tsune = kitsune, fox.

Virtually all of the riddles in the book shake out something like that. Some of them are ridiculously easy. Some of them are ridiculously hard, for one or more of several reasons:

1. the answer is a word that is now archaic;
2. they require a cryptic crossword-style understanding of conventions (e.g. tengu usually represents the sound ma, as in 魔, devil); or
3. there are just too many possible solutions, Dan Brown-style.

A good example of the latter case is one where the entire clue is hotoke, "Buddha", from which we are supposed to get kusari, "chain", because Buddha makes suffering (ku) depart (sari). I mean, come on, medieval Japanese word-nerds. That's not a riddle. It's just a pun. Puns do not need to be collected for the ages.

Nevertheless, I have gathered together four riddles that I think a speaker and reader of modern Japanese might have a decent chance at solving. Easy to hard, hints if you need 'em for the harder ones. Answers in comments. (Note that I'm only throwing in the English translations as a CJ comprehension aid -- obviously, you really have to think about the original Japanese to get these.) (Later note: I just realized that I've mostly picked kanji-based ones. Oh well.)

1. 廿人木にのぼる
   nizifunin ki ni noboru
   "Twenty people climbing a tree."
2. かミをミればしもにありしもをみればかミにありはゝのハらをとをりて子のかたにあり
   kami wo mireba simo ni ari / simo wo mireba kami ni ari / haha no hara wo toworite / ko no kata ni ari
   "Look at the top, and it's on the bottom / look at the bottom and it's on top / it goes through the mother's middle / and is in the child's side."
3. うへもなきおもひを仏ときたまふ
   uhe mo naki omohi wo hotoke tokitamahu
   "Buddha explains a thought with no top." (Hint.)
4. きたみなミにしまで風の吹あれて
   kita minami nisi made kaze no hukiarete
   "The wind rages to the north, south and west..." (Hint, part 1. Hint, part 2.)